| # | Problem | Pass Rate (passed user / total user) |
|---|---|---|
| 10193 | moocHW6a |
|
| 10194 | moocHW6b |
|
| 10195 | moocHW6c |
|
| 10221 | moocHW7a |
|
| 10222 | moocHW7b |
|
| 10223 | moocHW7c |
|
| 10241 | moocFinal1_換銅板 |
|
| 10242 | moocFinal2_M 皇后 N 城堡 |
|
| 10243 | moocFinal3_Max Pooling |
|
| 10244 | moocFinal4_高維度稀疏向量 |
|
| 10245 | Spiral Matrix |
|
Description
以範例程式為基礎，完成其中缺少的 zip 函數。這個函數的作用是將兩個 lists 合併，對應位置的元素組成一個 pair，然後產生一個新的 list 包含所有的 pairs。也就是從兩個 lists 變成一個 list of pairs。
底下的表示法，方括號 [] 代表 list，圓括弧 () 代表 pair。
譬如第一個 list 是 [1,2,3] 而第二個是 ["a","b","c"]，經過 zip 之後變成
[(1,"a"),(2,"b"),(3,"c")]。
接著如果再用第二個 list 和第一次 zip 之後的結果，再做一次 zip，結果會變成
[("a",(1,"a")),("b",(2,"b")),("c",(3,"c"))]
然後第一次 zip 和第二次 zip 得到的兩個 lists，再做第三次 zip 就變成
[((1,"a"),("a",(1,"a"))),((2,"b"),("b",(2,"b"))),((3,"c"),("c",(3,"c")))]
上述的操作已經寫在範例程式中，只要將 zip 正確寫出，就能產生上述的執行結果。
範例程式:
Input
輸入資料會有五行。
第一行是一個整數 M1，代表第一個 list 包含的資料筆數，第二行則是 M1 筆資料，每筆用空白隔開。
第三行是一個整數 M2，代表第二個 list 包含的資料筆數，第四行則是 M2 筆資料，每筆用空白隔開。
第五行則是一個整數 N。代表執行 zip 的次數。
Output
輸出只有一行，列出經過 zip 之後的 list 內容。最後有換行。
Sample Input Download
Sample Output Download
Tags
Discuss
Description
同樣是以範例程式，完成其中缺少的 unzip函數。這個函數的作用是將 a list of pairs 變成 a pair of lists。
底下的表示法，方括號 [] 代表 list，圓括弧 () 代表 pair。
譬如原本的 list of pairs 是 [(1,"a"),(2,"b"),(3,"c")]，經過 unzip 之後變成 ([1,2,3],["a","b","c"])。
如果有兩個 lists [1,2,3] 和]["a","b","c"]，先做第一題描述的兩次 zip，變成
[("a",(1,"a")),("b",(2,"b")),("c",(3,"c"))] 之後，如果再做一次 unzip 就變成
(["a","b","c"],[(1,"a"),(2,"b"),(3,"c")])
這一題要做的就是，輸入兩個 lists，經過 N 次 zip 之後，再做一次 unzip，然後輸出最後產生的 pair。
上述的操作已經寫在範例程式中，只要將 unzip 正確寫出，就能產生上述的執行結果。
範例程式:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#define STR_EXPAND(tok) #tok
#define STR(tok) STR_EXPAND(tok)
#define STR_LEN 20
/* incomplete struct Atom */
struct Atom;
/* a pair of atom */
typedef struct Pair {
struct Atom *left;
struct Atom *right;
} Pair;
/* a list of atoms */
typedef struct List {
struct Atom *data;
struct List *next;
} List;
/* an atom can be a string, an int, a pair of atoms, or a list */
typedef struct Atom {
char str[STR_LEN+1];
int val;
Pair *pair;
List *lst;
int dtype; /* 0 for string, 1 for int, 2 for pair, 3 for list*/
} Atom;
/* functions for creating an atom */
Atom* atom_str(char *str);
Atom* atom_val(int val);
Atom* copy_atom(Atom *aptr);
void print_atom(Atom *aptr);
void free_atom(Atom *atpr);
/* convert an atom to a single-atom list */
List* atom_to_list(Atom *a);
/* this function is important */
/* useful for creating a new copy of an existing list */
List* cons(Atom *a, List *b);
void print_list(List *lptr);
void free_list(List *lptr);
int length(List *lptr);
List* read_list_helper(List *l, int n);
List* read_list(void);
Atom* head(List *lptr);
List* tail(List *lptr);
List* zip(List *lptr1, List *lptr2);
Pair* unzip(List *lptr);
List* take(int n, List *l);
List* drop(int n, List *l);
Pair* pair_list(List *lptr1, List *lptr2);
Pair* split_at(int n, List *l);
void print_pair(Pair* p);
void free_pair(Pair* p);
int main(void)
{
List *s1, *s2, *s3;
Pair *p;
int N, i;
s1 = read_list();
s2 = read_list();
scanf("%d", &N);
for (i=0; istr[0] = 'Θ';
} else {
strncpy(aptr->str, str, STR_LEN);
}
aptr->val = 0;
aptr->pair = NULL;
aptr->lst = NULL;
aptr->dtype = 0;
return aptr;
}
/* Given a value, create a new atom */
Atom* atom_val(int val)
{
Atom *aptr = (Atom*) malloc(sizeof(Atom));
aptr->str[0] = 'Θ';
aptr->val = val;
aptr->pair = NULL;
aptr->lst = NULL;
aptr->dtype = 1;
return aptr;
}
Atom* copy_atom(Atom *aptr)
{
Atom *aptr_new;
aptr_new = (Atom*) malloc(sizeof(Atom));
if (aptr_new==NULL) return NULL;
if (aptr==NULL) return NULL;
aptr_new->dtype = aptr->dtype;
if (aptr->dtype == 0) {
strncpy(aptr_new->str, aptr->str, STR_LEN);
} else if (aptr->dtype == 1) {
aptr_new->val = aptr->val;
} else if (aptr->dtype == 2) {
if (aptr->pair == NULL) {
aptr_new->pair = NULL;
} else {
aptr_new->pair = (Pair *) malloc(sizeof(Pair));
aptr_new->pair->left = copy_atom(aptr->pair->left);
aptr_new->pair->right = copy_atom(aptr->pair->right);
}
} else if (aptr->dtype == 3) {
if (aptr->lst==NULL) {
aptr_new->lst = NULL;
} else {
aptr_new->lst = cons(head(aptr->lst), tail(aptr->lst));
}
}
return aptr_new;
}
void print_atom(Atom *aptr)
{
if (aptr==NULL) {
printf("Empty");
return;
}
switch (aptr->dtype) {
case 0:
printf("\"%s\"", aptr->str);
break;
case 1:
printf("%d", aptr->val);
break;
case 2:
print_pair(aptr->pair);
break;
case 3:
print_list(aptr->lst);
break;
default:
printf("Undefined.");
}
}
/* Given an atom, create a list containing the atom. */
List* atom_to_list(Atom *a)
{
List *b;
b = (List*) malloc(sizeof(List));
b->next = NULL;
b->data = copy_atom(a);
return b;
}
/* create a new list and add the atom to the head */
List* cons(Atom *a, List *b)
{
List *c;
c = atom_to_list(a);
if (b!=NULL) {
c->next = cons(head(b), tail(b));
}
return c;
}
void print_list(List *lptr)
{
printf("[");
while (lptr!=NULL) {
print_atom(lptr->data);
if (lptr->next != NULL)
printf(",");
lptr = lptr->next;
}
printf("]");
}
int len_helper(List *lptr, int len)
{
if (lptr==NULL) return len;
else return len_helper(lptr->next, len+1);
}
int length(List *lptr)
{
return len_helper(lptr, 0);
}
void free_atom(Atom *aptr)
{
if (aptr != NULL) {
if (aptr->dtype==2) {
free_pair(aptr->pair);
} else if (aptr->dtype==3) {
free_list(aptr->lst);
}
free(aptr);
}
}
void free_list(List *lptr)
{
List *p;
if (lptr!=NULL) {
p = tail(lptr);
if (head(lptr)!=NULL) {
free_atom(head(lptr));
}
free_list(p);
}
}
Atom* head(List *lptr)
{
return lptr->data;
}
List* tail(List *lptr)
{
return (lptr==NULL) ? NULL : lptr->next;
}
/* create a new list combining a string list and a value list
If the two input lists have different lengths, the new list will be
of the same length as the shorter one.
*/
List* zip(List *lptr1, List *lptr2)
{
Atom a;
List *l1, *l2;
if ( ??? ) { //lptr1 或 lptr2 兩者有一個是 NULL
return NULL;
} else {
a.pair = ???; // malloc 取得一塊 Pair 空間
a.pair->left = ???; // 利用 copy_atom 複製 lptr1 的開頭第一個 atom
a.pair->right = ???; // 利用 copy_atom 複製 lptr2 的開頭第一個 atom
a.dtype = 2;
l1 = ??? // 利用 zip 處理剩下的 lists (提示: 用遞迴)
l2 = cons(&a, l1); // 利用 cons 造出新的 list
free_pair(a.pair);
free_list(l1);
return l2;
}
}
Pair* unzip(List *lptr)
{
Atom *h;
Pair *p, *newp;
List *l1, *l2;
if (lptr==NULL) {
newp = pair_list(NULL, NULL);
return newp;
}
h = ???; // // 取出 lptr 的開頭第一個 atom
p = ???; // 利用 unzip 對剩下的 lptr 遞迴繼續處理
l1 = ???; // 兩個 lists 分別來自兩個 cons
l2 = ???; // 一個 cons 組合左邊的 list 另一個組合右邊的 list
newp = ???; // // 利用 pair_list 從兩個 lists 產生新的 pair
free_list(l1);
free_list(l2);
free_pair(p);
return newp;
}
Pair* pair_list(List *lptr1, List *lptr2)
{
Pair *p;
Atom a;
p = (Pair*)malloc(sizeof(Pair));
a.dtype = 3;
a.lst = lptr1;
p->left = copy_atom(&a);
a.lst = lptr2;
p->right = copy_atom(&a);
return p;
}
void print_pair(Pair *p)
{
printf("(");
print_atom(p->left);
printf(",");
print_atom(p->right);
printf(")");
}
void free_pair(Pair* p)
{
if (p!=NULL) {
free_atom(p->left);
free_atom(p->right);
free(p);
}
}
Input
與第一題相同。輸入資料會有五行。
第一行是一個整數 M1，代表第一個 list 包含的資料筆數，第二行則是 M1 筆資料，每筆用空白隔開。
第三行是一個整數 M2，代表第二個 list 包含的資料筆數，第四行則是 M2 筆資料，每筆用空白隔開。
第五行則是一個整數 N。代表執行 zip 的次數。
Output
輸出只有一行，列出經過 N次 zip 之後再做一次 upzip 得到的 pair 內容。最後有換行。
Sample Input Download
Sample Output Download
Tags
Discuss
Description
同樣是以範例程式，完成其中缺少的 take, drop, split_at函數。
假設某個 list 長得像 [10,20,30,40,50]
take(2, list) 的作用是產生一個新的 list 只取前2個元素，所以是 [10,20]
drop(2, list) 的作用是產生一個新的 list 去掉前2個元素，所以是 [30,40,50]
split_at(2, list) 則會把產生一個 pair 裡面包含兩段 lists，切斷點是在第2個元素，所以變成
([10,20],[30,40,50])。這個函數可以用 take 和 drop 做出來。
有了 take, drop, split_at 之後，這一題要做到的效果很簡單，只是把輸入的list，利用 split_at，把list從中間切斷再交換順序輸出。
這樣的工作當然用 array 也可以輕鬆做到，但是我們的目的是練習 C 結構以及指標和記憶體的使用，所以大家還是盡量練習看看。
範例程式:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#define STR_EXPAND(tok) #tok
#define STR(tok) STR_EXPAND(tok)
#define STR_LEN 20
/* incomplete struct Atom */
struct Atom;
/* a pair of atom */
typedef struct Pair {
struct Atom *left;
struct Atom *right;
} Pair;
/* a list of atoms */
typedef struct List {
struct Atom *data;
struct List *next;
} List;
/* an atom can be a string, an int, a pair of atoms, or a list */
typedef struct Atom {
char str[STR_LEN+1];
int val;
Pair *pair;
List *lst;
int dtype; /* 0 for string, 1 for int, 2 for pair, 3 for list*/
} Atom;
/* functions for creating an atom */
Atom* atom_str(char *str);
Atom* atom_val(int val);
Atom* copy_atom(Atom *aptr);
void print_atom(Atom *aptr);
void free_atom(Atom *atpr);
/* convert an atom to a single-atom list */
List* atom_to_list(Atom *a);
/* this function is important */
/* useful for creating a new copy of an existing list */
List* cons(Atom *a, List *b);
void print_list(List *lptr);
void free_list(List *lptr);
int length(List *lptr);
List* read_list_helper(List *l, int n);
List* read_list(void);
Atom* head(List *lptr);
List* tail(List *lptr);
List* zip(List *lptr1, List *lptr2);
Pair* unzip(List *lptr);
List* take(int n, List *l);
List* drop(int n, List *l);
Pair* pair_list(List *lptr1, List *lptr2);
Pair* split_at(int n, List *l);
void print_pair(Pair* p);
void free_pair(Pair* p);
int main(void)
{
List *s1;
Pair *p1;
Atom *tmp;
s1 = read_list();
p1 = split_at(length(s1)/2, s1);
tmp = p1->left;
p1->left = p1->right;
p1->right = tmp;
print_pair(p1);
printf("\n");
return 0;
}
List* read_list_helper(List *l, int n)
{
Atom *a;
int x;
char str[STR_LEN+1];
List *l1, *l2;
if (n==0) {
return l;
} else {
if (scanf("%d", &x)==1) {
a = atom_val(x);
} else {
scanf("%"STR(STR_LEN)"s", str);
while(!isspace(getchar()));
a = atom_str(str);
}
l1 = read_list_helper(l, n-1);
l2 = cons(a, l1);
free_list(l1);
return l2;
}
}
List* read_list(void)
{
int ndata;
scanf("%d", &ndata);
return read_list_helper(NULL, ndata);
}
/* Given a string, create a new atom */
Atom* atom_str(char *str)
{
Atom *aptr = (Atom*) malloc(sizeof(Atom));
if (str==NULL) {
aptr->str[0] = 'Θ';
} else {
strncpy(aptr->str, str, STR_LEN);
}
aptr->val = 0;
aptr->pair = NULL;
aptr->lst = NULL;
aptr->dtype = 0;
return aptr;
}
/* Given a value, create a new atom */
Atom* atom_val(int val)
{
Atom *aptr = (Atom*) malloc(sizeof(Atom));
aptr->str[0] = 'Θ';
aptr->val = val;
aptr->pair = NULL;
aptr->lst = NULL;
aptr->dtype = 1;
return aptr;
}
Atom* copy_atom(Atom *aptr)
{
Atom *aptr_new;
aptr_new = (Atom*) malloc(sizeof(Atom));
if (aptr_new==NULL) return NULL;
if (aptr==NULL) return NULL;
aptr_new->dtype = aptr->dtype;
if (aptr->dtype == 0) {
strncpy(aptr_new->str, aptr->str, STR_LEN);
} else if (aptr->dtype == 1) {
aptr_new->val = aptr->val;
} else if (aptr->dtype == 2) {
if (aptr->pair == NULL) {
aptr_new->pair = NULL;
} else {
aptr_new->pair = (Pair *) malloc(sizeof(Pair));
aptr_new->pair->left = copy_atom(aptr->pair->left);
aptr_new->pair->right = copy_atom(aptr->pair->right);
}
} else if (aptr->dtype == 3) {
if (aptr->lst==NULL) {
aptr_new->lst = NULL;
} else {
aptr_new->lst = cons(head(aptr->lst), tail(aptr->lst));
}
}
return aptr_new;
}
void print_atom(Atom *aptr)
{
if (aptr==NULL) {
printf("Empty");
return;
}
switch (aptr->dtype) {
case 0:
printf("\"%s\"", aptr->str);
break;
case 1:
printf("%d", aptr->val);
break;
case 2:
print_pair(aptr->pair);
break;
case 3:
print_list(aptr->lst);
break;
default:
printf("Undefined.");
}
}
/* Given an atom, create a list containing the atom. */
List* atom_to_list(Atom *a)
{
List *b;
b = (List*) malloc(sizeof(List));
b->next = NULL;
b->data = copy_atom(a);
return b;
}
/* create a new list and add the atom to the head */
List* cons(Atom *a, List *b)
{
List *c;
c = atom_to_list(a);
if (b!=NULL) {
c->next = cons(head(b), tail(b));
}
return c;
}
void print_list(List *lptr)
{
printf("[");
while (lptr!=NULL) {
print_atom(lptr->data);
if (lptr->next != NULL)
printf(",");
lptr = lptr->next;
}
printf("]");
}
int len_helper(List *lptr, int len)
{
if (lptr==NULL) return len;
else return len_helper(lptr->next, len+1);
}
int length(List *lptr)
{
return len_helper(lptr, 0);
}
void free_atom(Atom *aptr)
{
if (aptr != NULL) {
if (aptr->dtype==2) {
free_pair(aptr->pair);
} else if (aptr->dtype==3) {
free_list(aptr->lst);
}
free(aptr);
}
}
void free_list(List *lptr)
{
List *p;
if (lptr!=NULL) {
p = tail(lptr);
if (head(lptr)!=NULL) {
free_atom(head(lptr));
}
free_list(p);
}
}
Atom* head(List *lptr)
{
return lptr->data;
}
List* tail(List *lptr)
{
return (lptr==NULL) ? NULL : lptr->next;
}
List* take(int n, List *lptr)
{
/*
判斷 n 的值決定是否繼續
利用 cons 搭配 take 的遞迴呼叫 建構出回傳的 list
*/
}
List* drop(int n, List *lptr)
{
/*
判斷 n 的值決定是否繼續
利用 cons 搭配 drop 的遞迴呼叫 建構出回傳的 list
*/
}
Pair* pair_list(List *lptr1, List *lptr2)
{
Pair *p;
Atom a;
p = (Pair*)malloc(sizeof(Pair));
a.dtype = 3;
a.lst = lptr1;
p->left = copy_atom(&a);
a.lst = lptr2;
p->right = copy_atom(&a);
return p;
}
Pair* split_at(int n, List *lptr)
{
Pair *p;
Atom a;
/* 參考 pair_list 的寫法
利用 take 和 drop 還有 copy_atom
做出 split_at
*/
return p;
}
void print_pair(Pair *p)
{
printf("(");
print_atom(p->left);
printf(",");
print_atom(p->right);
printf(")");
}
void free_pair(Pair* p)
{
if (p!=NULL) {
free_atom(p->left);
free_atom(p->right);
free(p);
}
}
Input
輸入資料會有兩行
第一行是一個整數 M1，代表 list 包含的資料筆數。第二行是 list 的內容。
Output
輸出只有一行，是從中間切斷之後交換前後兩段。最後有換行。
Sample Input Download
Sample Output Download
Tags
Discuss
Description
搜尋某個產品名稱
找出符合的產品
並且依照評價高低
從評價高分到低分排序
如果評價相同
則繼續依照價格由低價到高價排序
範例程式：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
// #define ONLINE_JUDGE
/*
struct for product items
*/
typedef struct _Product {
char name[51];
float price;
float review;
int num_reviews;
} Product;
int compare(const void *a, const void *b)
{
Product *ia, *ib;
ia = *(Product **)a;
ib = *(Product **)b;
/* your code here */
}
void show_product(Product *item)
{
printf("%s, ", item->name);
printf("$%.2f, ", item->price);
printf("%.1f\n", item->review);
}
int main(void)
{
Product **items;
int i, j;
int ndata, nqueries;
char query[51];
#ifndef ONLINE_JUDGE
freopen("testcase1", "r", stdin);
//freopen("out1", "w", stdout);
#endif
scanf("%d", &ndata);
while (getchar() !='\n');
items = (Product**) malloc(sizeof(Product*) * ndata);
for (i=0; i<ndata; i++) {
items[i] = (Product*) malloc(sizeof(Product));
fgets(items[i]->name, 31, stdin);
items[i]->name[strlen(items[i]->name)-1] = 0;
scanf("%f", &items[i]->price);
scanf("%f", &items[i]->review);
scanf("%d", &items[i]->num_reviews);
while (getchar() !='\n');
}
scanf("%d", &nqueries);
while (getchar() !='\n');
qsort(items, ndata, sizeof(Product *), compare);
for (i=0; i<nqueries; i++) {
/* your code */
}
for (i=0; i<ndata; i++) {
free(items[i]);
}
free(items);
return 0;
}
Input
第一行的數字代表有幾個產品
接著每四行代表一個產品的資訊：
產品名稱
產品價格
產品評價
產品評價數
再來是一個數字，代表有幾筆 query
之後的每一行代表一筆 query
每筆 query 的內容為品牌名稱
Output
根據每筆 query 輸出：
品牌名稱
產品名稱1, 產品價格1, 產品評價1
...
產品名稱N, 產品價格N, 產品評價N
每一個品牌名稱下面可能會接好幾個產品
請依照題目要求將這些產品排序好
Sample Input Download
Sample Output Download
Tags
Discuss
Description
搜尋某個價位之間的產品
先依品牌名稱排序
同一品牌再依照評價從高到低排序
評價相同再依照價位由低價到高價排序
提示：
1. 自己寫一個字串比對的函數，只比對品牌名稱，也就是兩個字串從開頭一直比到到第一個空白出現為止。如果都完全一樣就傳回 0 ，否則就依照字元 ASCII 大小傳回 正值或負值。
2. 呼叫 qsort 進行排序，主要任務是把 qsort 需要的 compare 函數寫出來
3. 都用指標陣列，讓排序的動作只會改變指標，而不需要真的搬動 data item。
範例程式：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
// #define ONLINE_JUDGE
/*
struct for product items
*/
typedef struct _Product {
char name[51];
float price;
float review;
int num_reviews;
} Product;
int compare(const void *a, const void *b)
{
Product *ia, *ib;
ia = *(Product **)a;
ib = *(Product **)b;
/* your code here */
}
int my_strcmp(char *s1, char *s2)
{
/* your code here */
}
int compare_name(const void *a, const void *b)
{
/* your code here */
}
void show_product(Product *item)
{
printf("%s, ", item->name);
printf("$%.2f, ", item->price);
printf("%.1f\n", item->review);
}
int main(void)
{
Product **items;
int i, j;
int ndata, nqueries;
Product **filtered;
float lower, upper;
int num;
#ifndef ONLINE_JUDGE
freopen("testcase2", "r", stdin);
//freopen("out1", "w", stdout);
#endif
scanf("%d", &ndata);
while (getchar() !='\n');
items = (Product**) malloc(sizeof(Product*) * ndata);
for (i=0; i<ndata; i++) {
items[i] = (Product*) malloc(sizeof(Product));
fgets(items[i]->name, 31, stdin);
items[i]->name[strlen(items[i]->name)-1] = '\0';
scanf("%f", &items[i]->price);
scanf("%f", &items[i]->review);
scanf("%d", &items[i]->num_reviews);
while (getchar() !='\n');
}
scanf("%d", &nqueries);
while (getchar() !='\n');
qsort(items, ndata, sizeof(Product *), compare);
filtered = (Product**) malloc(sizeof(Product*) * ndata);
for (i=0; i<nqueries; i++) {
scanf("%f%f", &lower, &upper);
printf("%.2f<=price<=%.2f\n", lower, upper);
/* your code here */
}
for (i=0; i<ndata; i++) {
free(items[i]);
}
free(items);
free(filtered);
return 0;
}
Input
第一行的數字代表有幾個產品
接著每四行代表一個產品的資訊：
產品名稱
產品價格
產品評價
產品評價數
再來是一個數字，代表有幾筆 query
之後的每一行代表一筆 query
每筆 query 由兩個數字組成，代表價格區間
Output
根據每筆 query 輸出：
價格下限<=price<=價格上限
產品名稱1, 產品價格1, 產品評價1
...
產品名稱N, 產品價格N, 產品評價N
每一個價格區間下面可能會接好幾個產品
請依照題目要求將這些產品排序好
Sample Input Download
Sample Output Download
Tags
Discuss
Description
回到上一周的範例
這次要寫出 map 函數
以及搭配 map 使用的 atom_toupper 函數
map 的作用是傳入一個 list 以及一個函數指標
最後會產生一個新的 list
新的 list 的每個 atom
都是經過函數指標所指到的函數所處理過後的新的 atom
譬如某個 list 是 [1,2,3,4,5]
用 map 套用 atom_square 函數 (作用是將 atom 的值變成平方)
結果得到一個新的 list [1,4,9,16,25]
又例如某個 list 是["aa","bb","cc","dd","ee"]
套用 atom_toupper 函數 (作用是把字串的每個字元都變成大寫)
結果得到 ["AA","BB","CC","DD","EE"]
範例程式：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#define STR_EXPAND(tok) #tok
#define STR(tok) STR_EXPAND(tok)
#define STR_LEN 20
/* incomplete struct Atom */
struct Atom;
/* a pair of atom */
typedef struct Pair {
struct Atom *left;
struct Atom *right;
} Pair;
/* a list of atoms */
typedef struct List {
struct Atom *data;
struct List *next;
} List;
/* an atom can be a string, an int, a pair of atoms, or a list */
typedef struct Atom {
char str[STR_LEN+1];
int val;
Pair *pair;
List *lst;
int dtype; /* 0 for string, 1 for int, 2 for pair, 3 for list*/
} Atom;
/* functions for creating an atom */
Atom* atom_str(char *str);
Atom* atom_val(int val);
Atom* copy_atom(Atom *aptr);
void print_atom(Atom *aptr);
void free_atom(Atom *atpr);
/* convert an atom to a single-atom list */
List* atom_to_list(Atom *a);
/* this function is important */
/* useful for creating a new copy of an existing list */
List* cons(Atom *a, List *b);
void print_list(List *lptr);
void free_list(List *lptr);
int length(List *lptr);
List* read_list_helper(List *l, int n);
List* read_list(void);
Atom* head(List *lptr);
List* tail(List *lptr);
List* zip(List *lptr1, List *lptr2);
Pair* unzip(List *lptr);
List* take(int n, List *l);
List* drop(int n, List *l);
Pair* pair_list(List *lptr1, List *lptr2);
Pair* split_at(int n, List *l);
void print_pair(Pair* p);
void free_pair(Pair* p);
Atom* atom_toupper(Atom *a);
Atom* atom_square(Atom *a);
List* map(List *lptr, Atom* (*f)(Atom *));
int main(void)
{
List *s1, *s2, *s3, *s4;
s1 = read_list();
s3 = read_list();
s2 = map(s1, atom_square);
s4 = map(s3, atom_toupper);
print_list(s2);
printf("\n");
print_list(s4);
printf("\n");
return 0;
}
List* read_list_helper(List *l, int n)
{
Atom *a;
int x;
char str[STR_LEN+1];
List *l1, *l2;
if (n==0) {
return l;
} else {
if (scanf("%d", &x)==1) {
a = atom_val(x);
} else {
scanf("%"STR(STR_LEN)"s", str);
while(!isspace(getchar()));
a = atom_str(str);
}
l1 = read_list_helper(l, n-1);
l2 = cons(a, l1);
free_list(l1);
return l2;
}
}
List* read_list(void)
{
int ndata;
scanf("%d", &ndata);
return read_list_helper(NULL, ndata);
}
/* Given a string, create a new atom */
Atom* atom_str(char *str)
{
Atom *aptr = (Atom*) malloc(sizeof(Atom));
if (str==NULL) {
aptr->str[0] = '\0';
} else {
strncpy(aptr->str, str, STR_LEN);
}
aptr->val = 0;
aptr->pair = NULL;
aptr->lst = NULL;
aptr->dtype = 0;
return aptr;
}
/* Given a value, create a new atom */
Atom* atom_val(int val)
{
Atom *aptr = (Atom*) malloc(sizeof(Atom));
aptr->str[0] = '\0';
aptr->val = val;
aptr->pair = NULL;
aptr->lst = NULL;
aptr->dtype = 1;
return aptr;
}
Atom* copy_atom(Atom *aptr)
{
Atom *aptr_new;
aptr_new = (Atom*) malloc(sizeof(Atom));
if (aptr_new==NULL) return NULL;
if (aptr==NULL) return NULL;
aptr_new->dtype = aptr->dtype;
if (aptr->dtype == 0) {
strncpy(aptr_new->str, aptr->str, STR_LEN);
} else if (aptr->dtype == 1) {
aptr_new->val = aptr->val;
} else if (aptr->dtype == 2) {
if (aptr->pair == NULL) {
aptr_new->pair = NULL;
} else {
aptr_new->pair = (Pair *) malloc(sizeof(Pair));
aptr_new->pair->left = copy_atom(aptr->pair->left);
aptr_new->pair->right = copy_atom(aptr->pair->right);
}
} else if (aptr->dtype == 3) {
if (aptr->lst==NULL) {
aptr_new->lst = NULL;
} else {
aptr_new->lst = cons(head(aptr->lst), tail(aptr->lst));
}
}
return aptr_new;
}
void print_atom(Atom *aptr)
{
if (aptr==NULL) {
printf("Empty");
return;
}
switch (aptr->dtype) {
case 0:
printf("\"%s\"", aptr->str);
break;
case 1:
printf("%d", aptr->val);
break;
case 2:
print_pair(aptr->pair);
break;
case 3:
print_list(aptr->lst);
break;
default:
printf("Undefined.");
}
}
/* Given an atom, create a list containing the atom. */
List* atom_to_list(Atom *a)
{
List *b;
b = (List*) malloc(sizeof(List));
b->next = NULL;
b->data = copy_atom(a);
return b;
}
/* create a new list and add the atom to the head */
List* cons(Atom *a, List *b)
{
List *c;
c = atom_to_list(a);
if (b!=NULL) {
c->next = cons(head(b), tail(b));
}
return c;
}
void print_list(List *lptr)
{
printf("[");
while (lptr!=NULL) {
print_atom(lptr->data);
if (lptr->next != NULL)
printf(",");
lptr = lptr->next;
}
printf("]");
}
int len_helper(List *lptr, int len)
{
if (lptr==NULL) return len;
else return len_helper(lptr->next, len+1);
}
int length(List *lptr)
{
return len_helper(lptr, 0);
}
void free_atom(Atom *aptr)
{
if (aptr != NULL) {
if (aptr->dtype==2) {
free_pair(aptr->pair);
} else if (aptr->dtype==3) {
free_list(aptr->lst);
}
free(aptr);
}
}
void free_list(List *lptr)
{
List *p;
if (lptr!=NULL) {
p = tail(lptr);
if (head(lptr)!=NULL) {
free_atom(head(lptr));
}
free_list(p);
}
}
Atom* head(List *lptr)
{
return lptr->data;
}
List* tail(List *lptr)
{
return (lptr==NULL) ? NULL : lptr->next;
}
Pair* pair_list(List *lptr1, List *lptr2)
{
Pair *p;
Atom a;
p = (Pair*)malloc(sizeof(Pair));
a.dtype = 3;
a.lst = lptr1;
p->left = copy_atom(&a);
a.lst = lptr2;
p->right = copy_atom(&a);
return p;
}
void print_pair(Pair *p)
{
printf("(");
print_atom(p->left);
printf(",");
print_atom(p->right);
printf(")");
}
void free_pair(Pair* p)
{
if (p!=NULL) {
free_atom(p->left);
free_atom(p->right);
free(p);
}
}
Atom* atom_toupper(Atom *a)
{
Atom *b;
/* your code here */
return b;
}
Atom* atom_square(Atom *a)
{
Atom *b;
b = copy_atom(a);
b->val = b->val * b->val;
return b;
}
List* map(List *lptr, Atom* (*f)(Atom *))
{
Atom *a;
List *l1, *l2;
if (lptr==NULL) return NULL;
else {
l1 = ??? /* 用遞迴的方式 利用 map 處理 list 剩下的部分 並且用 l1 指標 記住結果 */
a = ??? /* 把 lptr 開頭的 atom 代入 f 得到新的 atom */
l2 = ??? /* 接著再利用 cons 組合 處理過的頭跟尾 */
free_atom(a);
free_list(l1);
return l2;
}
Input
總共會有 2 個 list
第 1 個 list 會用來套用 atom_square 函數
第 2 個 list 會用來套用 atom_toupper 函數
第一行的數字代表第 1 個 list 有幾個元素
第二行是 list 中的每個元素內容，分別以空白隔開
最後兩行以相同格式紀錄第 2 個 list
Output
第一行輸出第 1 個 list 套用 atom_square 函數的結果
第二行輸出第 2 個 list 套用 atom_toupper 函數的結果
Sample Input Download
Sample Output Download
Tags
Discuss
Description
輸入不同面值的銅板，然後輸入一個金額，將全部可能的找零方式列出。
譬如有 3 種銅板面值分別是 1 元、5元、10元，假設要湊出 17 元，如果把找零方法表示成 "(1元個數,5元個數,10元個數)"，總共會有下列幾種方法
(2,1,1)
(2,3,0)
(7,0,1)
(7,2,0)
(12,1,0)
(17,0,0)
排列順序的規則: 例如 (7,0,1) 先於 (12,1,0) 因為 7 比 12 小；而 (7,0,1) 和 (7,2,0) 的順序，因為第一個數目7 和 7 相等，這時候就要比第二個數目，而由於 0 小於 2 所以 (7,0,1) 先於 (7,2,0)。
Input
第一個數字 N 代表有幾種不同面值的銅板 (N <= 5)
接下來就是 N 個整數，表示 N 種對應的銅板面值
最後一個數字是要需要找零的金額
Output
列出每一種找零方法，用括號框住每個銅板的數量，數量之間用逗號隔開，每一種找零方法後面要換行。
不同的找零方法的排列順序要依照題目的規定。
Sample Input Download
Sample Output Download
Tags
Discuss
Description
輸入一個 N x N 矩陣，輸出一個新的 (N-2) x (N-2) 矩陣，新的矩陣的每個元素，對應到原來的矩陣 每一個 3 x 3 區塊的範圍內的最大值，例如輸入的矩陣是
10 20 30 90 30
50 60 30 20 50
80 50 70 60 20
90 40 30 20 80
20 30 40 50 90
輸出的矩陣
80 90 90
90 70 80
90 70 90
以輸出矩陣的左上角的 80 為例 因為它是原來輸入的矩陣的左上角 3 x 3 區域內的最大值:
10 20 30
50 60 30
80 50 70
又例如輸出的矩陣的中間的 70，是原本輸入矩陣的正中央 3x3 區塊內的最大值:
60 30 20
50 70 60
40 30 20
Input
第一行是一個整數 N，然後接下來 N 行，每行包含 N 個整數，總共 N*N 個整數。
N 的值最小是 3，最大不超過 10。
Output
N-2 行，每一行包含 N-2 個整數，兩個元素之間有一個空白隔開，每一行最後都要換行。
Sample Input Download
Sample Output Download
Tags
Discuss
Description
輸入兩個向量，計算向量內積值。
兩個向量的內積，是各項相乘然後加總。例如 [1,2,3] 和 [4,5,6] 內積是 1*4+2*5+3*6 = 32
我們考慮高維度的稀疏向量，也就是大多數的元素都是零，只有少數不為零。資料的表示方式如下
dim1: value1 dim2: value2 dim3:value3 … 0:0
最後以 0:0 結束。例如
向量 [0,5,0,0,9,0,0,33] 是一個 8 維向量，可表示成
2:5 5:9 8:33 0:0
值為0 的維度都可以忽略不需描述，只需記錄非零的維度。利用上述的表示法，讀取兩個向量，然後算出它們的內積。
Input
輸入兩行，分別對應到兩個整數向量。
向量維度最高不超過 2 的 31 次方。記憶體用量不超過 32 MB。每一行都是以 0:0 結束
Output
內積值
最後記得換行
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Given two positive integers M and N, construct an M-row, N-column matrix that comprises a sequence of numbers from 1 to M*N arranged in clockwise spiral order. For example, if M = 3 and N = 4, the matrix would be
1 2 3 4
10 11 12 5
9 8 7 6
If M = 4 and N = 4, the matrix would be
1 2 3 4
12 13 14 5
11 16 15 6
10 9 8 7
Now, given a query integer P (1 <= P <= M*N), you need to print the position of P in the spiral matrix. For example, if M = 4, N = 4, and P = 14, the position of the integer 14 is at the position of row = 2 and column = 3, so the output is
2 3
Input
The input contains three positive integers M N P, where M denotes the number of rows and N denotes the number of columns of the spiral matrix. Both M and N are not greater than 30. P is the query number.
Output
Print two integers that denote the row and column of the position of P. The two integers are separated by a blank. Print a newline at the end of the output.