版主新書發表：C#程式設計學以致用

緣起

剛開始建立這個部落格時，只是想找個地方，將我在大學針對多半高中時期偏文組之初學新生所編寫的程式設計課程內容堆積起來，隨著時間流逝，也就這麼堆著堆著，還堆出了不少東西。在長江後浪推前浪的歷史軌跡上，讓我在課程內容上有著推陳出新的機會。

程式設計是個有門檻的迷人玩意兒，很多學會寫程式的同學都能體會那種達成解題任務的快感，當快感持續，進行ACM解題目即自然而然的成為茶餘飯後之消遣，一但到達這個田地，便不自覺功力大增，頗有騰雲駕霧之勢。

C語言是許多程式設計初學者接觸到的第一個語言，C語言嚴謹易學，用來學習程式邏輯的確是個不錯的選擇。大三、大四的同學在做專題時，都能延伸C語言的程式邏輯，對其他語言的學習如Java, C#, Javascript或php等，就好比已打通任督二脈的武者，對不同派系武功都能信手拈來、快速上手，其中有許多同學是使用C#做為網頁或視窗程式的開發工具。

經過一段時間的市場演進，系上在檢討後，決定開始以C#做為程式設計初學者的第一個語言。我在98學年度開始使用C#來教程式設計，在選擇教科書的過程中，我遇到一些難題。現有出版的C#教學書籍大多以學習Visual C#為主軸，因此對C#開發視窗程式、網頁程式、資料庫等方面均多有著墨，但是對於如何學會寫程式，或深入應用C#語言就相當少見，殊為可惜。基於這些原因，便起心動念針對這幾年的程式設計教學經驗，編寫一個既可教同學寫程式、又能讓同學熟練C#語言應用的教學用書，書名為「C#程式設計學以致用」。98學年結束後，從我教授班走出去的同學中的三分之一已學會寫程式解題。這學期啟用這本書後，我相信學會寫程式的同學比例會徙增，更希望他們因此上癮，也能享受那種騰雲駕霧之感。

購書資訊

本書係以我教授的對象為主，因而並未交由出版社發行，僅在http://using-c-sharp.blogspot.com部落格銷售。期待想學寫程式的初學者在獲得本書後，利用其中循序漸進設計之題目，上機練習，您將會感覺到學習效果，而習得以C#語言解決問題的能力短時可見。

謹致

梁克新

Crystal Report 參數

Crystal Report 參數可在程式中傳入數值至報表中顯示或者做其他判斷使用。接下來就是幾個基本步驟設定。

有問題請一定要發問!如果圖片太小，可再點擊進去看大圖。

1.

在「欄位總管」中的「參數欄位」點擊右鍵，按下「新增」（如圖一）。圖一

2.

此時會跳出「建立參數欄位」的視窗，鍵入自訂名稱，並且選擇數值類型，按下「確定」（如圖二）。圖二

3.

確定後「參數欄位」下會多一個欄位，即為剛剛建立的欄位（如圖三）。圖三

4.

接著可以利用這建立出來的欄位，拖曳到報表上利用（如圖四），而在程式碼之中，只需多加傳遞參數的函式 SetParameterValue ，傳入兩參數為參數欄位名稱與值（如圖五），最後執行報表後就會顯示出你所傳遞的值（如圖六）。圖四圖五圖六

Crystal Report 公式

Crystal Report 公式功能能使報表看起來看簡潔，也可將顯示欄位合併，讓欄位數量減少，讓報表得以有更多空間顯示其他資料。接下來就是幾個基本步驟設定。

有問題請一定要發問!如果圖片太小，可再點擊進去看大圖。

1.

在左側欄位總管的公式欄位點擊右鍵，按下「新增」（如圖一）。圖一

2.

此時會跳出一「公式名稱」之視窗，命名後按下使用編輯器（如圖二）。圖二

3.

接下來會跳出設計公式的視窗（如圖三），可以在右下方處編輯此公式欄位所要顯示之資料，使用的是 Crystal 語法，可以搭配資料庫欄位之值且可再加以變化，而 Crystal 語法類似 C#，右上方兩格視窗有函式與運算子，可以用拖曳方式將函式或運算子到右下方編輯公式處（資料庫欄位也可拖曳），如此一來，公式欄位可以說是千變萬化，設定完成後，在左上方按下「儲存並離開」。圖三

4.

此時在欄位總管中的公式欄位會多一欄位（如圖四），即是剛剛設定完成的欄位。這時就可將此欄位拖曳至報表運用（如圖五），最後顯示出來（如圖六）。圖四圖五圖六

Crystal Report 群組

此次要教大家如何使用 Crystal Report 群組的功能，便於在報表上分類與分區能使報表資訊更清楚顯示，使用過程並不困難，只有幾個步驟，在 Crystal Report 基本使用 上已有教大家怎麼建置基本的 Crystal Report。接下來就是幾個基本步驟設定。

有問題請一定要發問!如果圖片太小，可再點擊進去看大圖。

1.

在報表上任一空白處點擊右鍵，選擇「插入」、點擊「群組」，如圖所示（如圖一）。圖一

2.

此時會跳出「插入群組」視窗（如圖二），此時先視資料庫需用哪個欄位分類，而我在資料庫加了一個 Related 欄位（如圖三），便於在報表上分類，所以此時在「插入群組」視窗中需選擇 Related 欄位（如圖四）並按下確定。圖二圖三圖四

3.

加入群組後，會出現一群組首與群組尾的區塊（如圖五），方便設計一些以群組為主的圖片或背景，增加美感。接著我將剩下的資料庫欄位擺入（如圖六）報表中，執行後，就變成以 Related 欄位分類的報表（如圖七）。圖五圖六圖七

Crystal Report 基本使用

最近小弟在研究 Crystal Report 的用法，並且做了很多報表，一開始覺得用這個很麻煩，因為使用的項目還蠻多的，且版面要自己設計。但其實用熟了，就沒甚麼差了，所以在此分享 Crystal Report 的使用心得，當作是教學範例。我會從建置網頁、資料集新增與設定、Crystal Report 新增與設定到最後匯入資料的逐步順序說起，無非是因為給第一次使用 Crystal Report 的人也能照著下列步驟做起，重點是要玩出心得，這就不枉我寫這篇網誌了。

