C語言考古題 & C的解題 -- 程式設計學習入門

Problem 879 Circuit Nets，電絡網

2011-07-10T14:02:00.001+08:00

同 793 Network Connections，在此不贅述。

By David.K

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

Problem 793 Network Connections，網絡連接

2011-07-10T13:55:00.001+08:00

此題使用 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 機器人運動

2011-07-10T13:35:00.001+08:00

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

#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

2011-07-10T12:52:00.001+08:00

先對 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，星星 ? 物體 ?

2011-06-26T16:08:00.006+08:00

此題利用深度優先搜尋法即可解決問題。重點 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，最小質數

2011-06-25T18:51:00.000+08:00

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

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

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

Problem 10579 Fibonacci Numbers，超大費氏級數

2011-06-25T16:01:00.001+08:00

此題需要利用大數相加即可， 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題庫目錄
回首頁

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

2010-09-25T17:10:00.002+08:00

緣起

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

程式設計是個有門檻的迷人玩意兒，很多學會寫程式的同學都能體會那種達成解題任務的快感，當快感持續，進行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 參數

2010-09-01T23:29:00.006+08:00

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

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

1.

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

2.

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

3.

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

4.

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

Crystal Report 公式

2010-09-01T00:28:00.004+08:00

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

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

1.

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

2.

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

3.

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

4.

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

Crystal Report 群組

2010-08-20T10:09:00.009+08:00

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

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

1.

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

2.

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

3.

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

Crystal Report 基本使用

2010-08-15T20:37:00.009+08:00

最近小弟在研究 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 教學

2010-08-15T12:49:00.010+08:00

Crystal Report 教學目錄

Crystal Report 基本使用

Crystal Report 群組

Crystal Report 公式

Crystal Report 參數

Crystal Report 子報表

Problem 11805 Bafana Bafana，傳球

2010-07-11T22:13:00.003+08:00

輸入 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，最長共同子字串

2010-07-11T14:20:00.003+08:00

建議大家可以上網去找「最長共同子字串」的演算法，此演算法是由「最長連續共同子字串」推演而來。「最長共同子字串」的方法就是依序比對字串，將最佳比對結果逐一往陣列右下方推，推到最後，答案就出來了。
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，骰子遊戲

2010-07-11T13:52:00.002+08:00

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

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

2010-07-11T12:55:00.002+08:00

給你一陣列，要你求出從字元 '@'( 一定在最後一排 )到字元 '#'( 一定在第一排 )，按照字串 "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，小學數學

2010-07-11T12:26:00.003+08:00

此題要算出他給你的運算式。用 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，麻煩的小孩

2010-07-11T11:59:00.002+08:00

通常可愛的小孩會製造一些麻煩，例如說拿別人的東西總是不會歸回原位放好，如果拿了 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

2010-07-05T12:01:00.003+08:00

給你圓的半徑 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，牛與車

2010-07-04T18:48:00.011+08:00

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

牛數量	車數量	開門數	門總數
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，進位餘數

2010-07-03T12:40:00.002+08:00

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

首先將於除轉為 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，面積

2010-07-03T12:14:00.003+08:00

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

這題如果給你 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，最大宗教群

2010-07-03T11:43:00.003+08:00

此題與 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，最大朋友群

2010-07-03T00:09:00.004+08:00

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