1、目錄1.河內(nèi)之塔32.Algorithm Gossip: 費式數(shù)列43.巴斯卡三角形54.Algorithm Gossip: 三色棋65.Algorithm Gossip: 老鼠走迷官（一）86.Algorithm Gossip: 老鼠走迷官（二）107.Algorithm Gossip: 騎士走棋盤118.Algorithm Gossip: 八皇后149.Algorithm Gossip: 八枚銀幣1610.Algorithm Gossip: 生命游戲1811.Algorithm Gossip: 字串核對2112.Algorithm Gossip: 雙色、三色河內(nèi)塔2313.Algorith

2、m Gossip: 背包問題（Knapsack Problem）2714.Algorithm Gossip: 蒙地卡羅法求 PI3215.Algorithm Gossip: Eratosthenes篩選求質(zhì)數(shù)3316.Algorithm Gossip: 超長整數(shù)運算（大數(shù)運算）3517.Algorithm Gossip: 長 PI3718.Algorithm Gossip: 最大公因數(shù)、最小公倍數(shù)、因式分解4019.Algorithm Gossip: 完美數(shù)4320.Algorithm Gossip: 阿姆斯壯數(shù)4621.Algorithm Gossip: 最大訪客數(shù)4822.Algorith

3、m Gossip: 中序式轉(zhuǎn)后序式（前序式）5023.Algorithm Gossip: 后序式的運算5324.Algorithm Gossip: 洗撲克牌（亂數(shù)排列）5525.Algorithm Gossip: Craps賭博游戲5726.Algorithm Gossip: 約瑟夫問題（Josephus Problem）5927.Algorithm Gossip: 排列組合6128.Algorithm Gossip: 格雷碼（Gray Code）6329.Algorithm Gossip: 產(chǎn)生可能的集合6530.Algorithm Gossip: m元素集合的n個元素子集6831.Algo

4、rithm Gossip: 數(shù)字拆解7032.Algorithm Gossip: 得分排行7333.Algorithm Gossip: 選擇、插入、氣泡排序7534.Algorithm Gossip: Shell 排序法 - 改良的插入排序7935.Algorithm Gossip: Shaker 排序法 - 改良的氣泡排序8236.排序法 - 改良的選擇排序8437.Algorithm Gossip: 快速排序法（一）8838.Algorithm Gossip: 快速排序法（二）9039.Algorithm Gossip: 快速排序法（三）9240.Algorithm Gossip: 合并排

5、序法9541.Algorithm Gossip: 基數(shù)排序法9842.Algorithm Gossip: 循序搜尋法（使用衛(wèi)兵）10043.Algorithm Gossip: 二分搜尋法（搜尋原則的代表）10244.Algorithm Gossip: 插補搜尋法10545.Algorithm Gossip: 費氏搜尋法10846.Algorithm Gossip: 稀疏矩陣11247.Algorithm Gossip: 多維矩陣轉(zhuǎn)一維矩陣11448.Algorithm Gossip: 上三角、下三角、對稱矩陣11549.Algorithm Gossip: 奇數(shù)魔方陣11850.Algorith

6、m Gossip: 4N 魔方陣11951.Algorithm Gossip: 2(2N+1) 魔方陣1211.河內(nèi)之塔說明河內(nèi)之塔(Towers of Hanoi)是法國人M.Claus(Lucas)于1883年從泰國帶至法國的，河內(nèi)為越戰(zhàn)時北越的首都，即現(xiàn)在的胡志明市；1883年法國數(shù)學家 Edouard Lucas曾提及這個故事，據(jù)說創(chuàng)世紀時Benares有一座波羅教塔，是由三支鉆石棒（Pag）所支撐，開始時神在第一根棒上放置64個由上至下依由小至大排列的金盤（Disc），并命令僧侶將所有的金盤從第一根石棒移至第三根石棒，且搬運過程中遵守大盤子在小盤子之下的原則，若每日僅搬一個盤子，則當

7、盤子全數(shù)搬運完畢之時，此塔將毀損，而也就是世界末日來臨之時。解法如果柱子標為ABC，要由A搬至C，在只有一個盤子時，就將它直接搬至C，當有兩個盤子，就將B當作輔助柱。如果盤數(shù)超過2個，將第三個以下的盤子遮起來，就很簡單了，每次處理兩個盤子，也就是：A-B、A -C、B-C這三個步驟，而被遮住的部份，其實就是進入程式的遞回處理。事實上，若有n個盤子，則移動完畢所需之次數(shù)為2n - 1，所以當盤數(shù)為64時，則所需次數(shù)為：264- 1 = 為5.782e+16年，也就是約5000世紀，如果對這數(shù)字沒什幺概念，就假設每秒鐘搬一個盤子好了，也要約5850億年左右。 #include void hanoi