環境： windows 7、vs 2008

有問題請一定要發問!如果圖片太小，可再點擊進去看大圖。

1.

在左上角新增一個空白網站（如圖一），或者開啟已有網站。圖一

2.

開啟或新增網站後，在工具列上會找到「報告」的分類，而現在所要用到的控制項，就是圖中（如圖二）所指的控制項，名稱為「CrystalReportViewer」。圖二

3.

將此控制項拖曳到網頁(*.aspx)程式碼內，如圖（如圖三），並命名此控制項之 ID 為 CrystalReportViewer1。圖三

4.

接著在方案總管的空白處按右鍵，選擇「加入新項目」，會跳出視窗（如圖四），選擇「資料集」，命名後按下加入。圖四

5.

在這之前，要先確定資料表名稱以及欄位名稱，因為是初步教學，所以我隨手建立一個資料表，內容也是亂打的（如圖五）。圖五

6.

延續第三步驟，加入資料集後，對隨處對中間空白區域點擊右鍵，選擇加入，再選擇「TableAdapter」（如圖六）。接下來會跳出幾個基本設定視窗（如圖七、圖八、圖九、圖十、圖十一），比較注意的是圖九中的設定，因為它是決定報表連接的欄位，而不是資料的內容，所以在這裡的設定要小心，其中圓圈 1 的區塊是下達查詢語法，圓圈 2 的按鈕是可以讓你嘗試查詢語法是否正確，下達正確後再傳到圓圈 1 的區塊。圖六圖七圖八圖九圖十圖十一

7.

設定完成後，會出現如圖（如圖十二）所示。圖十二

8.

接著在方案總管的空白處按右鍵，選擇「加入新項目」，會跳出視窗（如圖十三），選擇「Crystal Report」，命名後按下加入。圖十三

9.

加入後，會跳出一視窗，有三種報表格式，「使用報表精靈」、「使用空白報表」、「從現存報表」，在這裡，要使用「空白報表」（如圖十四），因為「報表精靈」格式很固定且設定又多，所以我不喜歡用。圖十四

10.

設定完成報表格式，在「欄位總管」中對「資料庫欄位」點擊右鍵選擇「資料庫專家」（如圖十五）。圖十五

11.

此步驟是設定報表的欄位，也是要小心謹慎點，照圖（如圖十六）的 1 處為選擇「目前的連接」資料集，點擊 2 處，即可將資料加入 3 處，之後按下確定。圖十六

12.

回到「欄位總管」中，就會發現多了一個資料表，並且有資料表中的欄位（如圖十七）。圖十七

13.

在 Crystal Report 的工具箱，有三個不同的控制項，「Text Object」可以在報表加上固定的文字、「Line Object」可以在報表加上線條、「Box Object」可以在報表加上框線（如圖十八）。圖十八

14.

開始設計報表格式，可以將欄位總管的資料庫欄位拉進報表，報表分五區，「報表首」為報表前出現此區塊內容、「頁首」為每頁首前出現此區塊內容、「細目」為資料表的內容、「報表尾」為報表後出現此區塊內容、「頁尾」為每頁後出現此區塊內容（如圖十九）。以下只是隨手設計，如有雷同，那就雷同。圖十九

15.

最後在(*.cs)檔案寫程式匯入資料內容，此處也需要特別注意欄位的對應（如圖二十）。
圖二十

16.

最後，執行此網站，就可以看到如圖（如圖二十一）所示，可以看到區域的對應，也就是說，可以利用這些區域來配置更漂亮的報表。圖二十一

Crystal Report 教學

Crystal Report 教學目錄

1. Crystal Report 基本使用


2. Crystal Report 群組


3. Crystal Report 公式


4. Crystal Report 參數


5. Crystal Report 子報表

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題庫目錄
回首頁

Problem 10696 f91

此題為簡單題一枚。依照題目給的公式：

    *  If N ≤ 100, then f91(N) = f91(f91(N+11));
   * If N ≥ 101, then f91(N) = N-10.

我們可以拿 92 來做例子：
f91(92) = f91(f91(92 + 11)) = f91(f91(103)) = f91(93) = f91(f91(93 + 11)) = f91(94) = ...... = f91(101) = 91。
以上例子證明小於 101 之數，此遞迴函式必定將他調整為 91。
所以只要小於 101 之數為 91，大於等於 101 之數為此數減 10。
By David.K

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

Problem 10684 The jackpot，賭博

此題需要用到動態規畫。告知一連串的賭局輸贏金額，要你求出在任一段連續賭局中，能獲得的最多金幣，只需輸出金幣數值即可。

只需利用動態規劃將較佳數值往後推，推到陣列結束，在找出陣列內最大值即可。這裡也用到了輸入優化的方法。C 語言程式碼如下：

#define SIZE 10001

int money[SIZE], record[SIZE];

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

主程式內 ....
while (n = getInt())
{
    for (i = 0; i < n; i ++)
        money[i] = 0, record[i] = 0;
    int max = 0;  
    money[0] = getInt();
    if (money[0] <= 0)
       record[0] = 0; 
    else 
       record[0] = money[0], max = money[0];
    for (i = 1; i < n; i ++)
    {
        money[i] = getInt();
        record[i] = money[i] < money[i] + record[i - 1] ? 
             money[i] + record[i - 1] : money[i];
        if (record[i] > max) max = record[i];
    }
    if (max == 0) puts("Losing streak.");
    else printf ("The maximum winning streak is %d.\n", max);
}

By David.K

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

Problem 10664 Luggage，行李

此題讀入各行李重量後，以大到小排序，最後再平均分配在兩台車子上，如兩台車同重量，輸出 "YES"，否則，輸出 "NO"。

此處我也用到了輸入優化的方式。
關鍵程式碼如下：

#define SIZE 21

int luggage[SIZE], changeLine, index;

int getInt()
{
    char ch;
    int n = 0;
    changeLine = 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;
    }
    if (ch == '\n') changeLine = 1;
    return n;
}

主程式內 ....
index = 0, changeLine = 0, a = 0, b = 0;
while (!changeLine)
{
    luggage[index] = getInt();
    for (i = index; i >= 1; i --)
        if (luggage[i] > luggage[i - 1])
            tmp = luggage[i], luggage[i] = luggage[i - 1], luggage[i - 1] = tmp;
        else break;
    index ++;
}

