1134 - I2P CS 2016 Chen Winter Assignment Scoreboard

Time

2017/01/20 10:00:00 2017/02/28 23:59:00

Clarification

# Problem Asker Description Reply Replier Reply Time For all team
# Problem Pass Rate (passed user / total user)
1000 The A+B Problem
10034 moocHW1c
10035 moocHW1a
10036 moocHW1b
10062 moocHW2a
10063 moocHW2b
10064 moocHW2c
10094 moocHW3a
10095 moocHW3b
10096 moocHW3c
10115 moocHW4a
10116 moocHW4b
10167 moocHW5a
10172 moocHW5b
10173 moocHW5c
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

1000 - The A+B Problem   

Status  |  Limits Submit

Description

Given a,b, output a+b.

Input

a,b<=100000000.

Output

a+b

Sample Input  Download

Sample Output  Download

Tags

4 5 ddd 3 a #include <stdio.h> p klrscpp ? CCY rain orange



Discuss




10034 - moocHW1c   

Status  |  Limits Submit

Description

The input contains two floating numbers X and P.

Suppose that 0

The number P represents the precision, which only has four possible values in this problem: 1, 0.1, 0.01, and 0.001.

The task is to round off the number X with respect to the given precisoin P.

For example, if X is 0.4526 and P is 0.1, then the answer is 0.5000.

If X is 0.4526 and P is 0.01, then the answer is 0.4500. If X is 0.5678 and P is 1, then the answer is 1.0000.

 

[注意輸出的最後要換行]

Input

 Two floating point numbers X and P, where 0

Output

 The number after rounding off. The format should be the same as X: four digits after the decimal point.

Sample Input  Download

Sample Output  Download

Tags

dp



Discuss




10035 - moocHW1a   

Status  |  Limits Submit

Description

Suppose that we have an encoding scheme defined by the following mapping: 

1->'A', 2->'B', 3->'C', ..., 9->'I', 0->'J'.
Given a three-digit number N as the input, use the above mapping to encode N.
 
 
[注意輸出的最後要換行]

Input

A three-digit integer N

Output

The encoding result

Sample Input  Download

Sample Output  Download

Tags




Discuss




10036 - moocHW1b   

Status  |  Limits Submit

Description

Consider a conversion that modifies the digits of an integer N as follows: Check each digit of N. If the digit is odd, keep it unchanged. If the digit is even, divide it by 2. For example, if N is 1234, the answer is 1132; if N is 747, the answer is 727.

 

[hint]

8/2((8+1)%2)+8(8%2) = 4

7/2((7+1)%2)+7(7%2) = 7

[注意輸出的最後要換行]

Input

 An integer N, where 0<N<10000

Output

 The number after conversion

Sample Input  Download

Sample Output  Download

Tags




Discuss




10062 - moocHW2a   

Status  |  Limits Submit

Description

 輸入的字元只會有小寫英文字母和空格 ' ' 或換行，然後以 '#' 字元做為結束。例如:

    adefc xy z uvw mn o p rtv eee
    uk mof pq rwy #
將輸入的資料走過一遍，忽略所有空白，計算出最長的非遞減序列包含了多少個小寫英文字母。以上面的輸入資料為例，其中包含的每段非遞減序列分別是 adef cxyz uvw mnoprtv eeeu kmo fpqrwy，而其中最長的非遞減序列應該是 mnoprtv 這一段，包含了七個英文字母，因此程式的必須輸出 7。另外的例子像是 
aaaauuuu# 應該要輸出 8。 還有一種特殊情況是一開始就遇到 #，這時候要輸出 0。
 

Input

 如題目所描述，輸入的資料會包含小寫英文字母，其中可能穿插空格和換行，最後會以 '#' 結尾。

Output

 輸出一個整數值，代表最長的非遞減序列的長度，最後要加一個換行字元

Sample Input  Download

Sample Output  Download

Tags




Discuss




10063 - moocHW2b   

Status  |  Limits Submit

Description

 讀取一個整數 N    (0<N<50)，輸出一個 N-by-N    的矩陣，對角線上的值是 2，對角線兩旁是 -1，其餘位置則
都是 0。

例如 N    的值如果是 5，輸出結果會長得像下面這樣。

