經(jīng)典算法(C語言)

1.漢若塔..............................................................................2

2.費式數(shù)列............................................................................2

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

4.三色棋..............................................................................4

5.老鼠走迷官（一）....................................................................6

6.老鼠走迷官（二）....................................................................7

7.騎士走棋盤..........................................................................9

8.八皇后.............................................................................11

9.八枚銀幣...........................................................................13

10.生命游戲..........................................................................14

11.字串核對..........................................................................17

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

13.背包問題（KnapsackProblem）......................................................22

14.蒙地卡羅法求PI......................................................................................................................................25

15.Eratosthenes篩選求質(zhì)數(shù).............................................................26

16.超長整數(shù)運算（大數(shù)運算）.........................................................28

17.長PI............................................................................................................................................................29

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

19.完美數(shù)............................................................................34

20.阿姆斯壯數(shù)........................................................................37

21.最大訪客數(shù)........................................................................38

22.中序式轉(zhuǎn)后序式（前序式）.........................................................40

23.后序式的運算......................................................................42

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

25.Craps賭博游戲.....................................................................46

26.約瑟夫問題（JosephusProblem）.........................................................................................................47

27.排列組合..........................................................................49

28.格雷碼（GrayCode）..............................................................................................................................50

29.產(chǎn)生可能的集合....................................................................52

30.m元素集合的n個元素子集.........................................................54

31.數(shù)字拆解..........................................................................56

32.得分排行..........................................................................58

33.選擇、插入、氣泡排序.............................................................60

34.Shell排序法-改良的插入排序.......................................................63

35.Shaker排序法-改良的氣泡排序......................................................65

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

37.快速排序法（一）.................................................................70

38.快速排序法（二）.................................................................72

39.快速排序法（三）.................................................................73

40.合并排序法........................................................................76

41.基數(shù)排序法........................................................................78

42.循序搜尋法（使用衛(wèi)兵）...........................................................80

43.二分搜尋法（搜尋原則的代表）.....................................................82

44.插補(bǔ)搜尋法........................................................................84

45.費氏搜尋法........................................................................87

46.稀疏矩陣..........................................................................90

47.多維矩陣轉(zhuǎn)一維矩陣...............................................................91

48.上三角、下三角、對稱矩陣.........................................................93

49.奇數(shù)魔方陣........................................................................95

50.4N魔方陣..........................................................................96

51.2(2N+1)魔方陣97

1.漢若塔

說明河內(nèi)之塔（1'0亞6躇0{1142110。是法國人乂.。2網(wǎng)11^$）于1883年從泰國帶至法國的，河內(nèi)為越戰(zhàn)時北越的首都，即現(xiàn)在的胡

志明市；1883年法國數(shù)學(xué)家EdouardLucas曾提及這個故事，據(jù)說創(chuàng)世紀(jì)時Benares有一座波羅教塔，是由三支鉆石棒（Pag）

所支撐，開始時神在第一根棒上放置64個由上至下依由小至大排列的金盤（Disc）,并命令僧侶將所有的金盤從第一根石棒移

至第三根石棒，且搬運過程中遵守大盤子在小盤子之下的原則，若每日僅搬一個盤子，則當(dāng)盤子全數(shù)搬運完畢之時，此塔將

毀損，而也就是世界末日來臨之時。

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

數(shù)超過2個，將第三個以下的盤子遮起來，就很簡單了，每次處理兩個盤子，也就是：A->B,A->C、B->C這三個步驟，而被

遮住的部份，其實就是進(jìn)入程式的遞回處理。事實上，若有n個盤子，則移動完畢所需之次數(shù)為2八n-1,所以當(dāng)盤數(shù)為64時，

64

則所需次數(shù)為:2-1=18446744073709551615為5.05390248594782e+16年，也就是約5000世紀(jì),如果對這數(shù)字沒什幺概念,

就假設(shè)每秒鐘搬一個盤子好了，也要約5850億年左右。

#include<stdio.h>