for (i = 0; i < index; i ++)
{
    if (a == b) a += luggage[i];
    else if (a > b) b += luggage[i];
    else a += luggage[i];  
}

if (a == b) puts("YES");
else puts("NO");

By David.K

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

Problem 10919 Prerequisities?，畢業

讀入此學生修課通過的課程編號，用陣列接收，並且排序，再讀入課程類別課程數量以及必須通過課程的數量，接著一筆一筆讀入此課程類別的所有課程編號，比對修課通過的課程編號，累計數量後，大於等於此課程類別就代表此課程類別通過。如此將所有課程類別判斷過一次，如果沒有不通過的，就代表他會畢業。

此處如果輸入數量多的話，可以利用輸入優化來讀入整數或小數，而大家可以參網友「藍丫」提供的輸入優化 這函式讀入整數，如果數量一大，幾乎可以縮短一半以上的時間。感謝網友提供的輸入優化函式。而此函式程式碼如下：

#define SIZE 101

int classID[SIZE];
int index, n, m, c, r;

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;
}

所以可利用函式讀取修課通過的數量，排序好後，課程可用二分搜尋法來找尋是否有此課程。最後判斷他是否會畢業。

int isFind(int low, int high, int n)
{
    int mid;
    if (low > high) return -1;
    else
    {
        mid = (low + high) / 2;
        if (n == classID[mid])
            return mid;
        else if (n < classID[mid])
            return isFind(low, mid - 1, n);
        else 
            return isFind(mid + 1, high, n);
    }
}

主程式內 ....
while ((n = getInt()))
{
    index = 0;
    m = getInt();
    while (n --)
    {
        id = getInt();
        classID[index] = id;
        for (i = index; i >= 1; i --)
            if (classID[i] < classID[i - 1])
                tmp = classID[i], classID[i] = classID[i - 1], classID[i - 1] = tmp;
            else break;
        index ++;    
    }
    int error = 0, f;
    while (m --)
    {
        c = getInt(), r = getInt();
        int count = 0, find;
        while (c --)
        {
            f = getInt();
            find = isFind(0, index, f);
            if (find != -1) count ++;
        }
        if (count < r) error = 1; 
    }
    if (error) puts("no");
    else puts("yes");
}

By David.K

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

Problem 10903 Rock-Paper-Scissors，剪刀石頭布

讀入兩整數 n 和 k，說明有 n 的人進行 k * n * (n-1) / 2 場剪刀石頭布的遊戲，要你算出最後每個人的勝率，而勝率為 w / (l + w) (註：w 為勝場數，l 為敗場數)。

創建一個結構陣列，紀錄每個人勝敗場次數，如以下程式碼：

#define SIZE 101

struct player
{
    int win;
    int lose;
};
struct player p[SIZE];

其實只要比較每場勝敗為誰，再將這些結果累加到每個人的陣列索引，最後印出勝率。C 語言程式碼如下：

scanf("%d", &k);
for (i = 1; i <= n; i ++)
    p[i].win = 0, p[i].lose = 0;
game = k * n * (n - 1) / 2;
while (game --)
{
    scanf("%d %s %d %s", &p1, f1, &p2, f2);
    int kind1, kind2;
    if (f1[0] == 'r') kind1 = 1;
    else if (f1[0] == 'p') kind1 = 2;
    else kind1 = 3;
    if (f2[0] == 'r') kind2 = 1;
    else if (f2[0] == 'p') kind2 = 2;
    else kind2 = 3;
    if (kind1 > kind2) 
    { 
        j = kind1 - kind2;
        if (j == 1) p[p1].win ++, p[p2].lose ++;
        else p[p2].win ++, p[p1].lose ++;
    }
    else if (kind1 < kind2)
    {
        j = kind2 - kind1;
        if (j == 1) p[p2].win ++, p[p1].lose ++;
        else p[p1].win ++, p[p2].lose ++;
    }
}
int total, win;
for (i = 1; i <= n; i ++)
{
    win = p[i].win;
    total = win + p[i].lose;
    if (total == 0) printf("-\n");
    else printf("%.3f\n",(float)win / (float)total);
}

By David.K

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

Problem 10963 The Swallowing Ground，拼組地面

就是給你地面每個格子的間隙，要你判斷它組不組的起來。

只要記錄第一格子的間隙，再判斷接下來的間隙是否相同，不相同，輸出 no；相同，輸出 yes。

scanf("%d", &n);
while (n --)
{
    error = 0;  
    scanf("%d", &m);
    scanf("%d %d", &y1, &y2);
    sub = y1 - y2;
    m --;
    while (m --)
    {
        scanf("%d %d", &y1, &y2);
        if (sub != y1 - y2) error = 1;
    }
    if (error) printf("no\n");
    else printf("yes\n");
    if (n) printf("\n");
}

By David.K

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

Problem 11005 Cheapest Base，省錢

讀入 "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ" 每個字印出的錢，可用一整數陣列來接收：

for (i = 0; i < 36; i ++)
    scanf("%d", &money[i]);

接著我寫一函式，傳入兩整數，一為轉換為錢之整數，一為此整數的進位制。函式程式碼如下：

int getMoney(int n, int base)
{
    int nMoney = 0;
    for (; n; n /= base)
        nMoney += money[n % base];
    return nMoney;
}

最後將 2 - 36 進位與欲印出的數字丟到上述函式轉換錢，並且進行比較，比較後記錄最小值，最後印出即可。C 語言程式碼如下：

index = 0;
scanf("%d", &m);
for (i = 0; i < m; i ++)
{
    scanf("%d", &k);
    index = 0;
    min = getMoney(k, 2);
    best[index ++] = 2;
    for (j = 3; j <= 36; j ++)
    {
        count = getMoney(k, j);
        if (min == count) best[index ++] = j;
        if (min > count) min = count, index = 0, best[index ++] = j;
    }
    printf("Cheapest base(s) for number %d:", k);
    for (j = 0; j < index; j ++)
        printf(" %d", best[j]);
    printf("\n");
}

By David.K

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

Problem 11015 05-2 Rendezvous，小組集合

