Problem 879 Circuit Nets，電絡網

同 793 Network Connections，在此不贅述。

By David.K

p879題目連結
回ACM題庫目錄
回首頁

Problem 793 Network Connections，網絡連接

此題使用 Dijkstra 演算法即可解決。

Dijkstra 演算法可以參考：http://zh.wikipedia.org/wiki/%E8%BF%AA%E7%A7%91%E6%96%AF%E5%BD%BB%E7%AE%97%E6%B3%95

By David.K

p793題目連結
回ACM題庫目錄
回首頁

Problem 10116 Robot Motion 機器人運動

這題其實也只要多建立一個相同大小的陣列紀錄步數以及重複步數值就可以了。

#define row 12
#define col 12

int step, r, c;

char motion[row][col];
int record[row][col];

void move(int x, int y)
{
   int i, j;
    record[x][y] = step ++;
    
    switch (motion[x][y])
 {
        case 'N':
            x --;
            break;
        case 'E':
            y ++;
            break;
        case 'W':
            y --;
            break;
        case 'S':
            x ++;
            break;
    }
    
    if (x < 0 || x >= r || y < 0 || y >= c)
    {
        printf("%d step(s) to exit\n", step - 1);
        return;
 }   
    if (record[x][y] != -1 )
    {
        int k = step - record[x][y];
     printf("%d step(s) before a loop of %d step(s)\n", step - k - 1, k);
  return;  
 }
 move(x, y);
 
}

最後在主程式內傳入開始的 x, y 座標即可。

By David.K

p10116題目連結
回ACM題庫目錄
回首頁

Problem 12019 Doom's Day Algorithm

先對 Doom's Day 做解釋。