voidhanoi(intn,charA,charB,charC){

ififn=1){

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

else(

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

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

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

intmain(){

intn;

printf("請輸入盤數(shù)：");

scanf("％d”,&n);

hanoi(n,

return0;

2.費式數(shù)列

說明

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

產(chǎn)。起初只有一只免子，一個月后就有兩只免子，二個月后有三只免子，三個月后有五只免子（小免子投入生產(chǎn)）……?

如果不太理解這個例子的話，舉個圖就知道了，注意新生的小免子需一個月成長期才會投入生產(chǎn)，類似的道理也可以用于植

物的生長，這就是Fibonacci數(shù)列，一般習(xí)慣稱之為費氏數(shù)列，例如以下：1、1、2、3、5、8、13、21、34、55、89

解法

依說明，我們可以將費氏數(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[O]=0;

Fib[l]=1;

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

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

for(i=0；i<N;i++)

printf(,f%d",Fib[i]);

printf(”\n”)；

return0;

3.巴斯卡三角形

#include<stdio.h>

#defineN12

longcombi(intn,intr){

inti;

longp=1;

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

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

returnp;

)

voidpaint(){

intn,r,t;

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

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

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

if(r=O){

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

pr血”)；

}else{

printff”)；

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

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

}

printf(',\nM);

4.三色棋

說明

三色旗的問題最早由E.W.Dijkstra所提出，他所使用的用語為DutchNationFlag（Dijkstra為荷蘭人），而多數(shù)的作者則使用

Three-ColorFlag來稱之。

假設(shè)有一條繩子，上面有紅、白、藍(lán)三種顏色的旗子，起初繩子上的旗子顏色并沒有順序，您希望將之分類，并排列為藍(lán)、

白、紅的順序，要如何移動次數(shù)才會最少，注意您只能在繩子上進(jìn)行這個動作，而且一次只能調(diào)換兩個旗子。

解法

在一條繩子上移動，在程式中也就意味只能使用一個陣列，而不使用其它的陣列來作輔助，問題的解法很簡單，您可以自己

想像一下在移動旗子，從繩子開頭進(jìn)行，遇到藍(lán)色往前移，遇到白色留在中間，遇到紅色往后移，如下所示：

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

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

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

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

注意B、W、R并不是三色旗的個數(shù)，它們只是?個移動的指標(biāo)；什幺時候移動結(jié)束呢？一開始時未處理的R指標(biāo)會是等于旗

子的總數(shù)，當(dāng)R的索引數(shù)減至少于W的索引數(shù)時，表示接下來的旗子就都是紅色了，此時就可以結(jié)束移動，如下所示：

#include<stdio.h>

#include<stdlib.h>

#include<string.h>

#defineBLUEV

#defineWHITE*

#defineREDF

#defineSWAP(x,y){chartemp;\

temp=color[x];\

color[x]=color[y];\

color[y]=temp;}

intmain(){

charcolor[]={'r',bJw','w‘,

intwFlag=0;

intbFlag=0;

intrFlag=strlen(color)-1;

inti;

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

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

printf(n\nH);

while(wFlag<=rFlag){

if(color[wFlag]==WHITE)

wFlag++;

elseif(color[wFlag]==BLUE){

SWAP(bFIag,wFlag);

bFlag++;wFlag++;

}

else(

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

rFlag-;

SWAP(rFlag,wFlag);

rFlag-;

)

)

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

printf(n%c”,color[i]);

printf(M\nH);

return0;

5.老鼠走迷官（一）

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

求出由入口至出口的路徑。

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

向，如此在陣列中依序測試四個方向，直到走到出口為止，這是遞回的基本題，請直接看程式應(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){

intij;

printff顯示迷宮：\nH);

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

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

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

printfC'l");

else

printfC”)；

printf(M\nM);

if(visit(startl,startJ)=0)

printf(”\n沒有找到出口！\n");

else{

primf(”\n顯示路徑:\nn);

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

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

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

printf("|");

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

printffO”)；

else

printf(M”);

}

printff\n")；

return0;

}

intvisit(inti,intj){

maze[i][j]=1;

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

success=1;

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

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

ififsuccess!=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]=0;

returnsuccess;

}

6.老鼠走迷官(二)

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

解法求所有路徑看起來復(fù)雜但其實更簡單，只要在老鼠走至出口時顯示經(jīng)過的路徑，然后退回上一格重新選擇卜?個位置

繼續(xù)遞回就可以了，比求出單一路徑還簡單，我們的程式只要作一點修改就可以了。

#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){

intij;

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

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

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

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

printf(H|n);

else

printff")；

printf(n\nn);

}

visit(startl,startJ);

return0;

}

voidvisit(inti,intj){

intm,n;

maze[i][j]=1;

if(i=endl&&j==endJ){

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

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

fbr(n=0;n<9;n++)

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

printf("|");

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

printf(HOH);

else

printf(H”)；

printffW”)；

}

}

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

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

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

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

maze[i][j]=0;

7.騎士走棋盤

說明騎士旅游(Knighttour)在十八世紀(jì)初倍受數(shù)學(xué)家與拼圖迷的注意，它什么時候被提出已不可考，騎士的走法為西洋棋

的走法，騎士可以由任一個位置出發(fā)，它要如何走完[所有的位置？

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

在1823年提出，簡單的說，先將最難的位置走完，接下來的路就寬廣了，騎士所要走的下一步，「為下一步再選擇時，所能走

的步數(shù)最少的一步。」，使用這個方法，在不使用遞回的情況下，可以有較高的機(jī)率找出走法(找不到走法的機(jī)會也是有的)。

#include<stdio.h>

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

intmain(void){

intstartx,starty;

intij;

prints輸入起始點:")；

scanf(,,%d%d",&startx,&starty);

if{travel(startx,starty)){

print」游歷完成!\n");

}

else{

printf("游歷失??！\nM);

}

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

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

printff%2d”,board[i][j])；

)

putchar('\n*);

}

return0;

}

inttravel(intx,inty){

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

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

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

intexists[8]={0};

inti,j,k,m,1;

inttmpi,tmpj;

intcount,min,tmp;

i=x;

j=y;

board[i][j]=1;

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

for(l=0;l<8;1-H-)

exists[l]=0;

1=0;

〃試探八個方向

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

tmpi=i+ktmovel[k];

tmpj=j+ktmove2[k];

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

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

continue;

//如果這個方向可走，記錄下來

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

nexti[l]=tmpi;

nextj[l]=tmpj;

//可走的方向加一個

1++；

count=1;

//如果可走的方向為0個，返回

ififcount==0){

return0;

}

elseif(count=1){

//只有一個可走的方向

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

min=0;

}

else{

〃找出下一個位置的出路數(shù)

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

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

tmpi=nextifl]+ktmovel[k];

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

if(tmpi<0||tmpj<0||

tmpi>7||tmpj>7){

continue;

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

exists[l]++;

tmp=exists[O];

min=0;

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

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

if(exists[l]<tmp){

tmp=exists[l];

min=1;

)

}

}

//走最少出路的方向

i=nexti[min];

j=nextjfmin];

board[i][j]=m;

}