此題給你兩整數，N 和 M，接下來會有 N 列姓名，代表組員 1 ~ N 的姓名。再接下來會有 M 列資料，M 列每列會有三整數 i, j 和 k，代表組員 i 到組員 j 的距離為 k。最後要你求出哪一組員的家，與其他所有組員家的距離是最短的。

使用「佛洛依德最短路徑演算法」就可以解決此題。首先，創建一個 N * N 陣列 W 並且將陣列內所有值歸 0，順便紀錄 N 個組員的姓名；而接下來 M 列資料，讀取每行 i, j , k 後將 W[i][j] = W[j][i] = k。

因為可能有些組員到其他組員家是沒有路勁的，所以演算法稍做修改，C 語言程式碼如下：

#define SIZE 23
struct Crew
{
    char name[12];
};
struct Crew c[SIZE];
int W[SIZE][SIZE];

主程式內 ....
for (k = 1; k <= n; k ++)
    for (i = 1; i <= n; i ++)
        for (j = 1; j <= n; j ++)
        {
            if (i != j && W[i][k] != 0 && W[k][j] != 0)
            {
                int m = W[i][k] + W[k][j];
                if (W[i][j] == 0) W[i][j] = m;
                else if (m < W[i][j]) W[i][j] = m;
            }
        }

最後，加總以某組員家為集合地點的路徑，再去比較誰的路徑最短，最後再印出組員名字。C 語言程式碼如下：

for (i = 1, min = 0; i <= 1; i ++)
    for (j = 1; j <= n; j ++)
        if (i != j)
            min += W[i][j];
minID = 1;
int count;
for (i = 2; i <= n; i ++)
{
    for (j = 1, count = 0; j <= n; j ++)
    {
        if (i != j)
            count += W[i][j];
    }
    if (min > count)
        min = count, minID = i;
}
printf("Case #%d : %s\n", caseNum ++, c[minID].name);

By David.K

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

Problem 10026 Shoemaker's Problem，工作排序

本來我打算放棄解這題，不過 google 了一下，發現只須要用到排序，就能解決這一題。

假設有兩個工作要比較，d1, m1 和 d2, m2 (d 為工作天，m 為延遲罰金)，要比較它們的大小就讓它們工作天以及延遲罰金互乘，再去比較大小，則可很輕易的就排序出結果，例如： 3個工作天，延遲罰金 5 以及 4 個工作天，延遲罰金 7，而 3 * 7 > 4 * 5，則後者排序在前，前者排序在後。

關鍵程式碼如下：

#define SIZE 1001
struct Job
{
    int num;
    int wDay;
    int dMoney;
};
struct Job job[SIZE], r;

主程式內 ...

scanf("%d", &m);
for (i = 0; i < m; i ++)
{
    scanf("%d %d", &day ,&money);
    job[i].wDay = day, job[i].dMoney = money;
    job[i].num = i + 1;
    for (j = i; j >= 1; j --)
    {
        if (job[j].wDay * job[j - 1].dMoney < 
            job[j - 1].wDay * job[j].dMoney)
        {
            r = job[j], job[j] = job[j - 1],
            job[j - 1] = r;
        }
        else break;
    }
}

最後只要逐個印出 job 陣列內的 num 值就好了。

By David.K

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

Problem 10048 Audiophobia，噪音恐懼症

此題與 Problem 534 Frogger 用的方法一模一樣，只是這題更簡單了，因為它不需要算點與點之間的距離，它直接給你某路口走到某路口所經過的街道，噪音有多少分貝。

因為這一題有些地方不能直達，所以值還會是 0，所以我初始化就全部給他定 1000，噪音到 1000 分貝，耳膜也破了吧。再接著用最小路徑演算法，答案就會呼之欲出了。

for (i = 1; i <= C; i ++)
    for (j = 1; j <= C; j ++)
        W[i][j] = 1000;

for (i = 0; i < S; i ++)
{
    int noise, p1, p2;
    scanf("%d %d %d", &p1, &p2, &noise);
    W[p1][p2] = W[p2][p1] = noise;
}
for (k = 1; k <= C; k ++)
    for (i = 1; i <= C; i ++)
        for (j = 1; j <= C; j ++)
            if (i != j)
                W[i][j] = min(W[i][j], max(W[i][k], W[k][j]));
if (caseNum != 1) printf("\n");
printf("Case #%d\n", caseNum ++);
for (i = 1; i <= Q; i ++)
{
    int p1, p2;
    scanf("%d %d", &p1, &p2);
    int minNoise = W[p1][p2];
    if (minNoise != 1000) printf("%d\n", W[p1][p2]);
    else printf("no path\n");
}

By David.K

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

Problem 10015 Joseph's Cousin，吃人遊戲

此題為紐西蘭停電的進階版，因為他不是從頭到尾數同一個數，而是要吃掉第 i 個人，就要數第 i 個質數，直到吃剩最後一個人才停，要輸出這最後一個人在什麼位置。

我用的方法很粗糙，暴力破解，所以執行時間有點長，不過還是過了。

首先建立質數表，數值到 33000，就能把前 3502 的質數找出來：

#define SIZE 33000
int prime[SIZE + 1];
int prime_table[SIZE], prime_table_len = 0;

void makeprime(){
    int i, j;
    prime_table[prime_table_len ++] = 2;
    for(i = 3; i < SIZE; i += 2)
        if(!prime[i]){
            for(j = i + i; j <= SIZE; j += i)
                prime[j] = 1;
            prime_table[prime_table_len ++] = i;
        }
}

再用暴力破解即可，C 語言程式碼如下：

int nextLife(int isLife[], int site, int n)
{
    while (!isLife[site])
    {
        site ++;  
        if (site >= n) site -= n;
    }
    return site;
}

int main()
{
    makeprime();
    int n, i, j, life;
    while (scanf("%d", &n) == 1 && n)
    {
        int isLife[n], nowSite = 0, count;
        for (i = 0; i < n; i ++) /* 初始化 */
            isLife[i] = 1;
        for (i = 0; i < n - 1; i ++)
        {
            count = prime_table[i] - 1;
            
            for (j = 0; j < count; j ++)
            {
                nowSite = nextLife(isLife, nowSite, n);
                nowSite ++;
                if (nowSite >= n) nowSite -= n;
            }
            nowSite = nextLife(isLife, nowSite, n);
            isLife[nowSite] = 0;
        }
        for (i = 0; i < n; i ++)
            if (isLife[i]) { printf("%d\n", i + 1); break; }
        
    }
    return 0;
}

