目錄

1.河內(nèi)之塔.......................................................................3

2.AlgorithmGossip:費(fèi)式數(shù)歹U.............................................................................................................4

3.巴斯卡三角形...................................................................5

4.AlgorithmGossip:三色棋........................................................6

5.AlgorithmGossip:老鼠走迷官（一）...............................................8

6.AlgorithmGossip:老鼠走迷官（二）.............................................10

7.AlgorithmGossip:騎士走棋盤....................................................11

8.AlgorithmGossip:八皇后.......................................................14

9.AlgorithmGossip:八枚銀幣.....................................................16

10.AlgorithmGossip:生命游戲.....................................................18

11.AlgorithmGossip:字串核對(duì)......................................................21

12.AlgorithmGossip:雙色、三色河內(nèi)塔............................................23

13.AlgorithmGossip:背包問題（KnapsackProblem）.................................27

14.AlgorithmGossip:蒙地卡羅法求PI............................................................................................32

15.AlgorithmGossip:Eratosthenes篩選求質(zhì)數(shù)........................................33

16.AlgorithmGossip:超長整數(shù)運(yùn)算（大數(shù)運(yùn)算）....................................35

17.AlgorithmGossip:長PI................................................................................................................37

18.AlgorithmGossip:最大公因數(shù)、最小公倍數(shù)、因式分解............................40

19.AlgorithmGossip:完美數(shù)......................................................43

20.AlgorithmGossip:F可姆斯壯數(shù)..................................................46

21.AlgorithmGossip:最大訪客數(shù)....................................................48

22.AlgorithmGossip:中序式轉(zhuǎn)后序式（前序式）....................................50

23.AlgorithmGossip:后序式的運(yùn)算................................................53

24.AlgorithmGossip:洗撲克牌（亂數(shù)排列）........................................55

25.AlgorithmGossip:Craps賭博游戲................................................57

26.AlgorithmGossip:約瑟夫問題（JosephusProblem）................................................................59

27,AlgorithmGossip:排列組合......................................................61

28.AlgorithmGossip:格雷碼（GrayCode）...................................................................................63

29.AlgorithmGossip:產(chǎn)生可能的集合..............................................65

30.AlgorithmGossip:m元素集合的n個(gè)元素子集....................................68

31.AlgorithmGossip:數(shù)字拆解......................................................70

32.AlgorithmGossip:得分科F彳亍.....................................................73

33.AlgorithmGossip:選擇、插入、氣泡排序........................................75

34.AlgorithmGossip:Shell排序法-改良的插入排序.................................79

35,AlgorithmGossip:Shaker排序法?改良的氣泡排序................................82

36.排序法-改良的選擇排序......................................................84

37.AlgorithmGossip:快速排序法（一）............................................88

38.AlgorithmGossip:快速排序法（二）............................................90

39.AlgorithmGossip:快速：HF序法（三）............................................92

40.AlgorithmGossip:合并排序法..................................................95

41.AlgorithmGossip:基數(shù)排序法....................................................98

42,AlgorithmGossip:循序搜尋法（使用衛(wèi)兵）.......................................100

43.AlgorithmGossip:二分搜尋法（搜尋原則的代表）...............................102

44.AlgorithmGossip:插補(bǔ)搜尋法..................................................105

45.AlgorithmGossip:費(fèi)氏搜尋法..................................................108

46.AlgorithmGossip:稀疏矩陣...................................................112

47.AlgorithmGossip:多維矩陣轉(zhuǎn)一維矩陣.........................................114

48.AlgorithmGossip:上三角、下三角、對(duì)稱矩陣...................................115

49.AlgorithmGossip:奇數(shù)魔方陣..................................................118

50.AlgorithmGossip:4N魔方陣...................................................119

51.AlgorithmGossip:2（2N+1）魔方陣...............................................121

1.河內(nèi)之塔

說明河內(nèi)之塔(TowersofHanoi)是法國人M.Claus(Lucas)于1883年從泰國帶至法國的，河內(nèi)為越

戰(zhàn)時(shí)北越的首都，即現(xiàn)在的胡志明市；1883年法國數(shù)學(xué)家EdouardLucas曾提及這個(gè)故事，據(jù)說

創(chuàng)世紀(jì)時(shí)Benares有一座波羅教塔，是由三支鉆石棒(Pag)所支撐，開始時(shí)神在第一根棒上放

置64個(gè)由上至下依由小至大排列的金盤(Disc),并命令僧侶將所有的金盤從第一根石棒移至第