return1;

}

8.八皇后

說明西洋棋中的皇后可以直線前進(jìn)，吃掉遇到的所有棋子，如果棋盤上有八個皇后，則這八個皇后如何相安無事的放置在

棋盤上，1970年與1971年，E.W.Dijkstra與N.Wirth曾經(jīng)用這個問題來講解程式設(shè)計之技巧。

解法關(guān)于棋盤的問題，都可以用遞回求解，然而如何減少遞回的次數(shù)？在八個皇后的問題中，不必要所有的格子都檢查過,

例如若某列檢查過，該該列的其它格子就不用再檢查了，這個方法稱為分支修剪。

#include<stdio.h>

#include<stdlib.h>

#defineN8

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

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

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

intqueen[N+l]={0};

intnum;//解答編號

voidbacktrack(int);//遞回求解

intmain(void){

inti;

num=0;

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

column[i]=1;

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

rup[i]=lup[i]=1;

backtrack(l);

return0;

)

voidshowAnswer(){

intx,y;

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

fbr(y=1;y<=N;y-H-){

fbr(x=1;x<=N;x-H-){

ifl(queen[y]==x){

printffQn);

}

else{

printffJ);

}

)

printf("\n)

voidbacktrack(inti){

intj;

if(i>N){

showAnswer();

}

else(

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

iRcolumnfj]=1&&

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

queen[i]=j;

//設(shè)定為占用

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

backtrack(i+l);

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

9.八枚銀幣

說明現(xiàn)有八枚銀幣abcdefgh,已知其中一枚是假幣，其重量不同于真幣，但不知是較輕或較重，如何使用天平以最少的

比較次數(shù)，決定出哪枚是假幣，并得知假幣比真幣較輕或較重。

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

決策樹(decisiontree),使用分析與樹狀圖來協(xié)助求解。一個簡單的狀況是這樣的，我們比較a+b+c與d+e+f,如果相等，則

假幣必是g或h,我們先比較g或h哪個較重，如果g較重，再與a比較(a是真幣)，如果g等于a,則g為真幣，則h為假幣，由于h

比g輕而g是真幣，則h假幣的重量比真幣輕。

#include<stdio.h>

#include<stdlib.h>

#include<time.h>

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

voideightcoins(int[]);

intmain(void){

intcoins[8]={0};

inti;

srand(time(NULL));

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

coins[i]=10;

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

scanf(n%dn,&i);

coins[rand()%8]=i;

eightcoins(coins);

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

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

printf(,f%d",coins[i]);

printf(M\nM);

return0;

}

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

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

printfCn假幣%d較重”,i+1);

else

prin氓”\n假幣%d較輕”,j+1);

)