By David.K

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

Problem 10010 Where's Waldorf?，找字串

給你一雜亂無章的字元陣列，要你從這字元陣列中，找尋出一些相符字串。只是搜尋字串必須朝著某一方向進行，例如：
要找尋底下四個字串
Waldorf
Bambi
Betty
Dagbert
而在底下陣列出現之位置如變色所在：

abcDEFGhigg
hEbkWalDork
FtyAwaldORm
FtsimrLqsrc
byoArBeDeyv
Klcbqwikomk
strEBGadhrb
yUiqlxcnBjf

上面例子已經很清楚的顯示，搜尋字串必須朝某一方向，不能彎來彎去，而輸出要輸出字串符合的開頭位置：
2 5
2 3
1 2
7 8

此題要用遞迴來解決，但是一旦決定方向，便不再改變。寫一函式嘗試核對字串，傳入陣列位置 i, j，以及找尋字串目前索引 index 和方向的編號 id(此數決定該往何方向核對字串)，C 語言程式碼如下：

#define SIZE 51

char W[SIZE][SIZE];
char str[200];
int row, col, isFind, len;

void searchStr(int i, int j, int index, int id)
{ 
    if (W[i][j] != str[index]) return;
    if (isFind || index == len - 1) {isFind = 1; return;}
    else
    {
        /* 左 */
        if (j - 1 >= 0 && (!id || id == 1)) 
            searchStr(i, j - 1, index + 1, 1);
        /* 左上 */
        if (j - 1 >= 0 && i - 1 >= 0 && (!id || id == 2)) 
            searchStr(i - 1, j - 1, index + 1, 2);
        /* 上 */
        if (i - 1 >= 0 && (!id || id == 3)) 
            searchStr(i - 1, j, index + 1, 3);
        /* 右上 */
        if (j + 1 < col && i - 1 >= 0 && (!id || id == 4)) 
            searchStr(i - 1, j + 1, index + 1, 4);
        /* 右 */
        if (j + 1 < col && (!id || id == 5)) 
            searchStr(i, j + 1, index + 1, 5);
        /* 右下 */
        if (j + 1 < col && i + 1 < row && (!id || id == 6)) 
            searchStr(i + 1, j + 1, index + 1, 6);
        /* 下 */
        if (i + 1 < row && (!id || id == 7)) 
            searchStr(i + 1, j, index + 1, 7);
        /* 左下 */
        if (j - 1 >= 0 && i + 1 < row && (!id || id == 8)) 
            searchStr(i + 1, j - 1, index + 1, 8);
    }
}

上段程式面，str 為找尋字串，W 為字元陣列。

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

gets(str);
len = strlen(str); 
for (j = 0; j < len; j ++)
    str[j] = tolower(str[j]);
isFind = 0;
for (j = 0; j < row && !isFind; j ++)
    for (s = 0; s < col && !isFind; s ++)
    {
        searchStr(j, s, 0, 0);
        if (isFind) printf("%d %d\n", j + 1, s + 1);
    }

By David.K

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

Problem 10004 Bicoloring，著色問題

此題為一老老實實的 m - 著色問題，這用回溯演算法就可以解決了。

首先將節點能連接的通通將值改為 1，因為是雙向的，所以也要將反向連接的也改為 1，C 語言程式碼如下：

int pathNum, f, t;
scanf("%d", &pathNum);
for (i = 0; i < pathNum; i ++)
    scanf("%d %d", &f, &t), W[f + 1][t + 1] = W[t + 1][f + 1] = 1;

利用回溯演算法找出有幾種塗色方式，C 語言程式碼如下：

int promising(int i)
{
    int j;
    for (j = 1; j < i; j ++)
    {
        if (W[i][j] && vcolor[i] == vcolor[j])
            return 0;
    }
    return 1;
}

void m_coloring(int i)
{
    int color, j;
    if (i == n + 1)
        total ++;
    else
    {
        for (color = 1; color <= m; color ++)
        {
            vcolor[i] = color;
            if (promising(i)) m_coloring(i + 1);
        }
    }
}

最後只須在主程式內如此呼叫以及印出：

total = 0;
m_coloring(1);
if (total == 0) printf("NOT BICOLORABLE.\n");
else printf("BICOLORABLE.\n");

By David.K

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

Problem 763 Fibinary Numbers，費氏級數顯示方式

費氏級數進位的有些數值可能會有不只一種情況，例如：10 可表示為 10010 (8 + 2)，但也可表示為 1110 (5 + 3 + 2)，題目會給你兩個費氏級數，請你相加之後，要轉成前者，而不是後者，也就是說，不允許 1 相連。

首先，讀入兩字串，將這兩字串反向擺入一個整數陣列，方便相加：

mIndex = strlen(str);
for (i = mIndex - 1, j = 0; i >= 0 ; i--, j ++)
    m[j] = str[i] - '0';    
memset(str, 0, strlen(str)); 
scanf("%s", str); 
nIndex = strlen(str);
for (i = nIndex - 1, j = 0; i >= 0 ; i--, j ++)
    n[j] = str[i] - '0';

寫一函式，相加兩陣列到 sum 陣列：

void add(int index)
{ 
    int i;
    for (i = 0; i < index; i ++)
        sum[i] = m[i] + n[i];
}

相加之後，就判斷 1 相連的位置，並且使它進位，直到判斷沒有任何數要進位為止。 C 語言程式碼如下：

isChange = 1;
while (isChange)
{
    isChange = 0;
    index = sumLength();  
    for (i = index ; i >= 2; i --)
        if (sum[i] > 1) sum[i]--, sum[i - 1] ++, sum[i - 2] ++, isChange = 1;
    for (i = index; i >= 1; i --)
        if (sum[i] >= 1 && sum[i - 1] >= 1) sum[i]--, sum[i - 1]--, sum[i + 1] ++, isChange = 1;
    if (sum[0] >= 2)
       sum[1] ++, sum[0] -= 2, isChange = 1;
    if (sum[1] >= 2)
       sum[1] -= 2, sum[2] ++, sum[0] ++, isChange = 1;            
}