三根石棒，且搬運(yùn)過程中遵守大盤子在小盤子之下的原則，若每日僅搬一個(gè)盤子，則當(dāng)盤子全

數(shù)搬運(yùn)完畢之時(shí)，此塔將毀損，而也就是世界末日來臨之時(shí)。

解法如果柱子標(biāo)為ABC,要由A搬至C,在只有一個(gè)盤子時(shí)，就將它直接搬至C,當(dāng)有兩個(gè)盤

子，就將B當(dāng)作輔助柱。如果盤數(shù)超過2個(gè)，將第三個(gè)以下的盤子遮起來，就很簡單了，每次處

理兩個(gè)盤子，也就是：A->B、A->C、B->C這三個(gè)步驟，而被遮住的部份，其實(shí)就是進(jìn)入程式

的遞回處理。事實(shí)上，若有n個(gè)盤子，則移動(dòng)完畢所需之次數(shù)為2八n-1,所以當(dāng)盤數(shù)為64時(shí)，則

64

所需次數(shù)為:2-1=18446744073709551615為5.05390248594782C+16年，也就是約5000世紀(jì)，

如果對(duì)這數(shù)字沒什幺概念，就假設(shè)每秒鐘搬一個(gè)盤子好了，也要約5850億年左右。

#include<stdio.h>

voidhanoi(intn,charA,charB,charC){

if(n==1){

printf(nMovesheet%dfrom%cto%c\nM,n,A,C);

}

else{

hanoi(n-l,A,C,B);

printf(nMovesheet%dfrom%cto%c\nn,n,A,C);

hanoi(n-l,B,A,C);

}

)