voidcightcoins(intcoins[]){

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

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

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

compare(coins,6,7,0);

else

compare(coins,7,6,0);

)

elseifl(coins[0]4-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])

compare(coins,1,3,0);

}

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

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

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

compare(coins,5,2,0);

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

compare(coins,3,1,0);

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

compare(coins,4,0,1);

10.生命游戲

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

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

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

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

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

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

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

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

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

鄰居個數(shù)為3時，則該細(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++){

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();

printff'\nContinuenextGeneration?”)；

getchar();

ans=toupper(getchar());

if(ans!=Y)break;

}

return0;

}

voidinit(){

introw,col;

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

for(col=0;col<MAXCOL;coH-+)

map[row][col]=DEAD;

puts("GameoflifeProgram");

puts("Enterx,ywherex,yislivingcell”)；

printf(nO<=x<=%d,0<=y<=%d\n”，

MAXROW-1,MAXCOL-1);

puts("Terminatewithx,y=-1,-ln);

while(l){

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

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

0<=col&&col<MAXCOL)

map[row][col]=ALIVE;

elseififrow==-1||col==-1)

break;

else

printff'(x,y)exceedsmapranage!n);

intncighbors(introw,intcol){

intcount=0,c,r;

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

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

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

continue;

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

count++;

}

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

count—;

returncount;

}

voidoutputMap(){

introw,col;

printf("\n\n%20cGameoflifecellstatus\nn);

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

printf(H\n%20cn,1');

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

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

elseputchar('-')；

voidcopyMap(){

introw,col;

for(row=0;row<MAXROW;row++)

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

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

}

11.字串核對

說明今日的一些高階程式語言對于字串的處理支援越來越強(qiáng)大(例如Java、Perl等)，不過字串搜尋本身仍是個值得探討的

課題，在這邊以Boyer-Moore法來說明如何進(jìn)行字串說明，這個方法快且原理簡潔易懂。

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

開頭開始比對，例如Knuth-Morris-Pratt演算法字串搜尋，這個方法也不錯，不過要花時間在公式計算上；Boyer-Moore字串

核對改由關(guān)鍵字的后面開始核對字串，并制作前進(jìn)表，如果比對不符合則依前進(jìn)表中的值前進(jìn)至下一個核對處，假設(shè)是p好了,

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

如果關(guān)鍵字中有重復(fù)出現(xiàn)的字元，則前進(jìn)值就會有兩個以上的值，此時則取前進(jìn)值較小的值，如此就不會跳過可能的位置，

例如texture這個關(guān)鍵字，t的前進(jìn)值應(yīng)該取后面的3而不是取前面的7。

#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[80];

charstr_key[80];

chartmp[80]={'\0r};

intm,n,p;

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

gets(strinput);

printff請輸入搜尋關(guān)鍵字：”);

gets(strkey);

m=strlen(str_input);//計算字串長度

n=strlen(str_key);

table(str_key);

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

while(p!=-1){

substring(str_input,tmp,p,m);

printf(n%s\n",tmp);

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

}

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,m,n;

chartmp[80]=

m=strlen(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){

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

mp[j]=text[i];

tmp[j]=VT;

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

說明雙色河內(nèi)塔與三色河內(nèi)塔是由之前所介紹過的河內(nèi)塔規(guī)則衍生而來，雙色河內(nèi)塔的目的是將下圖左上的圓環(huán)位置經(jīng)移

動成為右下的圓環(huán)位置：

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

解法無論是雙色河內(nèi)塔或是三色河內(nèi)塔，其解法觀念與之前介紹過的河內(nèi)塔是類似的，同樣也是使用遞回來解，不過這次

遞回解法的目的不同，我們先來看只有兩個盤的情況，這很簡單，只要將第一柱的黃色移動至第二柱，而接下來第一柱的藍(lán)

色移動至第三柱。

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

接下來最底層的就不用管它們了，因為它們已經(jīng)就定位，只要再處理第?柱的上面兩個盤子就可以了。那么六個盤的情況呢？

一樣！首先必須用遞回完成下圖左上至右下的移動：

接下來最底層的就不用管它們了，因為它們已經(jīng)就定位，只要再處理第一柱上面的四個盤子就可以了，這又與之前只有四盤

的情況相同，接下來您就知道該如何進(jìn)行解題了，無論是八個盤、十個盤以上等，都是用這個觀念來解題。

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

?旦||

接下來最底兩層的就不用管它們了，因為它們已經(jīng)就定位，只要再處理第一柱上面的三個盤子就可以了。

J二*Ih"

雙色河內(nèi)塔C實作

#include<stdio.h>

voidhanoi(intdisks,charsource,chartemp,chartarget){

if(disks==1){

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

printf(Mmovediskfrom%cto%c\n",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;

for(i=disks/2;i>l;i-){

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

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

printf{nmovediskfrom%cto%c\n",source,temp);

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

printf^Mmovediskfrom%cto%c\nH,temp,target);

}

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

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

}

intmain(){

intn;

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

scanf(M%dn,&n);

hanoi2colors(n);

return0;

}

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

#include<stdio.h>

voidhanoi(intdisks,charsource,chartemp,chartarget){

if(disks=1){

printf{nmovediskfrom%cto%c\n",source,target);

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

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

}else{

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

hanoi(l,source,temp,target);

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

voidhanoi3colors(intdisks){

charsource='A';

chartemp=B;

chartarget='C;

inti;

if(disks=3){

printfiC'movediskfrom%cto%c\n",source,temp);

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

printfl(nmovediskfrom%cto%c\n",source,target);

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

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

printf(,,movediskfrom%cto%c\n"，target,temp);;

)

else{

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

printfC'movediskfrom%cto%c\n",source,temp);

printf(vmovediskfrom%cto%c\n",source,temp);

printfV'movediskfrom%cto%c\n",source,temp);

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

printftnmovediskfrom%cto%c\n",temp,target);

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

printfiC'movediskfrom%cto%c\n",temp,target);

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

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

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

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

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

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

if(i>l){

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

)

printfif'movediskfrom%cto%c\n",target,source);

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

if(i>l){

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