最後反向印出即可。

By David.K

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

Problem 626 Ecosystem，食物鏈

輸入一 n 值後，讀入 n * n 陣列，例如： n = 3，而陣列內容如下

索引  | 1 | 2 | 3
---------------
1     | 0 | 1 | 0
---------------
2     | 0 | 0 | 1
---------------
3     | 1 | 0 | 0

這例子代表有三種動物，動物 1 吃動物 2，動物 2 吃動物 3，動物 3 吃動物 1。
所以形成一個循環 1 吃 2 吃 3 吃 1，以 1 2 3 表示，但也可以以 2 3 1、 3 1 2 表示，但這種情況只要輸出遞增或遞減的那個。

此題用一巢狀迴圈就可以找出所有食物鏈，假設動物 i 吃動物 j，動物 j 吃動物 k，動物 k 吃動物 i。首先要找尋動物 i 以及動物 j，在嘗試找尋動物 k，最後再判斷是否為遞增或遞減。
尋找動物 k 的方法，我用一函式來找尋， C 語言程式碼如下：

int system[102][102];

int n, count;
void ecosystem(int f, int m)
{
    int i, j, t;
    if (!system[f][m]) return;
    for (t = 0; t < n; t ++)
    {
        if (system[m][t] && system[t][f])
           if (( f > m && m > t ) ||( t > m && m > f ))
           { printf("%d %d %d\n", f + 1, m + 1, t + 1); count ++; }
        
    }
}

最後只須在主程式內呼叫以及輸出：

count = 0;
for (i = 0; i < n; i ++)
    for (j = 0; j < n; j ++)
    {
        ecosystem(i, j);
    }
printf("total:%d\n\n", count); 

By David.K

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

Problem 821 Page Hopping，翻頁

題目輸入整數 i 和整數 j，意思是說第 i 頁翻到第 j 頁需要一次，數量不等，讀到 0 0 結束讀取，若一開始就輸入 0 0 程式就會結束，當我們翻書時，會產生一書的「拍打聲」，所以我們要輸出此書平均會「拍打」幾聲。

此題要先紀錄最大的頁數，並且將所有第 i 頁翻到第 j 頁的資料在索引內的值變為 1，例如：
1 2 2 4 1 3 3 1 4 3 0 0
而陣列內的所有狀態如下：
0 1 1 0
0 0 0 1
1 0 0 0
0 0 1 0
而陣列狀態定義好後，使用「最短路徑演算法」後，再將陣列內的值總合起來除以陣列內有值的個數，答案就會出來了。C 語言程式碼如下：

count = 0, sum = 0; 
for(k = 1; k <= max; k++)
r(i = 1; i <= max; i++)
or(j = 1; j <= max; j++)
        {
            if (i != j && page[i][k] != 0 && page[k][j] != 0)
            {
                int t = page[i][k] + page[k][j];
                if (page[i][j] == 0) page[i][j] = t;
                else if (t < page[i][j]) page[i][j] = t;
            }
        }
or(i = 1; i <= max; i ++)
   for(j = 1; j <= max; j ++)
   {
       int t = page[i][j];
       if (page[i][j] > 0) sum += t, count ++;
   }
printf("Case %d: average length between pages = %.3f clicks\n", caseNum ++,(float)sum / (float)count);

By David.K

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

Problem 808 Bee Breeding，最短移動距離

此題與 Problem 10182 Bee Maja 一樣，要先求出座標以及位置。

而此題座標規則與 10182 有些不同，如下圖：而求出座標以及位置，10182 講得很清楚了，這裡不再多說，只是求出兩座標後要利用以下公式求出距離：
座標 1：(x1, y1)、座標 2：(x2, y2)， dx = x1 - x2, dy = y1 - y2，則距離為： (|dx| + |dy| + |dx + dy|) / 2。
By David.K

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

Problem 10182 Bee Maja，蜜蜂座標的轉換

Maja 是一隻蜜蜂，她和其他數以千計的蜜蜂住在鬧區，這鬧區是一種以六邊形緊鄰的方式排列。
但問題就出在 Willi 告訴 Maja，在哪裡可以與他會面，要知道，Willi 是一個懶惰的蜜蜂，而 Maja 是一個勤勞的蜜蜂，所以他們對於鬧區有不同的座標看待方式。
以下為 Maja 看待鬧區方式：而以下為 Willi 看待鬧區方式：問題就是，我輸入 Willi 座標，請你把它轉換為 Maja 座標。

首先，我們要找出座標規則，如同下圖所示：接著判斷它的移動方向，從 1 開始第一次循環，只跑一次，它是從 0, 0往下，再來往左上、上、右上、右下到 6 為止，接著 7 進入第二循環，跑兩次，往下，左下(注意，右下每次執行階會與循環次數少 1，所以第一次循環沒有執行)、左上、上、右上、右下到 17 為止。如此如此執行到大於等於 100000 為止。
依照以上觀念寫成 C 語言程式碼如下：

#define SIZE 100000

struct point
{
    int x, y;
};
struct point p[SIZE + 1];
int index;
void create()
{
    p[1].x = 0, p[1].y = 0;
    index = 2;
    int nowI = 0, nowJ = 0, count, num;
    for (num = 1; index <= SIZE; num ++)
    {
        for (count = 0; count < num && index <= SIZE; count ++, index ++)
            p[index].x = nowI, p[index].y = ++ nowJ;
        for (count = 0; count < num - 1 && index <= SIZE; count ++, index ++)
            p[index].x = -- nowI, p[index].y = ++ nowJ;
        for (count = 0; count < num && index <= SIZE; count ++, index ++)
            p[index].x = -- nowI, p[index].y = nowJ;
        for (count = 0; count < num && index <= SIZE; count ++, index ++)
            p[index].x = nowI, p[index].y = -- nowJ;
        for (count = 0; count < num && index <= SIZE; count ++, index ++)
            p[index].x = ++ nowI, p[index].y = -- nowJ;
        for (count = 0; count < num && index <= SIZE; count ++, index ++)
            p[index].x = ++ nowI, p[index].y = nowJ;
    }
}

最後在主程式如此呼叫：

create();
int n;
    