注意：包含最後一列在內，每一列結尾都有一個換行；此外每個數目佔了三個字元寬度，因此 2 的前面會有兩個空格，0 的前面也會有兩個空格，但是 -1的前面只有一個空格。

  2 -1  0  0  0
 -1  2 -1  0  0
  0 -1  2 -1  0
  0  0 -1  2 -1
  0  0  0 -1  2
 

Input

N    是一個整數，範圍是 0<N<50。

Output

 如題目所描述的 N-by-N 矩陣。注意換行和空格。

(Sample Output 因系統問題無法正確顯示，請以題目中敘述的格式為準 )

Sample Input  Download

Sample Output  Download

Tags

4



Discuss




10064 - moocHW2c   

Status  |  Limits Submit

Description

輸入一個整數 N    (10<N<10000000)，譬如 N 的值是 10413，把這個數字切成兩段有底下幾種切法，{1,0413}、{10,413}、{104,13}以及 {1041,3}，其中 {1,0413} 和 {104,13} 兩種切法，如果拿大數除以小數，可以除得盡，0413 除以 1 的商是 413 (前面第一個 0忽略)，104    除以 13 的商則是 8，你的程式要能求出其中最小的商，在這個例子就是 8。

假如不論哪一種切法，都沒有整除的情況發生，則輸出 0。
再舉一些例子，譬如 N的值是 3897433，答案是 9，因為 {3897,433}。譬如 N的值 3343674，答案是 11。
又譬如 N    的值是 100，則答案是 0。又譬如 N是 795則答案是 0。
要注意程式碼不要發生除以 0 的情況。

 

Input

一個整數 N，10<N<10000000。

Output

 如題目描述，將 N 分成兩段之後，大數除以小數能夠得到的最小的商。輸出的答案後面要加換行字元。

Sample Input  Download

Sample Output  Download

Tags




Discuss




10094 - moocHW3a   

Status  |  Limits Submit

Description

輸入分為兩部分。第一部分是一個經過了編碼後的加法數學等式，其中涉及的每個數字位數絕不會超過三位數，例如 ABC+CB=BDJ，表示是某個三位數 ABC加上某個二位數 CB 等於某個三位數 BDJ。編碼都是英文大寫字母，而且只會是 A, B, C, D, E, F, G, H, I, J 其中一部分。

接下來第二部分是編碼的對應數值，格式都會是一個英文大寫字母，搭配一個數字，最後是 # 結尾，例如 A 5 B 6 C 7 D 4 J 3 #，表示字母 A 對應到數值 5，字母 B 對應到數值 6，字母 C 對應到數值 7，字母 D 對應到數值 4，字母 J 對應到數值 3。其餘沒有對應的字母，預設值是 -1。

這個題目的任務很簡單，只要將輸入的資料讀進來並稍做處理，然後把他們顯示出來就行了。

可以使用我們提供的程式架構，也可以全部自己寫。如果要用我們提供的架構，要自己寫的部分只有兩個函數，

void read_equation(void);

void read_mapping(void);

在函數中直接修改下列全域陣列

char Num_Str1[10];

char Num_Str2[10];

char Num_Str3[10];

int Mapping[10];

以下為程式架構:

#include <stdio.h>
void read_equation(void);
void read_mapping(void);
char Num_Str1[10];
char Num_Str2[10];
char Num_Str3[10];
int Mapping[10];
int main()
{
    int i;
    for(i=0;i<10;i++){
        Mapping[i]=-1;
    }
    
    read_equation();
    read_mapping();
    
    
    
    for(i=0;i<4;i++){
        if(Num_Str1[i]=='\0'){
            printf(" ");
            break;}
        else printf("%c",Num_Str1[i]);
    }
    for(i=0;i<4;i++){
        if(Num_Str2[i]=='\0'){
            printf(" ");
            break;}
        else printf("%c",Num_Str2[i]);
    }
    for(i=0;i<4;i++){
      if(Num_Str3[i]=='\0'){
          printf("\n");
          break;}
        else printf("%c",Num_Str3[i]);
    }
    
    
    
    
    for(i=0;i<10;i++){
        printf("%3d",Mapping[i]);
    }
    printf("\n");
    
    
    


    return 0;
}
}

 

Input