這個神奇的方法就叫做 "Doomsday Algorithm"，詳細的原理就是… 每一年的二月的最後一天 (2/28 或 2/29)，和 4/4、6/6、8/8、10/10、12/12，和 9/5、5/9、7/11、11/7 (記憶口訣是 "我在 7-11 的工作時間是朝 9 晚 5″)，和 3/7 (二月最後一天的一星期後)，和 1/3 (西元年不可被 4 整除) 或 1/4 (可以被 4 整除)，這些日子的星期都是一樣的，這一天叫做 Doomsday，而上面這些日子就是一年中每個月的基準日，只要配合簡單的餘數運算就可以求出今年其他日子是星期幾啦。

但是如果要算其他年份，例如說去年的 Doomsday，怎麼辦呢 ? 因為 365 除以 7 會餘 1，也就是說每一個平常年 Doomsday 會跳一天，而閏年則會跳兩天；這樣一天，其他年份的 Doomsday 也就可以求出來，所以上面的算法也可以引申到其他年份啦。對於 19XX 年來說還有另一個速算法：先記住 1900 年的 Doomsday 是星期三；然後把 XX/12 的商和餘數，以及餘數除以 4 所得的商數，把這三個數字加起來以後，再除以 7，所得的餘數就是該年份 Doomsday 和星期三的相差數了。例如說 1937 年，XX = 37，37 / 12 商是 3 餘數是 1，1 /4 的商是 0，3 + 1 + 0 = 4，星期三再加 4 天就是星期天，也就是說 1937 年的 Doomsday 是星期天。

可是上面只有對 19xx 年有效啊，能推廣到其他的世紀去嗎 ? 其實是可以的，只要知道了該世紀的基準日就可以算了。經由觀察可以得知各世紀的 Doomsday 是以 "五三二日" 的循環在輪替，也就是說 1900 年是星期三，則 1800 年就是前一個，也就是星期五，而 2000 年就是星期二了。這就是世紀基準日的速記法。有了該世紀的基準日的話，就可以套用上一段所說的算法來計算該世紀任一天的星期了。

不過說實在的，上面這些步驟也確實太麻煩啦 !! 所以下面就有人發明了速算法：一樣是要先知道每個月的 Doomsday 基準日是那一天，然後算出你要求的日期和基準日差幾天，再把上面講的年份的那三個數字加起來，就加上該世紀 Doomsday 的星期，就是所求的那天是星期幾了。舉例來說，1937/7/7 (七七事變) 是星期幾呢 ? 先前提過，7/11 是 Doomsday，所以 7/7 就是 -4 的差距；37/12=3…1，1/4=0，-4 + 3 + 1 + 0 = 0；而 1900 年的 Doomsday 是星期三，再加上 0 天的差距，就是告訴我們 1937/7/7 是星期三。

以上引用自 http://blog.ijliao.info/archives/2004/04/07/321/

因為我們已經知道年份為 2011，而 2011 年 Doomsday 為星期一，其實也只要用一個陣列來加加減減就好了

char week[7][10] = {"Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday", "Sunday"};
int month[13] = {-1 ,3, 28, 7, 4, 9, 6, 11, 8, 5, 10, 7, 12};

int find(int m, int d)
{
    int index = (d - month[m]) % 7;
    index = index % 7 < 0 ? index + 7: index;
    printf("%s\n", week[index]);
}

讀入月份和日期，呼叫 find(m, d) 即可。
By David.K

p12019題目連結
回ACM題庫目錄
回首頁

Problem 11244 Counting Stars，星星 ? 物體 ?

此題利用深度優先搜尋法即可解決問題。重點 C 語言程式碼如下：

struct map
{
    char line[104];
}data[104];


void findStar(int i, int j)
{
    isOne ++;
    data[i].line[j] = '.';
    
    if (i - 1 >= 0 && j - 1 >= 0 && data[i - 1].line[j - 1] == '*')
       findStar(i - 1, j - 1);
    if (j - 1 >= 0 && data[i].line[j - 1] == '*')
       findStar(i, j - 1);
    if (i + 1 < r && j - 1 >= 0 && data[i + 1].line[j - 1] == '*')
       findStar(i + 1, j - 1);
       
    if (i - 1 >= 0 && data[i - 1].line[j] == '*')
       findStar(i - 1, j);
    if (i + 1 < r && data[i + 1].line[j] == '*')
       findStar(i + 1, j);    
       
    if (i - 1 >= 0 && j + 1 < c && data[i - 1].line[j + 1] == '*')
       findStar(i - 1, j + 1);    
    if (j + 1 < c && data[i].line[j + 1] == '*')
       findStar(i, j + 1);    
    if (i + 1 < r && j + 1 < c && data[i + 1].line[j + 1] == '*')
       findStar(i + 1, j + 1);
}

而主程式內需如此呼叫：

for (i = 0; i < r; i ++)
{
    for (j = 0; j < c; j ++)
    {
        isOne = 0;
        if (data[i].line[j] == '*') findStar(i, j);
        if (isOne == 1) count ++;
    }
}

打完收假。
By David.K

p11244題目連結
回ACM題庫目錄
回首頁

Problem 10852 Less Prime，最小質數

此題先建立質數表 prime_table[] 後，利用以下 C 語言程式碼判斷即可：

j = 0;
while(prime_table[++ j] * 2 <= n);

p10852 問題連結 ACM 題庫目錄 回到首頁

Problem 10579 Fibonacci Numbers，超大費氏級數

此題需要利用大數相加即可， line 為 1001，len 由各位去拿捏這尺寸需要多少才夠，記得要宣告 int fn[line][len];。
重點 C 語言程式碼如下：

void createFn()
{
    int i, j, k;
    fn[0][0] = 0;
    fn[1][0] = 1;
    for(i = 2 ; i < line ; i ++)
    {
        for(j = 0 ; j < len ; j ++)
        {
            fn[i][j] += fn[i - 1][j] + fn[i - 2][j];
            if(fn[i][j] > 9)
            {
                fn[i][j + 1] += fn[i][j] / 10;
                fn[i][j] %= 10;
            }
        }
    }
}

By David.K

p10579題目連結
回ACM題庫目錄
回首頁

Problem 11805 Bafana Bafana，傳球

輸入 N K P 三整數，代表有球員 1 - N，而球員圍成一圈，球員 2 在球員 1 的右邊，球員 3 在球員 2 的右邊，...以此類推。從球員 K 發球，每次傳球只往右邊一個球員傳，傳 P 次。問你最後球會在哪一個球員腳上。

此題讀入三整數後，利用以下 C 語言程式碼即可解：

j = (K + P) % N;
if (j == 0) j = N;

By David.K

p11805題目連結
回ACM題庫目錄
回首頁

Problem 10405 Longest Common Subsequence，最長共同子字串

建議大家可以上網去找「最長共同子字串」的演算法，此演算法是由「最長連續共同子字串」推演而來。「最長共同子字串」的方法就是依序比對字串，將最佳比對結果逐一往陣列右下方推，推到最後，答案就出來了。
C 語言程式碼如下：

#define LEN 1000

char seq1[LEN + 1], seq2[LEN + 1];

int lcs_length(int s1Len, int s2Len) 
{
    int i, j;
    int table[s1Len + 1][s2Len + 1];
    memset(table, 0, sizeof(table));
 
    for(i = 1; i <= s1Len; ++i) {
        for(j = 1; j <= s2Len; ++j) {
            if(seq1[i - 1] == seq2[j - 1])
                table[i][j] = table[i - 1][j - 1] + 1;
            else if(table[i - 1][j] > table[i][j - 1])
                table[i][j] = table[i - 1][j];
            else
                table[i][j] = table[i][j - 1];
        }
   }
   return table[s1Len][s2Len];
}

int main()
{
    
    while (gets(seq1))
    {
        gets(seq2);  
        int s1Len = strlen(seq1), s2Len = strlen(seq2);
        printf("%d\n", lcs_length(s1Len, s2Len));
    }
    
    return 0;
}

By David.K

p10405題目連結
回ACM題庫目錄
回首頁

Problem 10409 Die Game，骰子遊戲

首先宣告一結構，紀錄骰子上下東西南北所屬數字為何：

struct Dice
{
    int up, down, north, east, south, west;
};
struct Dice d;

主程式內，讀入翻動次數 n 次後，先初始化骰子數字各在哪些方位：

d.up = 1, d.down = 6, d.north = 2,
d.east = 4, d.south = 5, d.west = 3;

最後只要依照相對面的骰子總和為 7 以及空間概念，就可寫出來：

while (n --)
{
    scanf("%s", str);  
    if (str[0] == 's') /* 南 */
        d.south = d.up, d.up = d.north, 
        d.down = 7 - d.up, d.north = 7 - d.south;
    if (str[0] == 'n') /* 北 */
        d.down = d.north, d.north = d.up,
        d.up = 7 - d.down, d.south = 7 - d.north;
    if (str[0] == 'w')
        d.down = d.west, d.west = d.up,
        d.up = 7 - d.down, d.east = 7 - d.west;
    if (str[0] == 'e')
        d.east = d.up, d.up = d.west,
        d.down = 7 - d.up, d.west = 7 - d.east;
}
printf("%d\n", d.up);

By David.K

p10409題目連結
回ACM題庫目錄
回首頁

Problem 10452 Marcus

給你一陣列，要你求出從字元 '@'( 一定在最後一排 )到字元 '#'( 一定在第一排 )，按照字串 "IEHOVA" 走法，列出怎麼走才會走的到字元 '#' 的走法。

所以先寫好一字串，讓它走一步可以比對索引字元，若不對，則不走；若走到，則印出。用一遞迴函式實現，i, j 為目前位置，index 為目前字串索引：

#define SIZE 8
#define LEN 7
int n, row, col, sI, sJ, eI, eJ;

char letters[LEN + 1] = {'@', 'I', 'E', 'H', 'O', 'V', 'A', '#'};
char path[LEN];
char stone[SIZE][SIZE + 1];
void visit(int i, int j, int index)
{
    if (letters[index] != stone[i][j]) return;
    if (i == eI && j == eJ)
    {
        int k;
        
        if (path[0] == 'r') printf("right");
        else if (path[0] == 'l') printf("left");
        else if (path[0] == 'f') printf("forth");
        
        for (k = 1; k < LEN; k ++)
        {
            if (path[k] == 'r') printf(" right");
            else if (path[k] == 'l') printf(" left");
            else if (path[k] == 'f') printf(" forth");
        }
        printf("\n");
    }
    /* 左 */
    if (j - 1 >= 0) path[index] = 'l', visit(i, j - 1, index + 1);
    /* 右 */
    if (j + 1 < col) path[index] = 'r', visit(i, j + 1, index + 1);
    /* 前 */
    if (i - 1 >= 0) path[index] = 'f', visit(i - 1, j, index + 1);
}

最後，在主程式如此呼叫：

scanf("%d %d", &row, &col);  
for (i = 0; i < row; i ++)
{
    scanf("%s", stone[i]);
    if (i == 0)
    { 
        for (j = 0; j < col; j ++)
            if (stone[i][j] == '#') eI = i, eJ = j;
    }
    if (i == row - 1)
    {
        for (j = 0; j < col; j ++)
            if (stone[i][j] == '@') sI = i, sJ = j;
    }
}
visit(sI, sJ, 0);

By David.K

p10452題目連結
回ACM題庫目錄
回首頁

Problem 10494 If We Were a Child Again，小學數學

此題要算出他給你的運算式。用 scanf("%s %s %lld", m, ch, &n) 讀入，第一個數可能會很大，所以利用字串讀入，讀入之後，利用我們平常小學算數的方法，將被除數一個一個從大位數到小位數的讀入，再用 n 去除或取餘數，除法就每次除每次印；餘數就最後在印就好了：

first = 1;  
if (ch[0] == '/')
{
    tmp = 0;
    for (i = 0; (c = m[i]); i ++)
    {
        tmp *= b;
        tmp += c - '0';
        j = tmp / n;
        if (j != 0) first = 0;
        if (!first) printf("%lld", j);
        tmp %= n;
    }
    if (first) printf("0");
    printf("\n");
}
if (ch[0] == '%')
{
    for (i = 0, tmp = 0; (c = m[i]); i ++)
    {
        tmp *= b;
        tmp += c - '0';
        tmp %= n;
    }
    printf("%lld\n", tmp);
}

By David.K

p10494題目連結
回ACM題庫目錄
回首頁

Problem 10497 Sweet Child Makes Trouble，麻煩的小孩

通常可愛的小孩會製造一些麻煩，例如說拿別人的東西總是不會歸回原位放好，如果拿了 3 個人的東西，而不歸回原位放好的擺法有 2 個，2 3 1 和 3 1 2。所以給你一個 n 值就是小孩拿了 n 樣東西，要你求出不歸回原位的擺法有幾種。

此處要用到大數概念，最長位數有 1976 位這麼長，所以處理起來頗為耗時，不過也只需處理一次並且記錄在字元陣列內，最後用 puts() 印出即可：

#define SIZE 800
#define LEN 2000
int p[SIZE + 1][LEN + 1] = {0};
char output[SIZE + 1][LEN + 1];
void create()
{
    int i; 
    p[0][0] = 1;
    p[1][0] = 0;
    output[0][0] = '1';
    output[0][1] = '\0';
    output[1][0] = '0';
    output[1][1] = '\0';
    int j, k, s, count = 0;
    for (i = 2; i <= SIZE; i ++)
    {
        for (j = 0; j <= LEN; j ++)
        {
            p[i][j] += (p[i - 1][j] + p[i - 2][j]) * (i - 1);
            p[i][j + 1] += p[i][j] / 10, p[i][j] %= 10;
        }
        
        for (j = LEN; j >= 0; j --)
            if (p[i][j] > 0) break;
        for (k = j, s = 0; k >= 0; k --, s ++)
            output[i][s] = p[i][k] + '0';
        output[i][s] = '\0'; 
    }
}

int main()
{
    int n;
    create();
    while (scanf("%d", &n) == 1 && n != -1)
        puts(output[n]);
    return 0;
}

By David.K

p10497題目連結
回ACM題庫目錄
回首頁

Problem 10432 Polygon Inside A Circle

給你圓的半徑 r 與內接 n 邊形的邊數量，要你求出 n 邊形面積多少。以上為 n = 8 的表示方式。
推導公式，要求橘色邊和綠色邊方能求出 n 邊形之一塊三角形面積，所以 θ 角要先求出，2 * PI 為一個圓周率，所以 θ = 2 * PI / n。
所以，取 θ 角的一半，橘色邊為 r * cos(PI / n)，
綠色邊為 2 * r * sin(PI / n)，
面積為 r * cos(PI / n) * 2 * r * sin(PI / n) / 2，
約分後為 r * r * cos(PI / n) * sin(PI / n) = r * r * sin(2 * PI / n) / 2。
(依照公式 sin2θ = 2sinθcosθ)
而有 n 塊三角形所以 n 邊形總面積為 n * r * r * sin(2 * PI / n) / 2。

By David.K

p10432題目連結
回ACM題庫目錄
回首頁

Problem 10491 Cows and Cars，牛與車

此題為機率題，找出其中公式就可解此題。舉幾個例子：

牛數量	車數量	開門數	門總數
2	1	1	3

以上資料來看，
先選牛的機率 2 / 3，換選車機率 1 / 1 (因為會開一個門是牛的門，規定又說一定要換門)，所以機率 2 / 3 * 1 = 2 / 3。
先選車機率 1 / 3，換選車機率 0 / 1 (一開始選車，再開一個是牛的門，規定一定要換門)，所以機率 1 / 3 * 0 = 0。
一定要換門的機率為 2 / 3 + 0 = 2 / 3。

牛數量	車數量	開門數	門總數
5	3	2	8

先選牛的機率 5 / 8，換選車機率 3 / 5，所以機率 5 / 8 * 3 / 5 = 15 / 40。
先選車機率 3 / 8，換選車機率 2 / 5 ，所以機率 3 / 8 * 2 / 5 = 6 / 40。
一定要換門的機率為 15 / 40 + 6 / 40 = 21 / 40。
最後推導公式：

牛數量	車數量	開門數	門總數
NCOWS	NCARS	NSHOW	DOORS (= NCOWS + NCARS)

先選牛的機率 NCOWS / DOORS，換選車機率 NCARS / (DOORS - NSHOW - 1)，所以機率 NCOWS * NCARS / (DOORS * (DOORS - NSHOW - 1))。
先選車機率 NCARS / DOORS，換選車機率 (NCARS - 1) / (DOORS - NSHOW - 1)，所以機率 NCARS * (NCARS - 1) / (DOORS * (DOORS - NSHOW - 1))。
一定要換門的機率為 (NCOWS + NCARS - 1) * NCARS / (DOORS * (DOORS - NSHOW - 1))。

By David.K

p10491題目連結
回ACM題庫目錄
回首頁

Problem 10551 Basic Remains，進位餘數

此題給你三個數，一是進位制，二是被除數，三是除數。要你求出在此進位制的餘數為何。

首先將於除轉為 10 進制，讀入數值後，用一函式轉換：

#define SIZE 1000
char p[SIZE + 1], m[10], print[SIZE + 1];
int b, r;

int get10Basic()
{
    int n = 0, i;
    int len = strlen(m);
    for (i = 0; i < len; i ++)
        n = n * b + (m[i] - '0');
    return n;
}

主程式內 ....
scanf("%s %s", p, m);
int len = strlen(p);
int i;
r = get10Basic();

最後只需將被除數從大到小一個一個讀入，每次讀入都要乘上進位制，再去和 r 取餘數，最後要轉回進位制印出。

int n = 0;
for (i = 0; i < len; i ++)
{
    n *= b;
    n += p[i] - '0';
    n %= r;
}
printbBasic(n);

printbBasic 函式程式碼：

void printbBasic(int n)
{
    int i = 0, j;
    for ( ; n; n /= b)
        print[i ++] = n % b;
    if (i == 0) printf("0");    
    for (j = i - 1; j >= 0; j --)
        printf("%c", print[j] + '0');
    printf("\n");
}

By David.K

p10551題目連結
回ACM題庫目錄
回首頁

Problem 10573 Geometry Paradox，面積

這題要求出下圖灰色部分的面積。

這題如果給你 r1, r2 半徑，那就很好算出灰色部分面積。
依照公式： ((r1 + r2) * (r1 + r2) - r1 * r1 - r2 * r2) * PI。
如果只給你 t，要假設 r1 = r2，則 t 就為直徑，則 t / 4 則為兩圓半徑，
則白色部分面積為： 2 * (t / 4 * t / 4 * PI) = t * t / 8 * PI。
而灰色部分則是 (t / 2 * t / 2 * PI) - t * t / 8 * PI = t * t / 8 * PI。

By David.K

p10573題目連結
回ACM題庫目錄
回首頁

Problem 10583 Ubiquitous Religions，最大宗教群

此題與 Problem 10608 Friends 是一樣的，不過數量更大，建議可以使用輸入優化來縮短時間，但還是跑了一秒多，說明可點上面連結去看。

以下還是提供 C 語言程式碼：

int n, m;

int getInt()
{
    char ch;
    int n = 0;
    while( ch = getchar())
        if(ch != ' ' && ch != '\n') break;
    n = ch - 48;
    while( ch = getchar())
    {
        if(ch == ' ' || ch == '\n') break;
        n = n * 10 + ch - 48;
    }
    return n;
}

主程式內 ....
while ((n = getInt()) && (m = getInt()))
{
    int student[n + 1];
    religionID = 1, count = 0;
    memset(student, 0, sizeof(student));
    while (m --)
    {
        i = getInt(), j = getInt();
        if (student[i] == 0 && student[j] == 0)
        {
            student[i] = religionID, student[j] = religionID;
            religionID ++;
            count ++;
        }
        else if((student[i] != 0 && student[j] == 0) ||
                (student[i] == 0 && student[j] != 0))
        {
            tmp = student[i] < student[j] ? student[j] : student[i];
            student[i] = tmp, student[j] = tmp;
        } 
        else if (student[i] != student[j])
        {
            tmp = student[j];
            replace = student[i];
            for (s = 1; s <= n; s ++)
                if (student[s] == tmp) student[s] = replace;
            count --;
        }
    }
    /* for (i = 1; i <= n; i ++)
        printf("%d ", student[i]);
    printf("\n"); */
    for (i = 1; i <= n; i ++)
        if (student[i] == 0) count ++;
    printf("Case %d: %d\n", caseNum ++, count);
}

By David.K

p10583題目連結
回ACM題庫目錄
回首頁

Problem 10608 Friends，最大朋友群

鎮上有 N 個人，照一句諺語說：「我朋友們的朋友也是我的朋友」。A 和 B 為朋友，B 和 C 為朋友，所以 C 和 A 也為朋友。

讀入 N 和 M 兩整數，N 為鎮上有公民 1 - N，而接下來會有 M 列資料，M 列資料都有兩整數 a, b，代表公民 a 和公民 b 為朋友。最後請你算出這鎮上最大朋友群的數量為多少。

其實只要給朋友群定義一個朋友群編號，如果雙方都沒有朋友群編號，就將兩人都定義一個新的朋友群編號，並將此朋友編號數量變成 2；若兩人其中一人沒有朋友群編號，則將他加入有編號的朋友群之中；如果兩人都有朋友群編號，就將其中一方的所有朋友的編號改為另一方的編號，順便將另一方朋友編號數量累加對方的數量。

一開始宣告陣列以及初始化朋友群編號以及朋友群數量：

scanf("%d %d", &n, &m);
int friends[n + 1], record[n + 1], max = 0;
count = 0, groupID = 1;
memset(friends, 0, sizeof(friends));
memset(record, 0, sizeof(record));

接下來用以上敘述的概念寫成分群並且計算數量的方法，順便記錄最大值，寫成 C 語言程式碼如下：

while (m --)
{
    scanf("%d %d", &a, &b);
    if (friends[a] == 0 && friends[b] == 0)
    {
        friends[a] = groupID, friends[b] = groupID;
        record[groupID] = 2;
        if (max < record[groupID]) max = record[groupID];
        
        groupID ++;
        count ++;
    }
    else if((friends[a] != 0 && friends[b] == 0) ||
            (friends[a] == 0 && friends[b] != 0))
    {
        tmp = friends[a] < friends[b] ? friends[b] : friends[a];
        friends[a] = tmp, friends[b] = tmp;
        record[tmp] ++;
        if (max < record[tmp]) max = record[tmp];
    } 
    else if (friends[a] != friends[b])
    {
        tmp = friends[b];
        replace = friends[a];
        record[tmp] = 0;
        for (s = 1; s <= n; s ++)
            if (friends[s] == tmp) friends[s] = replace, record[replace] ++;
        if (max < record[replace]) max = record[replace];
        count --;
    }
    /* for (s = 1; s <= n; s ++)
        printf("%d ", record[s]);
    printf("\n"); */
}
printf("%d\n", max);

By David.K

p10608題目連結
回ACM題庫目錄
回首頁

Problem 10637 Coprimes，互質

此題用回溯演算法就可解決。這一開始我怎麼寫都寫不出來，答案的順序錯誤，結果我上網找了一下，原來找尋這些互質的數要由小到大，而且找的下一個數要比前一個相等或來的大。

還有一點，要建構互質表，不然很容易就超過時間了，網友 藍ㄚ有兩種解題方法 ，我從這裡參考的。

所以一開始建立互質表，C 語言程式碼如下：

#define SIZE 101

int print[SIZE];
int GCD[SIZE][SIZE];
int S, t;

int gcd(int a,int b)  
{  
 if (a % b == 0){ return b;} 
 return gcd(b, a % b);
}

主程式內 ....
int a, b, n;
for(a = 1; a < SIZE; a ++)
    for(b = 1; b < SIZE; b ++)
        GCD[a][b] = gcd(a,b);

最後寫一函式，利用回溯演算法將每一種可能的方法全部試過，如果超過我們所定義數值，只有剛好等於我們定義數值，才會被列出。

void find (int index, int n, int sum)
{
    int i, j;
    if (index == t && sum == S)
    {
        printf("%d", print[0]);
        for (i = 1; i < index; i ++)
            printf(" %d", print[i]);
        printf("\n");
        return;
        
    }
    if (sum >= S) return;
    for (; n <= S - sum; n ++)
    {
           for (j = 0; j < index; j ++)
               if (GCD[print[j]][n] != 1) break;
               
           if (j == index && S - sum >= n)
           {
               print[index] = n;
               find(index + 1, n, sum + n);
           }
    }
    
}

最後在主程是如此呼叫：

scanf("%d", &n);
for (i = 1; i <= n; i ++)
{
    scanf("%d %d", &S ,&t);
    printf("Case %d:\n", i);
    find(0, 1, 0);
}

By David.K

p10637題目連結
回ACM題庫目錄
回首頁