while (scanf("%d", &n) == 1)
    printf("%d %d\n", p[n].x, p[n].y);

By David.K

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

Problem 785 Grid Colouring，著色

這題就是 Problem 784 Maze Exploration 的進階版，只比它難一咪咪。

字元 'X' 這次代表框架，此題重點就在於要記錄它著色的字元以及位置，就如同 784 的字元 '*' 一樣，所以宣告陣列有些許的改變。C 語言程式碼如下：

#define ROW 33
#define COL 83
#define SIZE 300
struct point
{    
    char ch;
    int i;
    int j;
};
struct point p[SIZE];
char str[ROW][COL];
int index;

而函式也稍做修改，程式碼如下：

void visit(int i, int j, char ch)
{
    str[i][j] = ch;
    
    if (str[i - 1][j] == ' ') visit(i - 1, j, ch);
    if (str[i + 1][j] == ' ') visit(i + 1, j, ch);
    if (str[i][j - 1] == ' ') visit(i, j - 1, ch);
    if (str[i][j + 1] == ' ') visit(i, j + 1, ch);
}

最後就是要記錄著色的字元以及位置，就請各位參考，在此就不再解說：

int n, len, line = 0, i;
index = 0;
while (gets(str[line]))
{   
    len = strlen(str[line]);
    if (str[line][0] == '_')
    {
        for (i = 0; i < index; i ++)
            visit(p[i].i, p[i].j, p[i].ch);
        for (i = 0; i <= line; i ++)
            puts(str[i]);
        line = 0, index = 0; continue;
    }
    for (i = 0; i < len; i ++)
        if (str[line][i] != ' ' && str[line][i] != 'X') 
        { p[index].ch = str[line][i]; p[index].i = line; p[index].j = i; index ++; }
    line ++;
}

By David.K

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

Problem 784 Maze Exploration，迷宮探索

此題給你一個迷宮，迷宮皆用字元 'X' 圍起，而目前的位置是在字元 '*' (星號)，可以上下左右移動，要找出在這個迷宮所能走到的範圍，並且用字元 '#' 填滿這個範圍。

我們可以先建立一個陣列，題目規定範圍在寬：30、長：80。

#define ROW 33
#define COL 83
char str[ROW][COL];

接著在主程式讀取字串並且記憶字元 '*' 在陣列的位置：

for (line = 0, isStar = 0; ; line ++)
{
    gets(str[line]);
    len = strlen(str[line]);
    if (!isStar)
    {
        for (i = 0; i < len; i ++)
            if (str[line][i] == '*') 
            { startI = line, startJ = i; isStar = 1; break; }
    }
    if (str[line][0] == '_') break;
}

isStar 為判斷字元 '*' 是否出現過，startI、startJ 記錄字元 '*' 在陣列之位置，只要一讀到字元 '_' 便跳出並且計算。
接下來就是將探索地區填滿字元 '#'，其實只要用遞迴就可以解決這個問題，讀入座標，將此位置的字元改為 '#'，並且嘗試上下左右位置是否為 ' '，再將這個位置傳入遞迴。C 語言程式碼如下：

void visit(int i, int j)
{
    str[i][j] = '#';
    
    if (str[i - 1][j] == ' ') visit(i - 1, j);
    if (str[i + 1][j] == ' ') visit(i + 1, j);
    if (str[i][j - 1] == ' ') visit(i, j - 1);
    if (str[i][j + 1] == ' ') visit(i, j + 1);
}

最後只須在主程式內這麼呼叫：

visit(startI, startJ);

By David.K

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

Problem 725 Division

輸入一 n 值，要找出所有 abcde / fghij = n 的數，條件是，abcde 和 fghij 的每個位數不能重複出現，如果不滿五位數，則補 0。此題與 Problem 471 Magic Numbers 相同，如果解了此題，不仿可以解解 471。

找尋此數，因 abcde > fghij，所以 fghij >= 1234，因為如果小於 1234 的數，都會違反條件。

首先，寫一判斷兩數符合條件之函式：

int check(int i, int j)
{
    int tmp, k, repeat[10] = {0};
    for (k = 0 ; k < 5; k ++)
    {
        tmp = i % 10;
        if (repeat[tmp]) return 0;
        repeat[tmp] = 1;
        i /= 10;
        tmp = j % 10;
        if (repeat[tmp]) return 0;
        repeat[tmp] = 1;
        j /= 10;
    }
    return 1;
}

主程式則是要從 fghij = 1234，持續判斷到 abcde >= 100000 為止。 C 語言程式碼如下：

abcde = 1234 * n, fghij = 1234;
count = 0;
if (caseNum ++ != 0) printf("\n");
for (; abcde < 100000; abcde += n, fghij ++)
    if (check(abcde, fghij)) 
        printf("%05d / %05d = %d\n", abcde, fghij, n), count ++;
if (count == 0) printf("There are no solutions for %d.\n", n);

By David.K

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

Problem 466 Mirror, Mirror

此題給你兩種矩形，請你判斷第一種如何旋轉或者水平鏡照，會變成第二種。

例如給你一個 4 * 4 的矩陣，如下：
‧X‧‧
‧X‧X
‧‧‧‧
‧‧X‧
而矩陣的旋轉以及鏡照有以下幾種情況：
(1) 90 Degree Rotation：矩陣向右旋轉 90 度。
‧‧‧‧
‧‧XX
X‧‧‧
‧‧X‧
(2) 180 Degree Rotation：矩陣向右旋轉 180 度。
‧X‧‧
‧‧‧‧
X‧X‧
‧‧X‧
(3) 270 Degree Rotation：矩陣向右旋轉 270 度。
‧X‧‧
‧‧‧X
XX‧‧
‧‧‧‧
(4) Vertical Reflection：水平鏡照，上下如同看鏡子似的，相互鏡照。
‧‧X‧
‧‧‧‧
‧X‧X
‧X‧‧
(5) Combination：水平鏡照加上一個角度的旋轉。(以下是水平鏡照加上右轉 90 度角)
‧‧‧‧
XX‧‧
‧‧‧X
‧X‧‧
(6) Preservation：一開始就和原本的一樣。
(7) Improper：以上狀況都不符合的情況。

其實關鍵就在於你會不會寫轉換函式，寫完幾乎就已經完成了。以下為關鍵函式程式碼：