如題目所描述，最後會以 '#' 結尾。

Output

總共要輸出兩行，注意兩行的結尾都要換行 (都要加 )。
第一行要顯示的東西，是讀進來的那三個經過編碼的數字，用空格分開。
第二行顯示的則是 A 到 J 對應的數值，如果沒有指定對應數值則預設值是 -1。注意，第二行的格式是 %3d，也就是說，如果是 0 到 9 的數字，前面會空兩個空格，如果是 -1 則前面只有一個空格。
 

Sample Input  Download

Sample Output  Download

Tags




Discuss




10095 - moocHW3b   

Status  |  Limits Submit

Description

延續第一題，但是要算出對應的數值，以便確認如果代入了對應數字之後，等式是否正確。譬如輸入是
EF+DE=GH
D 2
E 3
F 6
G 4
H 7
#
輸出應該是
36
23
47
Wrong
可以用提供的程式架構，也可以全部自己寫。使用提供的程式架構要自己寫出
void convert_all(void); 這個函數
程式架構如下：
#include <stdio.h>
#include <string.h>
#include <ctype.h>
char Num_Str1[10];
char Num_Str2[10];
char Num_Str3[10];
int Num1, Num2, Num3;
int Mapping[10];
 
void read_equation(void);
void read_mapping(void);
void convert_all(void);
void show(void);
 
int main(void)
{
    read_equation();
    read_mapping();
    convert_all();
    show();
 
    return 0;
}
 
void read_equation(void)
{
    char ch;
    int i1=0,i2=0,i3=0;
    while((ch=getchar())!='+'){
        Num_Str1[i1]=ch;
        i1++;
    }
    Num_Str1[i1]='\0';
    while((ch=getchar())!= '='){
        Num_Str2[i2]=ch;
        i2++;
    }
    Num_Str2[i2]='\0';
    while((ch=getchar())!= '\n'){
        Num_Str3[i3]=ch;
        i3++;
    }
    Num_Str3[i3]='\0';
}
 
void read_mapping(void)
{
    char inputc, ch, numc;
    int i;
    for(i=0;i<10; i++){Mapping[i]=-1;}
    while((inputc=getchar())!='#'){
        if(isupper(inputc)==1){ch=inputc;}
        if(isdigit(inputc)==1){numc=inputc;}
        Mapping[ch-65]=numc-48;
    }
}
 
void show(void)
{
    printf("%d\n", Num1);
    printf("%d\n", Num2);
    printf("%d\n", Num3);
    if (Num1+Num2 == Num3)
        printf("Right\n");
    else
        printf("Wrong\n");
}

 

Input

輸入格式和第一題完全相同。

Output

總共會有四行。前三行為讀進來的那三個經過編碼的字母所對應的數字，每個數字一行。最後一行輸出"Wrong"或"Right"表示等式是否正確。

Sample Input  Download

Sample Output  Download

Tags




Discuss




10096 - moocHW3c   

Status  |  Limits Submit

Description

延續第二題，假設輸入的對應關係，有可能會出錯的一定只會是前兩個對應。譬如輸入是
EF+DE=GH
D 2
E 3
F 6
G 4
H 7
#
我們知道代入編碼之後等式不會成立，而假設錯誤的對應，只可能是題目所提供的前兩個對應關係，在這個例子中就是 D和 E，重新嘗試之後，我們可以是出來 D 應該設為 3 而 E 應該設為 1，請將最後的對應關係印出來，以這個例子來說，要顯示
 -1 -1 -1  3  1  6  4  7 -1 -1
假設測試資料一定會有解，而且只有唯一解。
如果要使用我們提供的程式架構，要寫出 void try_try(void); 其中會利用到第二題的 convert_all()。
另外也要稍微修改 read_mapping()。
程式架構如下：

#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include <math.h>
char Num_Str1[10];
char Num_Str2[10];
char Num_Str3[10];
int Num1=0, Num2=0, Num3=0;
int Mapping[10];
/* Store the mapping of A at location 0;
Store the mapping of B at location 1; ...
Store the mapping of J at location 9
For example, if we have the following mapping:
A->5, B->6, C->7, D->4, E->3, F->0, G->2, H->1, I->9, J->8
the elements of Mapping[] will be
{5, 6, 7, 4, 3, 0, 2, 1, 9, 8}
*/
int First_Map, Second_Map, num_map=1;