8、(int n, char A, char B, char C) if(n = 1) printf(Move sheet %d from %c to %cn, n, A, C); else hanoi(n-1, A, C, B); printf(Move sheet %d from %c to %cn, n, A, C); hanoi(n-1, B, A, C); int main() int n; printf(請輸入盤數(shù)：); scanf(%d, &n); hanoi(n, A, B, C); return 0; 2.Algorithm Gossip: 費式數(shù)列說明Fibonacci為120

9、0年代的歐洲數(shù)學家，在他的著作中曾經(jīng)提到：若有一只免子每個月生一只小免子，一個月后小免子也開始生產(chǎn)。起初只有一只免子，一個月后就有兩只免子，二個月后有三只免子，三個月后有五只免子（小免子投入生產(chǎn)）.。 如果不太理解這個例子的話，舉個圖就知道了，注意新生的小免子需一個月成長期才會投入生產(chǎn)，類似的道理也可以用于植物的生長，這就是Fibonacci數(shù)列，一般習慣稱之為費氏數(shù)列，例如以下： 1、1 、2、3、5、8、13、21、34、55、89. 解法依說明，我們可以將費氏數(shù)列定義為以下： fn = fn-1 + fn-2 if n 1fn = n if n = 0, 1 #include #incl

10、ude #define N 20 int main(void) int FibN = 0; int i; Fib0 = 0; Fib1 = 1; for(i = 2; i N; i+) Fibi = Fibi-1 + Fibi-2; for(i = 0; i N; i+) printf(%d , Fibi); printf(n); return 0; 3.巴斯卡三角形#include #define N 12long combi(int n, int r) int i; long p = 1; for(i = 1; i = r; i+) p = p * (n-i+1) / i; return