void rotation90()
{
     int i, j;
     for (i = 0; i < n; i ++)
         strcpy(s[i], replace[i]);
     for (i = 0; i < n; i ++)
         for (j = 0; j < n; j ++)
             replace[i][j] = s[n - j - 1][i];
}

void rotation180()
{
     int i, j;
     for (i = 0; i < n; i ++)
         strcpy(s[i], replace[i]);
     for (i = 0; i < n; i ++)
         for (j = 0; j < n; j ++)
             replace[n - i - 1][j] = s[i][n - j - 1];         
}

void rotation270()
{
     int i, j;
     for (i = 0; i < n; i ++)
         strcpy(s[i], replace[i]);
     for (i = 0; i < n; i ++)
         for (j = 0; j < n; j ++)
             replace[j][i] = s[i][n - j - 1];

}

void reflection()
{
    int i, j;
    for (i = 0; i < n; i ++)
         strcpy(s[i], replace[i]);
    for (i = 0; i < n; i ++)
        for (j = 0; j < n; j ++)
            replace[n - j - 1][i] = s[j][i];
}

By David.K

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

Problem 474 Head / Tails Probability，2 的 -n 次方

要求 2_-n 的指數型態，可以用 double 的 %e 顯示，但格式不太對，而且 2^-1000000 次方的位數太大了，double 接收不了，所以還是乖乖的算出它來。

首先求位數，一般我們用 log₁₀(n) 能求出 n 是幾位數，例如 log₁₀(100) = 2、 log₁₀(1000) = 3、 log₁₀(56565) = 4.7525... 、 ... 等等。
所以可以宣告一整數 power，接收此次 n 值的位數，則位數求法為： (int)ceil(n * log10(2))。

再求 2^-n 的頭幾位數，可以利用公式推導：

          2-n = a
   log10(2-n) = log10(a)
-n * log10(2) = log10(a)
10 -n * log10(2) = a

但如果 n 值越大，a 就越小，所以我們可以加上剛剛求出的位數，將它變成有個位數，則為
10 ^{-n * log₁₀(2) + power}。

最後，不知道是 UVa 答案出了問題，還是題目沒說清楚，在 n = 6時，本來為 1.563e-2，卻為 1.562e-2，所以這要額外判斷。 C 語言程式碼如下：

int power = (int)ceil(n * log10(2));
double d = pow(10, -n * log10(2) + power);
if (n != 6) printf("2^-%d = %.3fe-%d\n", n, d, power);
else printf("2^-6 = 1.562e-2\n");

By David.K

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

Problem 471 Magic Numbers

輸入一個 n 值，請你找出所有 s1 / s2 的數，但有唯一條件，就是以上出現的每個數(n 或 s1 或 s2)，每個位數不會重複出現。例如： 1234567890 就符合條件， 1123 就不符合條件。

首先寫一個檢查位數的函式，符合就回傳 1，反之，回傳 0，C 語言程式碼如下：

int check (long long int n)
{
    int repeat[10] = {0};
    for (; n; n /= 10)
    {
        int tmp = n % 10;
        if (repeat[tmp]) return 0;
        repeat[tmp] = 1;
    }
    return 1;
}

接下來只要用一迴圈，初設 s1 = n, s2 = 1，找尋每個 s1 / s2 = n 的數值，在我實驗看來，s2 不會超過 180000。 C 語言程式碼如下：

long long int s1, s2, limit, n;
scanf("%d", &caseNum);

for (i = 0; i < caseNum; i ++)
{
    scanf("%lld", &n);
    limit = 180000;
    if (i != 0) printf("\n");
    for (s2 = 1, s1 = n; s2 < limit; s1 += n, s2 ++)
    {
        if (check(s1) && check(s2))
            printf("%lld / %lld = %lld\n", s1, s2, n);
    }
}

By David.K

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

Problem 459 Graph Connectivity，畫連接線

此題要用到回溯演算法，讀入第一個英文字母後，決定陣列的範圍，我們可以宣告整數陣列為 W[27][27]，因為大寫字母最大到 Z(26)，再接下來有 0 到多行，每行都有兩個大寫英文 ch1 和 ch2，代表連接線，此時我們可以改變 W 陣列內的值，將 W[ch1 - 'A'][ch2 - 'A'] = W[ch2 - 'A'][ch1 - 'A'] = 1，因為連接線是無向的，也藉此表示這兩點有連接。

再來宣告一整數陣列 v[27]，紀錄每個連結點是否有拜訪過，一旦拜訪，就不再拜訪，當拜訪每一個節點，改變它在 v 陣列位置的值為 1。接著再找尋它每一個能連結的點，就再將它每個能連結點 v 陣列位置的值改為 1，再繼續找尋這些連結點能連結的點。如此如此做下去，結果就會出來了。

以下為拜訪函式：

int m;
int W[27][27];
int v[27];
void visit(int n)
{
     v[n] = 1;
     int i, j;
     for (i = 0; i <= m; i ++)
         if (v[i] == 0 && W[n][i] == 1)
             visit(i);
}

在主程式如此呼叫此函式：

int n, i, j;
char ch[3];
scanf("%d", &n);
for (j = 0; j < n; j ++)
{
    int count = 0, isCase = 0;  
    memset(v, 0, sizeof(v));
    memset(W, 0, sizeof(W));
    while (gets(ch))
    {
        int len = strlen(ch);
        if (len == 0) 
        { 
           if (isCase)
           {
               for (i = 0; i <= m; i ++)
               {
                   if (v[i] == 0)
                       visit(i), count ++;
               }
               if (j != 0) printf("\n");
               printf("%d\n", count);
               isCase = 0;
               break;
           } 
        }
        if (len == 1) isCase = 1, m = ch[0] - 'A';
        if (len > 1)
        {
            int node1 = ch[0] - 'A';
            int node2 = ch[1] - 'A';
            W[node1][node2] = W[node2][node1] = 1;
        }
    }
    if (isCase)
    {
        for (i = 0; i <= m; i ++)
        {
            if (v[i] == 0)
                visit(i), count ++;
        }
        if (j != 0) printf("\n");
        printf("%d\n", count);
        isCase = 0;
    }
}

By David.K

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