void read_equation(void);
void read_mapping(void);
void convert_all(void);

void try_try(void);

void show(void);

int main(void)
{
    //freopen("input", "r",stdin);
    read_equation();
    read_mapping();
    try_try();
    show();

    return 0;
}
void read_equation(void)
{
    char cur_ch, str[10];
    int i, len=0;
    while(cur_ch=getchar()){
        if(cur_ch=='+'){
            for(i=0; i<len; i++){
                Num_Str1[i] = str[i];
            }
            Num_Str1[i] = '\0'; len=0;
        }
        else if(cur_ch=='='){
             for(i=0; i<len; i++){
                Num_Str2[i] = str[i];
            }
            Num_Str2[i] = '\0'; len=0;
        }
        else if(cur_ch=='\n'){
            for(i=0; i<len; i++){
                Num_Str3[i] = str[i];
            }
            Num_Str3[i] = '\0'; len=0;
            break;
        }
        else{
            str[len] = cur_ch;
            len++;
        }
    }
}
void read_mapping(void)
{
    // Hint: refer to HW3b and modify by yourself
}

/*
Convert the encrypted numbers into the corresponding values (decimal numbers).
Store the results in the global variables Num1, Num2, Num3.
For example, if the elements of Mapping[] are
  5  6  7  4 -1 -1 -1 -1 -1  3
and the elements of the three character arrays are
Num_Str1: 'A','B','C','\0'
Num_Str2: 'C','B','\0'
Num_Str3: 'B','D','J','\0'
then, the results of Num1, Num2, and Num3 should be 567, 76, and 643.
*/
void convert_all(void)
{
    /*
    Hint:
    Check the characters stored in Num_Str1.
    Use Mapping[] to find the corresponding values and store the results
    in Num1, Num2, and Num3.
    */
}

/*
Show
 */
void show(void)
{
    int i;
    for (i=0; i<10; i++) {
        printf("%3d", Mapping[i]);
    }
    printf("\n");
}

 

Input

輸入格式和第一題完全相同。

Output

總共要輸出一行，結尾要換行。顯示的則是 A 到 J 對應的數值，如果沒有指定對應數值則預設值是 -1。注意，輸出格式是 %3d，也就是說，如果是 0 到 9 的數字，前面會空兩個空格，如果是 -1 則前面只有一個空格。

Sample Input  Download

Sample Output  Download

Tags




Discuss




10115 - moocHW4a   

Status  |  Limits Submit

Description

假設只能使用兩種符號來組成字串，譬如 IOIOI 或 OOII，都是由 I 和 O 組成，長度分別是 5 和 4。如果給定一個這樣的字串，同時又告訴你其中只有N個符號是正確的，能否把全部可能的答案都產生出來？例如輸入的字串是 TTTFF，然後又跟你說其中只對了 4 個符號，則可能的答案應該會有下面五種：
TTTFT
TTTTF
TTFFF
TFTFF
FTTFF
再舉一個例子，如果輸入的字串是 OXOX，而其中只有 2 個符號是對的，則可能的答案會有底下六種：
OXXO
OOOO
OOXX
XXOO
XXXX
XOOX
答案要依照一定順序列出。決定順序的規則如下：盡量讓靠右邊的符號先變，盡量讓靠左邊的符號維持不變。以上面的輸入字串 OXOX (2個符號正確)為例，答案 OXXO 會排 OOOO 前面，因為 OXXO 和原本的輸入字串 OXOX 的最左兩個符號是相同的，但是 OOOO 和原本的輸入字串 OXOX 則是左邊第二個符號就不相同，所以 OXXO 的順位高於 OOOO。同理可以去檢驗其他順序，例如答案OOXX 順位高於 XXOO，因為OOXX 最左邊的符號和原輸入 OXOX 相同，但 XXOO 最左邊的符號就已經和 OXOX 不同。
再看一個範例：假設構成的符號有P 和 Q，輸入的字串是PPP，只對 1 個符號，則答案是
PQQ
QPQ
QQP
註:這一題可以自己寫，也可以直接改程式框架，寫出 void check_bits(int cur_bit, int num_hits)。
 