11、p;void paint() int n, r, t; for(n = 0; n = N; n+) for(r = 0; r = n; r+) int i;/* 排版設定開始 */ if(r = 0) for(i = 0; i = (N-n); i+) printf( ); else printf( ); /* 排版設定結(jié)束 */ printf(%3d, combi(n, r); printf(n); 4.Algorithm Gossip: 三色棋說明三色旗的問題最早由E.W.Dijkstra所提出，他所使用的用語為Dutch Nation Flag(Dijkstra為荷蘭人)，而多數(shù)的作者則

12、使用Three-Color Flag來稱之。假設有一條繩子，上面有紅、白、藍三種顏色的旗子，起初繩子上的旗子顏色并沒有順序，您希望將之分類，并排列為藍、白、紅的順序，要如何移動次數(shù)才會最少，注意您只能在繩子上進行這個動作，而且一次只能調(diào)換兩個旗子。解法在一條繩子上移動，在程式中也就意味只能使用一個陣列，而不使用其它的陣列來作輔助，問題的解法很簡單，您可以自己想像一下在移動旗子，從繩子開頭進行，遇到藍色往前移，遇到白色留在中間，遇到紅色往后移，如下所示：只是要讓移動次數(shù)最少的話，就要有些技巧：如果圖中W所在的位置為白色，則W+1，表示未處理的部份移至至白色群組。 如果W部份為藍色，則B與W的元素

13、對調(diào)，而B與W必須各+1，表示兩個群組都多了一個元素。 如果W所在的位置是紅色，則將W與R交換，但R要減1，表示未處理的部份減1。 注意B、W、R并不是三色旗的個數(shù)，它們只是一個移動的指標；什幺時候移動結(jié)束呢？一開始時未處理的R指標會是等于旗子的總數(shù)，當R的索引數(shù)減至少于W的索引數(shù)時，表示接下來的旗子就都是紅色了，此時就可以結(jié)束移動，如下所示：#include #include #include #define BLUE b #define WHITE w #define RED r #define SWAP(x, y) char temp; temp = colorx; colorx = c

14、olory; colory = temp; int main() char color = r, w, b, w, w, b, r, b, w, r, 0; int wFlag = 0; int bFlag = 0; int rFlag = strlen(color) - 1; int i; for(i = 0; i strlen(color); i+) printf(%c , colori); printf(n); while(wFlag = rFlag) if(colorwFlag = WHITE) wFlag+; else if(colorwFlag = BLUE) SWAP(bFlag

15、, wFlag); bFlag+; wFlag+; else while(wFlag rFlag & colorrFlag = RED) rFlag-; SWAP(rFlag, wFlag); rFlag-; for(i = 0; i strlen(color); i+) printf(%c , colori); printf(n); return 0; 5.Algorithm Gossip: 老鼠走迷官（一）說明老鼠走迷宮是遞回求解的基本題型，我們在二維陣列中使用2表示迷宮墻壁，使用1來表示老鼠的行走路徑，試以程式求出由入口至出口的路徑。解法老鼠的走法有上、左、下、右四個方向，在每前進一格之

16、后就選一個方向前進，無法前進時退回選擇下一個可前進方向，如此在陣列中依序測試四個方向，直到走到出口為止，這是遞回的基本題，請直接看程式應就可以理解。#include #include int visit(int, int); int maze77 = 2, 2, 2, 2, 2, 2, 2, 2, 0, 0, 0, 0, 0, 2, 2, 0, 2, 0, 2, 0, 2, 2, 0, 0, 2, 0, 2, 2, 2, 2, 0, 2, 0, 2, 2, 2, 0, 0, 0, 0, 0, 2, 2, 2, 2, 2, 2, 2, 2; int startI = 1, startJ = 1;

17、 / 入口int endI = 5, endJ = 5; / 出口int success = 0;int main(void) int i, j; printf(顯示迷宮：n); for(i = 0; i 7; i+) for(j = 0; j 7; j+) if(mazeij = 2) printf(); else printf( ); printf(n); if(visit(startI, startJ) = 0) printf(n沒有找到出口！n); else printf(n顯示路徑：n); for(i = 0; i 7; i+) for(j = 0; j 7; j+) if(maze

18、ij = 2) printf(); else if(mazeij = 1) printf(); else printf( ); printf(n); return 0; int visit(int i, int j) mazeij = 1; if(i = endI & j = endJ) success = 1; if(success != 1 & mazeij+1 = 0) visit(i, j+1); if(success != 1 & mazei+1j = 0) visit(i+1, j); if(success != 1 & mazeij-1 = 0) visit(i, j-1); i

19、f(success != 1 & mazei-1j = 0) visit(i-1, j); if(success != 1) mazeij = 0; return success; 6.Algorithm Gossip: 老鼠走迷官（二）說明由于迷宮的設計，老鼠走迷宮的入口至出口路徑可能不只一條，如何求出所有的路徑呢？解法求所有路徑看起來復雜但其實更簡單，只要在老鼠走至出口時顯示經(jīng)過的路徑，然后退回上一格重新選擇下一個位置繼續(xù)遞回就可以了，比求出單一路徑還簡單，我們的程式只要作一點修改就可以了。 #include #include void visit(int, int);int maze99

20、 = 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 0, 0, 0, 0, 0, 0, 0, 2, 2, 0, 2, 2, 0, 2, 2, 0, 2, 2, 0, 2, 0, 0, 2, 0, 0, 2, 2, 0, 2, 0, 2, 0, 2, 0, 2, 2, 0, 0, 0, 0, 0, 2, 0, 2, 2, 2, 0, 2, 2, 0, 2, 2, 2, 2, 0, 0, 0, 0, 0, 0, 0, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2;int startI = 1, startJ = 1; / 入口int endI = 7, endJ = 7;

21、 / 出口int main(void) int i, j; printf(顯示迷宮：n); for(i = 0; i 7; i+) for(j = 0; j 7; j+) if(mazeij = 2) printf(); else printf( ); printf(n); visit(startI, startJ); return 0; void visit(int i, int j) int m, n; mazeij = 1; if(i = endI & j = endJ) printf(n顯示路徑：n); for(m = 0; m 9; m+) for(n = 0; n 9; n+) i

22、f(mazemn = 2) printf(); else if(mazemn = 1) printf(); else printf( ); printf(n); if(mazeij+1 = 0) visit(i, j+1); if(mazei+1j = 0) visit(i+1, j); if(mazeij-1 = 0) visit(i, j-1); if(mazei-1j = 0) visit(i-1, j); mazeij = 0; 7.Algorithm Gossip: 騎士走棋盤說明騎士旅游（Knight tour）在十八世紀初倍受數(shù)學家與拼圖迷的注意，它什么時候被提出已不可考，騎士的

23、走法為西洋棋的走法，騎士可以由任一個位置出發(fā)，它要如何走完所有的位置？解法騎士的走法，基本上可以使用遞回來解決，但是純綷的遞回在維度大時相當沒有效率，一個聰明的解法由J.C. Warnsdorff在1823年提出，簡單的說，先將最難的位置走完，接下來的路就寬廣了，騎士所要走的下一步，為下一步再選擇時，所能走的步數(shù)最少的一步。，使用這個方法，在不使用遞回的情況下，可以有較高的機率找出走法（找不到走法的機會也是有的）。#include int board88 = 0; int main(void) int startx, starty; int i, j; printf(輸入起始點：); scan

24、f(%d %d, &startx, &starty); if(travel(startx, starty) printf(游歷完成！n); else printf(游歷失??！n); for(i = 0; i 8; i+) for(j = 0; j 8; j+) printf(%2d , boardij); putchar(n); return 0; int travel(int x, int y) / 對應騎士可走的八個方向 int ktmove18 = -2, -1, 1, 2, 2, 1, -1, -2; int ktmove28 = 1, 2, 2, 1, -1, -2, -2, -1;

25、 / 測試下一步的出路 int nexti8 = 0; int nextj8 = 0; / 記錄出路的個數(shù) int exists8 = 0; int i, j, k, m, l; int tmpi, tmpj; int count, min, tmp; i = x; j = y; boardij = 1; for(m = 2; m = 64; m+) for(l = 0; l 8; l+) existsl = 0; l = 0; / 試探八個方向 for(k = 0; k 8; k+) tmpi = i + ktmove1k; tmpj = j + ktmove2k; / 如果是邊界了，不可走

26、 if(tmpi 0 | tmpj 7 | tmpj 7) continue; / 如果這個方向可走，記錄下來 if(boardtmpitmpj = 0) nextil = tmpi; nextjl = tmpj; / 可走的方向加一個 l+; count = l; / 如果可走的方向為0個，返回 if(count = 0) return 0; else if(count = 1) / 只有一個可走的方向 / 所以直接是最少出路的方向 min = 0; else / 找出下一個位置的出路數(shù) for(l = 0; l count; l+) for(k = 0; k 8; k+) tmpi = n

27、extil + ktmove1k; tmpj = nextjl + ktmove2k; if(tmpi 0 | tmpj 7 | tmpj 7) continue; if(boardtmpitmpj = 0) existsl+; tmp = exists0; min = 0; / 從可走的方向中尋找最少出路的方向 for(l = 1; l count; l+) if(existsl tmp) tmp = existsl; min = l; / 走最少出路的方向 i = nextimin; j = nextjmin; boardij = m; return 1; 8.Algorithm Goss

28、ip: 八皇后說明西洋棋中的皇后可以直線前進，吃掉遇到的所有棋子，如果棋盤上有八個皇后，則這八個皇后如何相安無事的放置在棋盤上，1970年與1971年， E.W.Dijkstra與N.Wirth曾經(jīng)用這個問題來講解程式設計之技巧。解法關于棋盤的問題，都可以用遞回求解，然而如何減少遞回的次數(shù)？在八個皇后的問題中，不必要所有的格子都檢查過，例如若某列檢查過，該該列的其它格子就不用再檢查了，這個方法稱為分支修剪。#include #include #define N 8 int columnN+1; / 同欄是否有皇后，1表示有 int rup2*N+1; / 右上至左下是否有皇后 int lup2

29、*N+1; / 左上至右下是否有皇后 int queenN+1 = 0; int num; / 解答編號 void backtrack(int); / 遞回求解 int main(void) int i; num = 0; for(i = 1; i = N; i+) columni = 1; for(i = 1; i = 2*N; i+) rupi = lupi = 1; backtrack(1); return 0; void showAnswer() int x, y; printf(n解答 %dn, +num); for(y = 1; y = N; y+) for(x = 1; x N)

30、 showAnswer(); else for(j = 1; j = N; j+) if(columnj = 1 & rupi+j = 1 & lupi-j+N = 1) queeni = j; / 設定為占用 columnj = rupi+j = lupi-j+N = 0; backtrack(i+1); columnj = rupi+j = lupi-j+N = 1; 9.Algorithm Gossip: 八枚銀幣說明現(xiàn)有八枚銀幣a b c d e f g h，已知其中一枚是假幣，其重量不同于真幣，但不知是較輕或較重，如何使用天平以最少的比較次數(shù)，決定出哪枚是假幣，并得知假幣比真幣較輕或

31、較重。解法單就求假幣的問題是不難，但問題限制使用最少的比較次數(shù)，所以我們不能以單純的回圈比較來求解，我們可以使用決策樹（decision tree），使用分析與樹狀圖來協(xié)助求解。一個簡單的狀況是這樣的，我們比較a+b+c與d+e+f ，如果相等，則假幣必是g或h，我們先比較g或h哪個較重，如果g較重，再與a比較（a是真幣），如果g等于a，則g為真幣，則h為假幣，由于h比g輕而 g是真幣，則h假幣的重量比真幣輕。#include #include #include void compare(int, int, int, int); void eightcoins(int); int main(v

32、oid) int coins8 = 0; int i; srand(time(NULL); for(i = 0; i 8; i+) coinsi = 10; printf(n輸入假幣重量(比10大或小)：); scanf(%d, &i); coinsrand() % 8 = i; eightcoins(coins); printf(nn列出所有錢幣重量：); for(i = 0; i coinsk) printf(n假幣 %d 較重, i+1); else printf(n假幣 %d 較輕, j+1); void eightcoins(int coins) if(coins0+coins1+c

33、oins2 = coins3+coins4+coins5) if(coins6 coins7) compare(coins, 6, 7, 0); else compare(coins, 7, 6, 0); else if(coins0+coins1+coins2 coins3+coins4+coins5) if(coins0+coins3 = coins1+coins4) compare(coins, 2, 5, 0); else if(coins0+coins3 coins1+coins4) compare(coins, 0, 4, 1); if(coins0+coins3 coins1+c

34、oins4) compare(coins, 1, 3, 0); else if(coins0+coins1+coins2 coins1+coins4) compare(coins, 3, 1, 0); if(coins0+coins3 coins1+coins4) compare(coins, 4, 0, 1); 10.Algorithm Gossip: 生命游戲說明生命游戲（game of life）為1970年由英國數(shù)學家J. H. Conway所提出，某一細胞的鄰居包括上、下、左、右、左上、左下、右上與右下相鄰之細胞，游戲規(guī)則如下：孤單死亡：如果細胞的鄰居小于一個，則該細胞在下一次狀態(tài)將

35、死亡。 擁擠死亡：如果細胞的鄰居在四個以上，則該細胞在下一次狀態(tài)將死亡。 穩(wěn)定：如果細胞的鄰居為二個或三個，則下一次狀態(tài)為穩(wěn)定存活。 復活：如果某位置原無細胞存活，而該位置的鄰居為三個，則該位置將復活一細胞。解法生命游戲的規(guī)則可簡化為以下，并使用CASE比對即可使用程式實作：鄰居個數(shù)為0、1、4、5、6、7、8時，則該細胞下次狀態(tài)為死亡。 鄰居個數(shù)為2時，則該細胞下次狀態(tài)為復活。 鄰居個數(shù)為3時，則該細胞下次狀態(tài)為穩(wěn)定。 #include #include #include #define MAXROW 10 #define MAXCOL 25 #define DEAD 0 #define A

36、LIVE 1 int mapMAXROWMAXCOL, newmapMAXROWMAXCOL; void init(); int neighbors(int, int);void outputMap();void copyMap();int main() int row, col; char ans; init(); while(1) outputMap(); for(row = 0; row MAXROW; row+) for(col = 0; col MAXCOL; col+) switch (neighbors(row, col) case 0: case 1: case 4: case

37、 5: case 6: case 7: case 8: newmaprowcol = DEAD; break; case 2: newmaprowcol = maprowcol; break; case 3: newmaprowcol = ALIVE; break; copyMap(); printf(nContinue next Generation ? ); getchar(); ans = toupper(getchar(); if(ans != Y)break; return 0; void init() int row, col; for(row = 0; row MAXROW; r

38、ow+) for(col = 0; col MAXCOL; col+) maprowcol = DEAD; puts(Game of life Program); puts(Enter x, y where x, y is living cell); printf(0 = x = %d, 0 = y = %dn, MAXROW-1, MAXCOL-1); puts(Terminate with x, y = -1, -1); while(1) scanf(%d %d, &row, &col); if(0 = row & row MAXROW & 0 = col & col MAXCOL) ma

39、prowcol = ALIVE; else if(row = -1 | col = -1) break; else printf(x, y) exceeds map ranage!); int neighbors(int row, int col) int count = 0, c, r; for(r = row-1; r = row+1; r+) for(c = col-1; c = col+1; c+) if(r = MAXROW | c = MAXCOL) continue; if(maprc = ALIVE) count+; if(maprowcol = ALIVE) count-; return count; void outputMap() int row, col; printf(nn%20cGame of life cell statusn); for(row = 0; row MAXROW; row+) printf(n%20c, ); for(col = 0; col MAXCOL; col+) if(maprowcol = ALIVE) putchar(#); else putchar(-); void copyMa