intmain(){

intn;

printf(”請(qǐng)輸入盤數(shù)：”)；

scanf(',%dn,&n);

hanoi(n,'A/B'JC);

return0;

)

2.AlgorithmGossip:費(fèi)式數(shù)列

說明

Fibonacci為1200年代的歐洲數(shù)學(xué)家，在他的著作中曾經(jīng)提到：「若有一只免子每個(gè)月生一只小免

子，一個(gè)月后小免子也開始生產(chǎn)。起初只有一只免子，一個(gè)月后就有兩只免子，二個(gè)月后有三

只免子，三個(gè)月后有五只免子(小免子投入生產(chǎn))......。

如果不太理解這個(gè)例子的話，舉個(gè)圖就知道了，注意新生的小兔子需一個(gè)月成長期才會(huì)投入生

產(chǎn)，類似的道理也可以用于植物的生長，這就是Fibonacci數(shù)列，一般習(xí)慣稱之為費(fèi)氏數(shù)列，例

如以下：1、1、2、3、5、8、13、21、34、55、89......

解法

依說明，我們可以將費(fèi)氏數(shù)列定義為以下：

fn=fn-1+fn-2ifn>1

fn=nifn=0,1

#include<stdio.h>

#include<stdlib.h>

//defineN20

intmain(void){

intFib[N]={0};

inti;

Fib[0]=0;

Fib[l]=1;

for(i=2;i<N;i++)

Fib[i]=Fib[i-l]+Fib[i-2];

fbr(i=0;i<N;i-H-)

printf(M%dM,Fib[i]);

printf(n\nH);

return0;

3.巴斯卡三角形

#include<stdio.h>

#defineN12

longcombi(intn,intr){

inti;

longp=1;

fbr(i=l;i<=r;i++)

p=p*(n-i+l)/i;

returnp;

)

voidpaint(){

intn,r,t;

fbr(n=0;n<=N;n-H-){

fbr(r=0;r<=n;r++){

inti;/*排版設(shè)定開始*/

if(r=O){

for(i=0;i<=(N-n);i++)

printf,")；

}else{

printf(n”)；

}/*排版設(shè)定結(jié)束*/

printf(,,%3dn,combi(n,r));

printf(n\nn);

4.AlgorithmGossip:三色棋

說明

三色旗的問題最早由E.W.Dijkstra所提出，他所使用的用語為DutchNationFlag(Dijkstra為荷蘭

人)，而多數(shù)的作者則使用Three-ColorFlag來稱之。

假設(shè)有一條繩子，上面有紅、白、藍(lán)三種顏色的旗子，起初繩子上的旗子顏色并沒有順序，您

希望將之分類，并排列為藍(lán)、白、紅的順序，要如何移動(dòng)次數(shù)才會(huì)最少，注意您只能在繩子上

進(jìn)行這個(gè)動(dòng)作，而且一次只能調(diào)換兩個(gè)旗子。

解法

在一條繩子上移動(dòng)，在程式中也就意味只能使用一個(gè)陣列，而不使用其它的陣列來作輔助，問

題的解法很簡單，您可以自己想像一下在移動(dòng)旗子，從繩子開頭進(jìn)行，遇到藍(lán)色往前移，遇到

白色留在中間，遇到紅色往后移，如下所示：

只是要讓移動(dòng)次數(shù)最少的話，就要有些技巧：

如果圖中W所在的位置為白色，則W+1,表示未處理的部份移至至白色群組。

如果W部份為藍(lán)色，則B與W的元素對(duì)調(diào)，而B與W必須各+1,表示兩個(gè)群組都多了一個(gè)元素。

如果W所在的位置是紅色，則將W與R交換，但R要減1,表示未處理的部份減1。

注意B、W、R并不是三色旗的個(gè)數(shù)，它們只是一個(gè)移動(dòng)的指標(biāo)；什幺時(shí)候移動(dòng)結(jié)束呢？一開始

時(shí)未處理的R指標(biāo)會(huì)是等于旗子的總數(shù)，當(dāng)R的索引數(shù)減至少于W的索引數(shù)時(shí)，表示接下來的旗

子就都是紅色了，此時(shí)就可以結(jié)束移動(dòng)，如下所示：

^include<stdio.h>

#includc<stdlib.h>

//include<string.h>

//defineBLUEV

#defineWHITEV

#defineREDT'

#defineSWAP(x,y){chartemp;\

temp=color[x];\

color[x]=color[y];\

color[y]=temp;}

intmain(){

charcolor[]={Y*,fw\'b\*w',

b,T,bW"};

intwFlag=0;

intbFlag=0;

intrFlag=strlen(color)-1;

inti;

fbr(i=0;i<strlcn(color);i++)

printf(H%cM,color[i]);

printing”)；

while(wFlag<=rFlag){

if(color[wFlag]=WHITE)

wFlag++;

elseif(color[wFlag]=BLUE){

SWAP(bFlag,wFlag);

bFlag-H-;wFlag++;

}

else{

while(wFlag<rFlag&&color[rFlag]==RED)

rFlag-;

SWAP(rFlag,wFlag);

rFlag-;

for(i=0;i<strlen(color);i-H-)

printf(M%c”，color[i]);

printf(,,\n,');

return0;

5.AlgorithmGossip:老鼠走迷官（一）

說明老鼠走迷宮是遞回求解的基本題型，我們在二維陣列中使用2表示迷宮墻壁，使用1來表

示老鼠的行走路徑，試以程式求出由入口至出口的路徑。

解法老鼠的走法有上、左、下、右四個(gè)方向，在每前進(jìn)一格之后就選一個(gè)方向前進(jìn)，無法前

進(jìn)時(shí)退回選擇下一個(gè)可前進(jìn)方向，如此在陣列中依序測試四個(gè)方向，直到走到出口為止，這是

遞回的基本題，請(qǐng)直接看程式應(yīng)就可以理解。

#include<stdio.h>

#include<stdlib.h>

intvisit(int,int);

intmaze[7][7]={{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});

intstartl=1,startJ=1;〃入口

intendl=5,endJ=5;〃出口

intsuccess=0;

intmain(void){

inti,j;

printf("顯示迷宮：\nn);

fbr(i=0;i<7;i++){

for(j=0;j<7;j++)

if(maze[i]|j]=2)

printf(.")；

else

printf(n");

printf(n\nM);

if(visit(startl,startJ)=0)

printf(”\n沒有找到出口!\nn);

else{

printf("\n顯示路徑:\nM);

fbr(i=0;i<7;i++){

forG=0;j<7;j++){

if(maze[i][j]=2)

printf("|");

elseif(maze[i][j]=1)

printff。)；

else

printf(n”)；

}

return0;

)

intvisit(inti,intj){

maze[i][j]=1;

ififi=endl&&j=endJ)

success=1;

if(success!=1&&maze[i][j+l]=0)visit(i,j+1)；

if(success!=1&&maze[i+l][j]=0)visit(i+l,j);

if(success!=1&&maze[i][j-l]==0)visit(i,j-1);

if(success!=1&&maze[i-l][j]==0)visit(i-l,j);

ifl(success!=1)

maze[i][j]=0;

returnsuccess;

6.AlgorithmGossip:老鼠走迷官(二)

說明由于迷宮的設(shè)計(jì)，老鼠走迷宮的入口至出口路徑可能不只一條，如何求出所有的路徑呢？

解法求所有路徑看起來復(fù)雜但其實(shí)更簡單，只要在老鼠走至出口時(shí)顯示經(jīng)過的路徑，然后退

回上一格重新選擇下一個(gè)位置繼續(xù)遞回就可以了，比求出單?路徑還簡單，我們的程式只要作

一點(diǎn)修改就可以了。

#include<stdio.h>

#include<stdlib.h>

voidvisit(int,int);

intmaze[9][9]={{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}};

intstartl=1,startJ=1;〃入口

intendl=7,endJ=7;//出□

intmain(void){

inti,j;

printf("顯示迷宮：\n");

fbr(i=0;i<7;i++){

for(j=0;j<7;j++)

if(maze[i][j]——2)

printf("1");

else

printf("");

printf("\n");

visit(startl,startJ);

return0;

)

voidvisit(inti,intj){

intm,n;

maze[i][j]=1;

ifi[i=endl&&j=endJ){

printf("\n顯示路徑：\nn);

fbr(m=0;m<9;m++){

fbr(n=0;n<9;n-H-)

if(maze[m][n]=2)

printf("|");

elseifi(maze[m][n]==1)

printf(,,OH);

else

printf(H”)；

printf(n\nu);

if(maze[i][j+l]=0)visit(i,j+1);

if(maze[i+l][j]=0)visit(i+l,j);

if(maze[i][j-l]=0)visit(ij-l);

if(maze[i-l][j]=0)visit(i-l,j);

maze[i][j]=0;

)

7.AlgorithmGossip:騎士走棋盤

說明騎士旅游(Knighttour)在十八世紀(jì)初倍受數(shù)學(xué)家與拼圖迷的注意，它什么時(shí)候被提出

已不可考，騎士的走法為西洋棋的走法，騎士可以由任一個(gè)位置出發(fā)，它要如何走完[所有的位

置？

解法騎士的走法，基本上可以使用遞回來解決，但是純粹的遞回在維度大時(shí)相當(dāng)沒有效率，

一個(gè)聰明的解法由J.C.WamsdorfF在1823年提出，簡單的說，先將最難的位置走完，接下來的路

就寬廣了，騎士所要走的下一步，「為下一步再選擇時(shí)，所能走的步數(shù)最少的一步"，使用這個(gè)

方法，在不使用遞回的情況下，可以有較高的機(jī)率找出走法(找不到走法的機(jī)會(huì)也是有的)。

//include<stdio.h>

intboard[8][8]={0};

intmain(void){

intstartx,starty;

inti,j;

printf("輸入起始點(diǎn):");

scanfi(n%d%d”，&startx,&starty);

ifi(travel(startx,starty)){

printf("游歷完成！\n");

)

else(

printf("游歷失敗!\nH);

fbr(i=0;i<8;i++){

for(j=0;j<8;j++){

printfC%2d”,board[i][j]);

}

putchar('\n');

}

return0;

inttravel(intx,inty){

//對(duì)應(yīng)騎士可走的八個(gè)方向

intktmovel[8]={-2,-1,1,2,2,1,-1,-2);

intktmove2[8]={1,2,2,1,-1,-2,-2,-1);

//測試下一步的出路

intnexti[8]={0};

intnextj[8]={0};

//記錄出路的個(gè)數(shù)

intexists[8]={0};

inti,j,k,m,1;

inttmpi,tmpj;

intcount,min,tmp;

1=X；

j=y;

board[i][j]=1;

fbr(m=2;m<=64;m++){

fbr(l=0;1<8;1++)

existsfl]=0;

1=0;

//試探八個(gè)方向

for(k=0;k<8;k++){

tmpi=i+ktmovelfk];

tmpj=j+ktmove2[k];

//如果是邊界了，不可走

if(tmpi<0||tmpj<0||tmpi>7||tmpj>7)

continue;

//如果這個(gè)方向可走，記錄下來

ifi[board[tmpi][tmpj]==0){

nexti[l]=tmpi;

nextj[l]=tmpj;

〃可走的方向加一個(gè)

1++;

count=1;

〃如果可走的方向?yàn)?個(gè)，返回

ififcount==0){

return0;

}

elseififcount=1){

//只有一個(gè)可走的方向

//所以直接是最少出路的方向

min=0;

}

else{

//找出下一個(gè)位置的出路數(shù)

fbr(l=0;1<count;1++){

fbr(k=0;k<8;k-H-){

tmpi=nexti[l]+ktmovel[k];

tmpj=nextj[l]+ktmove2[k];

if^tinpi<0||tmpj<0||

tmpi>7||tmpj>7){

continue;

}

if(board[tmpi][tmpj]=0)

exists[l]-H-;

}

}

tmp=exists[0];

min=0;

//從可走的方向中尋找最少出路的方向

fbr(l=1;1<count;1++){

iftexists[l]<tmp){

tmp=exists。];

min=1;

//走最少出路的方向

i=nexti[min];

j=nextj[min];

board[i][j]=m;

}

return1;

8.AlgorithmGossip:八皇后

說明西洋棋中的皇后可以直線前進(jìn)，吃掉遇到的所有棋子，如果棋盤上有八個(gè)皇后，則這八

個(gè)皇后如何相安無事的放置在棋盤上，1970年與1971年，E.W.Dijkstra與N.Wirth曾經(jīng)用這個(gè)問

題來講解程式設(shè)計(jì)之技巧。

解法關(guān)于棋盤的問題，都可以用遞回求解，然而如何減少遞回的次數(shù)？在八個(gè)皇后的問題中，

不必要所有的格子都檢查過，例如若某列檢查過，該該列的其它格子就不用再檢查了，這個(gè)方

法稱為分支修剪。

#includc<stdio.h>

#include<stdlib.h>

//defineN8

intcolumn[N+l];//同欄是否有皇后，1表示有

intrup[2*N+l];//右上至左下是否有皇后

intlup[2*N+l];//左上至右下是否有皇后

intqueen[N+l]={0};

intnum;//解答編號(hào)

voidbacktrack(int);//遞回求解

intmain(void){

inti;

num=0;

for(i=l;i<=N;i++)

columnfi]=1;

fbr(i=1;i<=2*N;i++)

rup[i]=lup[i]=l;

backtrack(l);

return0;

}

voidshowAnswer(){

intx,y;

printf("\n解答%d\n",++num);

fbr(y=l;y<=N;y++){

fbr(x=1;x<=N;x++){

if(queen[y]==x){

printf(nQn);

else{

printf(H.M);

printf(n\nn);

voidbacktrack(inti){

intj;

if(\>N){

showAnswer();

}

else(

for(j=l；j<=N;j++){

ifi[column[j]=1&&

rup[i+j]==1&&lup[i-j+N]=1){

queen[i]=j;

//設(shè)定為占用

column[j]=rup[i-4]=lup[i-j+N]=0;

backtrack(i+l);

column[j]=rup[i-Fj]=lup[ij+N]=1;

9.AlgorithmGossip:八枚銀幣

說明現(xiàn)有八枚銀幣abcdefgh,已知其中枚是假幣，其重量不同于真幣，但不知是較輕或

較重，如何使用天平以最少的比較次數(shù)，決定出哪枚是假幣，并得知假幣比真幣較輕或較重。

解法單就求假幣的問題是不難，但問題限制使用最少的比較次數(shù)，所以我們不能以單純的回

圈比較來求解，我們可以使用決策樹(decisiontree),使用分析與樹狀圖來協(xié)助求解。一個(gè)簡單

的狀況是這樣的，我們比較a+b+c與d+e+f,如果相等，則假幣必是g或h,我們先比較g或h哪個(gè)

較重，如果g較重，再與a比較(a是真幣)，如果g等于a,則g為真幣，貝此為假幣，由于h比g輕

而g是真幣，貝此假幣的重量比真幣輕。

#include<stdio.h>

#includc<stdlib.h>

//include<time.h>

voidcompare(int[],int,int,int);

voideightcoins(int[]);

intmain(void){

intcoins[8]={0};

inti;

srand(time(NULL));

fdr(i=0;i<8;i++)

coins[i]=10;

printff\n輸入假幣重量(比10大或小)：”);

scanf(n%dM,&i);

coins[rand()%8]=i;

eightcoins(coins);

printf("\n\n列出所有錢幣重量：”)；

fbr(i=0;i<8;i++)

printf(H%d”,coins[i]);

printf(n\nu);

return0;

)

voidcompare(intcoins[],inti,intj,intk){

if(coins[i]>coins[k])

printf("\n假幣%d較重”,i+1);

else

printf(”\n假幣%d較輕”,j+l);

}

voideightcoins(intcoinsf]){

if(coins[0]+coins[1]+coins[2]=

coins[3]+coins[4]+coins[5]){

if(coins[6]>coins[7])

comparc(coins,6,7,0);

else

compare(coins,7,6,0);

}

elseif(coins[0]+coins[1]+coins[2]>

coins[3]+coins[4]+coins[5]){

if(coins[0]+coins[3]=coins[l]+coins[4])

compare(coins,2,5,0);

elseif(coins[0]+coins[3]>coins[l]+coins[4])

compare(coins,0,4,1);

if(coins[0]+coins[3]<coins[l]+coins[4])

comparc(coins,1,3,0);

}

elseif(coins[0]+coins[1]+coins[2]<

coins[3]+coins[4]+coins[5]){

if(coins[0]+coins[3]=coins[l]+coins[4])

compare(coins,5,2,0);

elseif(coins[0]+coins[3]>coins[1]+coins[4])

compare(coins,3,1,0);

if(coins[0]+coins[3]<coins[l]+coins[4])

compare(coins,4,0,1);

lO.AlgorithmGossip:生命游戲

說明生命游戲(gameoflife)為1970年由英國數(shù)學(xué)家J.H.Conway所提出，某一細(xì)胞的鄰居包

括上、下、左、右、左上、左下、右上與右下相鄰之細(xì)胞，游戲規(guī)則如下：

孤單死亡：如果細(xì)胞的鄰居小于一個(gè)，則該細(xì)胞在下一次狀態(tài)將死亡。

擁擠死亡：如果細(xì)胞的鄰居在四個(gè)以上，則該細(xì)胞在下一次狀態(tài)招死亡。

穩(wěn)定：如果細(xì)胞的鄰居為二個(gè)或三個(gè)，則下一次狀態(tài)為穩(wěn)定存活。

復(fù)活：如果某位置原無細(xì)胞存活，而該位置的鄰居為三個(gè)，則該位置將復(fù)活一細(xì)胞。

解法生命游戲的規(guī)則可簡化為以下，并使用CASE比對(duì)即可使用程式實(shí)作：

鄰居個(gè)數(shù)為0、1、4、5、6、7、8時(shí)，則該細(xì)胞下次狀態(tài)為死亡。

鄰居個(gè)數(shù)為2時(shí)，則該細(xì)胞下次狀態(tài)為復(fù)活。

鄰居個(gè)數(shù)為3時(shí)，則該細(xì)胞下次狀態(tài)為穩(wěn)定。

#include<stdio.h>

#include<stdlib.h>

#include<ctype.h>

//defineMAXROW10

#defineMAXCOL25

^defineDEAD0

#defineALIVE1

intmap[MAXROW][MAXCOL],newmap[MAXROW][MAXCOL];

voidinit();

intneighbors(int,int);

voidoutputMap();

voidcopyMap();

intmain(){

introw,col;

charans;

init();

while(l){

outputMap();

fbr(row=0;row<MAXROW;row-H-){

fbr(col=0;col<MAXCOL;col++){

switch(neighbors(row,col)){

case0:

case1:

case4:

case5:

case6:

case7:

case8:

newmap[row][col]=DEAD;

break;

case2:

newmap[row][col]=map[row][col];

break;

case3:

newmap[row][col]=ALIVE;

break;

copyMap();

printfi(n\nContinuenextGeneration?")；

getchar();

ans=toupper(getchar());

if(ans!='Y')break;

)

return0;

)

voidinit(){

introw,col;

fbr(row=0;row<MAXROW;row-H-)

fdr(col=0;col<MAXCOL;col++)

map[row][col]=DEAD;

puts(nGameoflifeProgram**);

puts(nEnterx,ywherex,yislivingcell”)；

printffO<=x<=%d,0<=y<=%d\nu,

MAXROW-1,MAXCOL-1);

puts(nTerminatewithx,y=-1,-ln);

while(l){

scanf(n%d%dM,&row,&col);

if(0<=row&&row<MAXROW&&

0<=col&&col<MAXCOL)

map[row][col]=ALIVE;

elseif(row==-1||col=-1)

break;

else

printf{n(x,y)exceedsmapranage!**);

)

}

intneighbors(introw,intcol){

intcount=0,c,r;

fbr(r=row-1;r<=row+1;r++)

fbr(c=col-1;c<=col+1;C++){

ifi(r<0||r>=MAXROW||c<0||c>=MAXCOL)

continue;

ifi(map[r][c]=ALIVE)

count-H-；

)

if(map[row][col]=ALIVE)

count-;

returncount;

)

voidoutputMap(){

introw,col;

printf(n\n\n%20cGameoflifecellstatus\nH);

fbr(row=0;row<MAXROW;row++){

printf(,,\n%20c\'');

fdr(col=0;col<MAXCOL;col++)

if(map[row][col]==ALIVE)putchar('#,);

elseputcharC*-*);

voidcopyMap(){

introw,col;

fbr(row=0;row<MAXROW;row-H-)

fbr(col=0;col<MAXCOL;col-H-)

map[row][col]=newmap[row][col];

}

ll.AlgorithmGossip:字串核對(duì)

說明今日的一些高階程式語言對(duì)于字串的處理支援越來越強(qiáng)大(例如Java、Perl等)，不過字

串搜尋本身仍是個(gè)值得探討的課題，在這邊以Boyer-Moore法來說明如何進(jìn)行字串說明，這個(gè)

方法快旦原理簡潔易懂。

解法字串搜尋本身不難，使用暴力法也可以求解，但如何快速搜尋字串就不簡單了，傳統(tǒng)的

字串搜尋是從關(guān)鍵字與字串的開頭開始比對(duì)，例如Knuth-Morris-Pratt演算法字串搜尋，這個(gè)

方法也不錯(cuò)，不過要花時(shí)間在公式計(jì)算上；Boyer-Moore字串核對(duì)改由關(guān)鍵字的后面開始核對(duì)字

串，并制作前進(jìn)表，如果比對(duì)不符合則依前進(jìn)表中的值前進(jìn)至下一個(gè)核對(duì)處，假設(shè)是p好了，然

后比對(duì)字串中p-n+1至p的值是否與關(guān)鍵字相同。

如果關(guān)鍵字中有重復(fù)出現(xiàn)的字元，則前進(jìn)值就會(huì)有兩個(gè)以上的值，此時(shí)則取前進(jìn)值較小的值，

如此就不會(huì)跳過可能的位置，例如texture這個(gè)關(guān)鍵字，t的前進(jìn)值應(yīng)該取后面的3而不是取前面的

7o

#include<stdio.h>

#include<stdlib.h>

#include<string.h>

voidtable(char*);//建立前進(jìn)表

intsearch(int,char*,char*);//搜尋關(guān)鍵字

voidsubstring(char*,char*,int,int);//取出子字串

intskip[256];

intmain(void){

charstr_input[8O];

charstr_key[8O];

chartmp[80]={'O'}；

intm,n,p;

printf("請(qǐng)輸入字串：”)；

gets(str_input);

printf(”請(qǐng)輸入搜尋關(guān)鍵字：”)；

gets(str_key);

m=strlen(strinput);//計(jì)算字串長度

n=strlen(str_key);

table(str_key);

p=search(n-1,strinput,str_key);

while(p!=-1){

substring(str_input,tmp,p,m);

printf(n%s\nH,tmp);

p=search(p+n+l,strinput,str_key);

)

printf(n\nH);

return0;

)

voidtable(char*key){

intk,n;

n=strlen(key);

for(k=0;k<=255;k++)

skip[k]=n;

for(k=0;k<n-1;k++)

skip[key[k]]=n-k-1;

)

intsearch(intp,char*input,char*key){

inti,in,n;

chartmp[80]={W};

m=strlcn(input);

n=strlen(key);

while(p<m){

substring(input,tmp,p-n+1,p);

if(!strcmp(tmp,key))//比較兩字串是否相同

returnp-n+1；

p+=skip[input[p]];

}

return-1;

}

voidsubstring(char*text,char*tmp,ints,inte){

inti,j;

fbr(i=s,j=0;i<=e;i-H-,j-H-)

mp[j]=text[i];

tmp[j]='\0';

)

12.AlgorithmGossip:雙色、三色河內(nèi)塔

說明雙色河內(nèi)塔與三色河內(nèi)塔是由之前所介紹過的河內(nèi)塔規(guī)則衍生而來，雙色河內(nèi)塔的目的

是將下圖左上的圓環(huán)位置經(jīng)移動(dòng)成為右下的圓環(huán)位置:

而三色河內(nèi)塔則是將下圖左上的圓環(huán)經(jīng)移動(dòng)成為右上的圓環(huán):

直II

解法無論是雙色河內(nèi)塔或是三色河內(nèi)塔，其解法觀念與之前介紹過的河內(nèi)塔是類似的，同樣

也是使用遞回來解，不過這次遞回解法的目的不同，我們先來看只有兩個(gè)盤的情況，這很簡單,

只要將第一柱的黃色移動(dòng)至第二柱，而接下來第一柱的藍(lán)色移動(dòng)至第三柱。

再來是四個(gè)盤的情況，首先必須用遞回完成下圖左上至右下的移動(dòng)：

接下來最底層的就不用管它們了，因?yàn)樗鼈円呀?jīng)就定位，只要再處理第一柱的上面兩個(gè)盤子就

可以了。那么六個(gè)盤的情況呢？一樣！首先必須用遞回完成下圖左上至右下的移動(dòng)：

接下來最底層的就不用管它們了，因?yàn)樗鼈円呀?jīng)就定位，只要再處理第一柱上面的四個(gè)盤子就

可以了，這又與之前只有四盤的情況相同，接下來您就知道該如何進(jìn)行解題了，無論是八個(gè)盤、

十個(gè)盤以上等，都是用這個(gè)觀念來解題。

那么三色河內(nèi)塔呢？一樣，直接來看九個(gè)盤的情況，首先必須完成下圖的移動(dòng)結(jié)果：

接下來最底兩層的就不用管它們了，因?yàn)樗鼈円呀?jīng)就定位，只要再處理第一柱上面的三個(gè)盤子

就可以了。

雙色河內(nèi)塔c實(shí)作

#include<stdio.h>

voidhanoi(intdisks,charsource,chartemp,chartarget){

if(disks=1){

printf(,,movediskfrom%cto%c\nn,source,target);

printff'movediskfrom%cto%c\nn,source,target);

}else{

hanoi(disks-l,source,target,temp);

hanoi(l,source,temp,target);

hanoi(disks-l,temp,source,target);

voidhanoi2colors(intdisks){

charsource='A';

chartemp='B';

chartarget='C;

inti;

fbr(i=disks/2;i>1;i-){

hanoi(i-l,source,temp,target);

printff'movediskfrom%cto%c\nn,source,temp);

printff'movediskfrom%cto%c\nn,source,temp);

hanoi(i-l,target,temp,source);

printsnmovediskfrom%cto%c\nH,temp,target);

}

printff'movediskfrom%cto%c\nM,source,temp);

printff'movediskfrom%cto%c\nM,source,target);

intmain(){

intn;

printf(”請(qǐng)輸入盤數(shù)：”);

scanf(M%dn,&n);

hanoi2colors(n);

return0;

三色河內(nèi)塔C實(shí)作

#include<stdio.h>

voidhanoi(intdisks,charsource,chartemp,chartarget){

if(disks=1){

printf(nmovediskfrom%cto%c\nn,source,target);

printf(nmovediskfrom%cto%c\nn,source,target);

printff'movediskfrom%cto%c\nn,source,target);

}else{

hanoi(disks-l,source,target,temp);

hanoi(1,source,temp,target);

hanoi(disks-l,temp,source,target);

voidhanoi3colors(intdisks){

charsource=*A*;

chartemp=B;

chartarget=*Cf;

inti;

iRdisks=3){

printff'movediskfrom%cto%c\nn,source,temp);

prints"movediskfrom%cto%c\nn,source,temp);

printf(nmovediskfrom%cto%c\nH,source,target);

printf(nmovediskfrom%cto%c\nM,temp,target);

printff'movediskfrom%cto%c\nn,temp,source);

printf(nmovediskfrom%cto%c\nn,target,temp);;

}

else{

hanoi(disks/3-l,source,temp,target);

printfi(nmovediskfrom%cto%c\nH,source,temp);

printff'movediskfrom%cto%c\nH,source,temp);

printf(nmovediskfrom%cto%c\n”，source,temp);

hanoi(disks/3-l,target,temp,source);

printfi(nmovediskfrom%cto%c\nn,temp,target);

printf(nmovcdiskfrom%cto%c\nH,temp,target);

printf(,,movediskfrom%cto%c\nn,temp,target);

hanoi(disks/3-1,source,target,temp);

printff'movediskfrom%cto%c\nH,target,source);

printfV'movediskfrom%cto%c\nH,target,source);

hanoi(disks/3-l,temp,source,target);

printf(Mmovediskfrom%cto%c\nM,source,temp);

for(i=disks/3-1;i>0;i—){

if(i>l){

hanoi(i-l,target,source,temp);

}

printfi(nmovediskfrom%cto%c\nn,target,source);

printff'movediskfrom%cto%c\n”,target,source);

if(i>l){

hanoi(i-l,temp,source,target);

)

printff'movediskfrom%cto%c\nn,source,temp);

intinain(){

intn;

printR”請(qǐng)輸入盤數(shù):?');

scanf("％d”，&n);

hanoi3colors(n);

return0;

13.AlgorithmGossip:背包問題(KnapsackProblem)

說明假設(shè)有?個(gè)背包的負(fù)重最多可達(dá)8公斤，而希望在背包中裝入負(fù)重范圍內(nèi)可得之總價(jià)物

品，假設(shè)是水果好了，水果的編號(hào)、單價(jià)與重量如下所示:

0李子4KGNT