Hint:

#include <stdio.h>
#include <string.h>
#define MAXBITS 16

char bits[3];
char input[MAXBITS+1];
char answer[MAXBITS+1];
int NBITS;

void check_bits(int cur_bit, int num_hits);
char flip(char ch);

int main(void)
{
    int nhits;

    /* Read the two symbols for the binary bits,
    e.g, OI, 01, OX, or -+, etc. */
    scanf("%2s", bits);

    /* Read the input bit string. */
    scanf("%s", input);
    NBITS = strlen(input);

    /* The answers will be stored in the array answer[] */
    answer[NBITS] = '\0';

    /* Read the number of correct bits */
    scanf("%d", &nhits);

    /* Call the recursive function check_bits
    Start from the leftmost bit. */
    check_bits(0, nhits);

    return 0;
}

/*
1.
The value of cur_bit keeps increasing as we
recursively call check_bits().
2.
If input[cur_bit] is correct, the value of num_hits
should decrease; otherwise we should keep num_hits unchanged
and check the next bit.
3.
Copy the bit from input[cur_bit] or flip the bit,
and store the result in the array answer[].
4.
If the recursive call reaches the end of the input,
it is done and we may print the answer using
    printf("%s
", answer);
*/
void check_bits(int cur_bit, int num_hits)
{
    /* YOUR CODE */

}

/*
Flip the bit. For example,
0 <--> 1
O <--> I
...
*/
char flip(char ch)
{
    return ( (ch==bits[0]) ? bits[1] : bits[0] );
}

Input

輸入資料會有三行。
第一行是兩個相連的字元，用來指出構成字串的符號是哪兩個。 (例如 "OI")
第二行是輸入的字串，假設字串長度最多不超過 16 個字元。 (例如 "IIOOIIOO")
第三行是正確的符號個數，假設正確的個數一定大於 0，且小於等於字串長度。

Output

每一行顯示一種可能的答案，結尾都要換行 (都要加 )。要注意輸出的答案的順序。列出的順序如果沒有按照題目規定，Online Judge 會判定為錯誤。

Sample Input  Download

Sample Output  Download

Tags




Discuss




10116 - moocHW4b   

Status  |  Limits Submit

Description

假設有 N 個不同密度、不同顏色的液體，密度由大至小，由低到高，疊在一個試管裡 (試管編號 0) ，形成顏色區隔明顯的層次。假設我們想將液體倒入另一個試管 (編號 1)，倒的時候只能倒出最上層的液體，而且過程中只允許將密度小的液體倒在密度大的液體上方。假如還有多一個試管 (編號 2) 作為過渡的容器，請問依照規則將全部液體從試管 0 移到試管 1，並且保持原有的顏色順序？
假設輸入是一個字串 RGB，代表最底層的液體是 R，中間是 G，上層是 B，則傾倒的方式為
B:0->1
G:0->2
B:1->2
R:0->1
B:2->0
G:2->1
B:0->1
也就是先將 B 從試管 0 倒入試管 1，再將 G 從試管 0 倒入試管 2，然後將 B 從試管 1 倒入試管 2，依此繼續下去，最後試管 1 內就會從低到高依序是 RGB 的排列。
 

Input

一個字串，長度不超過 8，其中包含的字元都不相同。

Output

列出完整的步驟，每個步驟一行，每一行結尾要有換行字元 '\n'。
每個步驟的描述格式，開頭是一個字元，表示被倒出的液體種類，再來是冒號 :，接下來是原本的試管編號，然後顯示->，最後是將要倒入的試管編號。
 

Sample Input  Download

Sample Output  Download

Tags

LOL use DP hanoi



Discuss




10167 - moocHW5a   

Status  |  Limits Submit

Description

以範例程式為基礎
再加上自己寫的程式碼完成任務
先來看需要哪些陣列和函數

#include 
#define MAP_SIZE 11
#define EXIT_ROW 5
#define EXIT_COL 10
#define NUM_CARS 10
#define WALL '#'
#define SPACE '.'
#define EXIT '='

/* #define ONLINE_JUDGE */

int map[MAP_SIZE][MAP_SIZE];
void map_reset(void);
void map_show(void);
int cars[NUM_CARS][4];
void cars_read(void);
void cars_put_on_map(void);

void list_moves(void);

map 是一個二維陣列
用來表示地圖的內容
map_reset() 的作用是清除地圖內容並且設定邊界和出口
map_show() 則是把 map 的內容顯示到螢幕上


cars 二維陣列記錄全部車子的座標
陣列的大小是 NUM_CARS 乘 4
用四個數字分別記錄每一輛車子的左上和右下位置
譬如 cars[5][0], cars[5][1], cars[5][2], car[5][3] 的值如果分別是 8, 6, 8, 9
代表車子目前水平佔據了地圖 (8, 6) 到 (8, 9) 的位置
也就是在 row 8上從 column 6 到 column 9 總共四個格子
最小的車子的大小是兩格
也就是至少會佔水平或垂直兩格

先將地圖用 map_reset() 清空
再用 cars_read() 和 cars_put_on_map() 讀入車子的座標並放上 map
然後用 map_show() 顯示出來
就會看到底下的狀態  (符號 f 的那輛車就是上面舉例的編號 5 的車子)
###########
#........g#
#..b.....g#
#..bcccc.g#
#..b...ijg#
#aabd..ijh=
#...d..ijh#
#...d..i.h#
#...d.ffff#
#eeeee....#
###########


需要自行完成的函數是
list_moves()
這個函數的功能是按照順序列出每一輛車子
朝向 右、下、左、上  四個方向分別能夠移動的距離
要注意車子子能前後開、不能側移 (水平的車只能水平移動、垂直的車只能垂直移動)
譬如編號 5 的車子 (符號 f) 可移動距離是 0 0 1 0
表示 向右不能動、向下不能動、向左能動 1 格、向上不能動

移動時如果碰到出口
直接將出口當作牆壁就行了
不要算入可移動距離內

關於輸出格式

在自己電腦上測試的階段
資料讀取來源是 cars.txt
地圖狀態會顯示在螢幕上
但是資料輸出則是在 output.txt
範例程式產生的 output.txt 內容都是 0
如果 list_moves() 寫對了
產生的 output.txt 內容應該要和 sample_output.txt 完全一樣
可以先自行比對看看
程式寫完之後

上傳至 Online Judge 前
記得要將/* #define ONLINE_JUDGE */ 的註解符號移除 (拿掉 /* 和 */)
讓它變成 

#define ONLINE_JUDGE

這樣就不會從 cars.txt 讀取資料
而是從 OJ 自訂的 standard input 讀取測資
並且不會在螢幕上畫出地圖內容
輸出資料也不會寫到 output.txt
而是寫到 OJ 自訂的 standard output
如此才能符合 OJ 需要判讀的輸出格式

 

Input

總共有 10 行
分別代表編號 0 到 編號 9 總共十輛車子的座標
用四個數字表示
四個數字的順序分別是是 左上角的 row column 和 右下角的 row column
每輛車子至少會佔兩格
 

Output

輸出格式也是 10 行
每一行都是用換行字元結尾
每一行會有四個數字
分別代表每輛車子朝四個方向能夠移動的距離
四個方向的順序是 右、下、左、上

要把出口當作牆壁看待
不要計入可移動距離
 

Sample Input  Download

Sample Output  Download

Tags




Discuss




10172 - moocHW5b   

Status  |  Limits Submit

Description

程式碼中包含了五十個英文單字，儲存在 char dictionary[N_WORDS][30];
N_WORDS 是字典中總共的英文單字數目, 也就是50
每一個 dictionary[i] 相當於一個字串
譬如 printf(“%s ”, dictionary[2]);
螢幕上應該會顯示出an
這次作業要完成的是範例程式當中的void complete(char *input_str);
傳入一個使用者輸入的字串 (假設只會包含小寫字母)
這個字串是某個英文單字的開頭部分
complete 這個函數要透過查字典的方式，將所有開頭符合輸入字串的英文單字都列出
在比對字串的時候，要把字典中的大寫字母都轉成小寫來比對
你的程式碼應該會需要用到 strncmp 以及 tolower 這兩個函數
請自行查詢這兩個函數的用法https://www.gnu.org/software/libc/manual/html_mono/libc.html
其中 strncmp 這個函數能傳入兩個指標參數，分別指向兩個字串，然後比對兩個字串前 n 個字元的相似度
如果兩個字串的前 n 個字元都相同，strncmp傳回的值會是 0
而 tolower 則可以把英文字母轉成小寫
 

注意事項：
1.將字典中的字，轉成小寫存入 lower[] 陣列中。用字元陣列儲存字串，字串的結尾記得要放 ‘\0’。
2.上傳至 OJ 之前，記得要將/* #define ONLINE_JUDGE */ 的註解符號移除 (拿掉 /* 和 */)
讓它變成 #define ONLINE_JUDGE
 

Input

N個搜尋字串

Output

查詢出的字串

Sample Input  Download

Sample Output  Download

Tags

dictionary.h:No such file or directory ideone.com/kKghbz



Discuss




10173 - moocHW5c   

Status  |  Limits Submit

Description

程式碼中包含了六十個英文單字，儲存在 char dictionary[N_WORDS][30];
N_WORDS 是字典中總共的英文單字數目, 也就是60
每一個 dictionary[i] 相當於一個字串
譬如 printf(“%s\n”, dictionary[2]);
螢幕上應該會顯示出an
這個作業題目要完成的是範例程式當中的三個函數
void count_letters(char *input_str, int *counts);
int equal_counts(int *counts1, int *counts2);
void find_words(char *input);
在 main 會呼叫 find_words
將使用者輸入的字串傳入 (假設只會包含小寫字母)
這個字串是某個英文單字的字母重新排列
find_words這個函數要透過查字典的方式，將所有經過適當排列之後能符合輸入字串的英文單字都列出
在比對字串的時候，要把字典中的大寫字母都轉成小寫來比對
你的程式碼應該會需要用到 tolower 函數
請自行查詢函數的用法https://www.gnu.org/software/libc/manual/html_mono/libc.html
find_words函數中會呼叫 count_letters 和 equal_counts
count_letters 的作用是計算某個單字中 ‘a’ 到 ‘z’ 每個小寫字母出現的次數
將 ‘a’ 出現的次數儲存在 counts[0]， ‘b’ 出現的次數儲存在 counts[1]，依此類推
equal_count 函數則是用來比較兩個單字中，每個字母的出現次數是否完全相同。

注意事項：
1.將字典中的字，轉成小寫存入 lower[] 陣列中。用字元陣列儲存字串，字串的結尾記得要放 ‘\0’。
2.上傳至 OJ 之前，記得要將/* #define ONLINE_JUDGE */ 的註解符號移除 (拿掉 /* 和 */)
讓它變成 #define ONLINE_JUDGE

Input

N個搜尋字串

Output

查詢出的字串

Sample Input  Download

Sample Output  Download

Tags

she Neo,one ate,eat,tea None. None EOF



Discuss




10193 - moocHW6a   

Status  |  Limits Submit

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




10194 - moocHW6b   

Status  |  Limits Submit

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




10195 - moocHW6c   

Status  |  Limits Submit

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




10221 - moocHW7a   

Status  |  Limits Submit

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

sort



Discuss




10222 - moocHW7b   

Status  |  Limits Submit

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

sort 韩永楷老师数据结构mooc



Discuss




10223 - moocHW7c   

Status  |  Limits Submit

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




10241 - moocFinal1_換銅板   

Status  |  Limits Submit

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




10242 - moocFinal2_M 皇后 N 城堡   

Status  |  Limits Submit

Description

在一個(M+N) x (M+N) 的棋盤上放M個皇后 N 個城堡，皇后可走直走斜，城堡只能走直，所有的棋子互相不能吃掉對方。
輸出有幾種合法的放法。

Input

相加不大於10的正整數M 和 N，表示在(M+N) x (M+N) 的棋盤上放置M個皇后 N 個城堡。

Output

總共有多少種安全的放法，記得換行

Sample Input  Download

Sample Output  Download

Tags




Discuss




10243 - moocFinal3_Max Pooling   

Status  |  Limits Submit

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




10244 - moocFinal4_高維度稀疏向量   

Status  |  Limits Submit

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




10245 - Spiral Matrix   

Status  |  Limits Submit

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.

Sample Input  Download

Sample Output  Download

Tags




Discuss