51CTO下載-經(jīng)典算法(C語(yǔ)言)

PAGEPAGE981.漢若塔 22.費(fèi)式數(shù)列 33.巴斯卡三角形 44.三色棋 55.老鼠走迷官（一） 76.老鼠走迷官（二） 97.騎士走棋盤(pán) 108.八皇后 139.八枚銀幣 1510.生命游戲 1711.字串核對(duì) 2012.雙色、三色河內(nèi)塔 2213.背包問(wèn)題（KnapsackProblem） 2614.蒙地卡羅法求PI 3115.Eratosthenes篩選求質(zhì)數(shù) 3216.超長(zhǎng)整數(shù)運(yùn)算（大數(shù)運(yùn)算） 3417.長(zhǎng)PI 3618.最大公因數(shù)、最小公倍數(shù)、因式分解 3919.完美數(shù) 4220.阿姆斯壯數(shù) 4521.最大訪(fǎng)客數(shù) 4622.中序式轉(zhuǎn)后序式（前序式） 4823.后序式的運(yùn)算 5224.洗撲克牌（亂數(shù)排列） 5425.Craps賭博游戲 5626.約瑟夫問(wèn)題（JosephusProblem） 5827.排列組合 6028.格雷碼（GrayCode） 6129.產(chǎn)生可能的集合 6330.m元素集合的n個(gè)元素子集 6631.數(shù)字拆解 6832.得分排行 7133.選擇、插入、氣泡排序 7334.Shell排序法-改良的插入排序 7735.Shaker排序法-改良的氣泡排序 8036.排序法-改良的選擇排序 8237.快速排序法（一） 8638.快速排序法 8839.快速排序法（三） 9040.合并排序法 9341.基數(shù)排序法 9642.循序搜尋法（使用衛(wèi)兵） 9843.二分搜尋法（搜尋原則的代表） 10044.插補(bǔ)搜尋法 10345.費(fèi)氏搜尋法 10646.稀疏矩陣 11047.多維矩陣轉(zhuǎn)一維矩陣 11148.上三角、下三角、對(duì)稱(chēng)矩陣 11349.奇數(shù)魔方陣 11550.4N魔方陣 11751.2(2N+1)魔方陣 1191.漢若塔說(shuō)明河內(nèi)之塔(TowersofHanoi)是法國(guó)人M.Claus(Lucas)于1883年從泰國(guó)帶至法國(guó)的，河內(nèi)為越戰(zhàn)時(shí)北越的首都，即現(xiàn)在的胡志明市；1883年法國(guó)數(shù)學(xué)家EdouardLucas曾提及這個(gè)故事，據(jù)說(shuō)創(chuàng)世紀(jì)時(shí)Benares有一座波羅教塔，是由三支鉆石棒（Pag）所支撐，開(kāi)始時(shí)神在第一根棒上放置64個(gè)由上至下依由小至大排列的金盤(pán)（Disc），并命令僧侶將所有的金盤(pán)從第一根石棒移至第三根石棒，且搬運(yùn)過(guò)程中遵守大盤(pán)子在小盤(pán)子之下的原則，若每日僅搬一個(gè)盤(pán)子，則當(dāng)盤(pán)子全數(shù)搬運(yùn)完畢之時(shí)，此塔將毀損，而也就是世界末日來(lái)臨之時(shí)。解法如果柱子標(biāo)為ABC，要由A搬至C，在只有一個(gè)盤(pán)子時(shí)，就將它直接搬至C，當(dāng)有兩個(gè)盤(pán)子，就將B當(dāng)作輔助柱。如果盤(pán)數(shù)超過(guò)2個(gè)，將第三個(gè)以下的盤(pán)子遮起來(lái)，就很簡(jiǎn)單了，每次處理兩個(gè)盤(pán)子，也就是：A->B、A->C、B->C這三個(gè)步驟，而被遮住的部份，其實(shí)就是進(jìn)入程式的遞回處理。事實(shí)上，若有n個(gè)盤(pán)子，則移動(dòng)完畢所需之次數(shù)為2^n-1，所以當(dāng)盤(pán)數(shù)為64時(shí)，則所需次數(shù)為：264-1=18446744073709551615為5.05390248594782e+16年，也就是約5000世紀(jì)，如果對(duì)這數(shù)字沒(méi)什幺概念，就假設(shè)每秒鐘搬一個(gè)盤(pán)子好了，也要約5850億年左右。#include<stdio.h>voidhanoi(intn,charA,charB,charC){if(n==1){printf("Movesheet%dfrom%cto%c\n",n,A,C);}else{hanoi(n-1,A,C,B);printf("Movesheet%dfrom%cto%c\n",n,A,C);hanoi(n-1,B,A,C);}}intmain(){intn;printf("請(qǐng)輸入盤(pán)數(shù)：");scanf("%d",&n);hanoi(n,'A','B','C');return0;}2.費(fèi)式數(shù)列說(shuō)明Fibonacci為1200年代的歐洲數(shù)學(xué)家，在他的著作中曾經(jīng)提到：「若有一只免子每個(gè)月生一只小免子，一個(gè)月后小免子也開(kāi)始生產(chǎn)。起初只有一只免子，一個(gè)月后就有兩只免子，二個(gè)月后有三只免子，三個(gè)月后有五只免子（小免子投入生產(chǎn)）。如果不太理解這個(gè)例子的話(huà)，舉個(gè)圖就知道了，注意新生的小免子需一個(gè)月成長(zhǎng)期才會(huì)投入生產(chǎn)，類(lèi)似的道理也可以用于植物的生長(zhǎng)，這就是Fibonacci數(shù)列，一般習(xí)慣稱(chēng)之為費(fèi)氏數(shù)列，例如以下：1、1、2、3、5、8、13、21、34、55、89解法依說(shuō)明，我們可以將費(fèi)氏數(shù)列定義為以下：fn=fn-1+fn-2ifn>1fn=nifn=0,1#include<stdio.h>#include<stdlib.h>#defineN20intmain(void){intFib[N]={0};inti;Fib[0]=0;Fib[1]=1;for(i=2;i<N;i++)Fib[i]=Fib[i-1]+Fib[i-2];for(i=0;i<N;i++)printf("%d",Fib[i]);printf("\n");return0;}3.巴斯卡三角形#include<stdio.h>#defineN12longcombi(intn,intr){inti;longp=1;for(i=1;i<=r;i++)p=p*(n-i+1)/i;returnp;}voidpaint(){intn,r,t;for(n=0;n<=N;n++){for(r=0;r<=n;r++){inti;/*排版設(shè)定開(kāi)始*/if(r==0){for(i=0;i<=(N-n);i++)printf("");}else{printf("");}/*排版設(shè)定結(jié)束*/printf("%3d",combi(n,r));}printf("\n");}}4.三色棋說(shuō)明三色旗的問(wèn)題最早由E.W.Dijkstra所提出，他所使用的用語(yǔ)為DutchNationFlag(Dijkstra為荷蘭人)，而多數(shù)的作者則使用Three-ColorFlag來(lái)稱(chēng)之。假設(shè)有一條繩子，上面有紅、白、藍(lán)三種顏色的旗子，起初繩子上的旗子顏色并沒(méi)有順序，您希望將之分類(lèi)，并排列為藍(lán)、白、紅的順序，要如何移動(dòng)次數(shù)才會(huì)最少，注意您只能在繩子上進(jìn)行這個(gè)動(dòng)作，而且一次只能調(diào)換兩個(gè)旗子。解法在一條繩子上移動(dòng)，在程式中也就意味只能使用一個(gè)陣列，而不使用其它的陣列來(lái)作輔助，問(wèn)題的解法很簡(jiǎn)單，您可以自己想像一下在移動(dòng)旗子，從繩子開(kāi)頭進(jìn)行，遇到藍(lán)色往前移，遇到白色留在中間，遇到紅色往后移，如下所示：只是要讓移動(dòng)次數(shù)最少的話(huà)，就要有些技巧：如果圖中W所在的位置為白色，則W+1，表示未處理的部份移至至白色群組。如果W部份為藍(lán)色，則B與W的元素對(duì)調(diào)，而B(niǎo)與W必須各+1，表示兩個(gè)群組都多了一個(gè)元素。如果W所在的位置是紅色，則將W與R交換，但R要減1，表示未處理的部份減1。注意B、W、R并不是三色旗的個(gè)數(shù)，它們只是一個(gè)移動(dòng)的指標(biāo)；什幺時(shí)候移動(dòng)結(jié)束呢？一開(kāi)始時(shí)未處理的R指標(biāo)會(huì)是等于旗子的總數(shù)，當(dāng)R的索引數(shù)減至少于W的索引數(shù)時(shí)，表示接下來(lái)的旗子就都是紅色了，此時(shí)就可以結(jié)束移動(dòng)，如下所示：#include<stdio.h>#include<stdlib.h>#include<string.h>#defineBLUE'b'#defineWHITE'w'#defineRED'r'#defineSWAP(x,y){chartemp;\temp=color[x];\color[x]=color[y];\color[y]=temp;}intmain(){charcolor[]={'r','w','b','w','w','b','r','b','w','r','\0'};intwFlag=0;intbFlag=0;intrFlag=strlen(color)-1;inti;for(i=0;i<strlen(color);i++)printf("%c",color[i]);printf("\n");while(wFlag<=rFlag){if(color[wFlag]==WHITE)wFlag++;elseif(color[wFlag]==BLUE){SWAP(bFlag,wFlag);bFlag++;wFlag++;}else{while(wFlag<rFlag&&color[rFlag]==RED)rFlag--;SWAP(rFlag,wFlag);rFlag--;}}for(i=0;i<strlen(color);i++)printf("%c",color[i]);printf("\n");return0;}5.老鼠走迷官（一）說(shuō)明老鼠走迷宮是遞回求解的基本題型，我們?cè)诙S陣列中使用2表示迷宮墻壁，使用1來(lái)表示老鼠的行走路徑，試以程式求出由入口至出口的路徑。解法老鼠的走法有上、左、下、右四個(gè)方向，在每前進(jìn)一格之后就選一個(gè)方向前進(jìn)，無(wú)法前進(jìn)時(shí)退回選擇下一個(gè)可前進(jìn)方向，如此在陣列中依序測(cè)試四個(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}};intstartI=1,startJ=1;//入口intendI=5,endJ=5;//出口intsuccess=0;intmain(void){inti,j;printf("顯示迷宮：\n");for(i=0;i<7;i++){for(j=0;j<7;j++)if(maze[i][j]==2)printf("█");elseprintf("");printf("\n");}if(visit(startI,startJ)==0)printf("\n沒(méi)有找到出口！\n");else{printf("\n顯示路徑：\n");for(i=0;i<7;i++){for(j=0;j<7;j++){if(maze[i][j]==2)printf("█");elseif(maze[i][j]==1)printf("

");elseprintf("");}printf("\n");}}return0;}intvisit(inti,intj){maze[i][j]=1;if(i==endI&&j==endJ)success=1;if(success!=1&&maze[i][j+1]==0)visit(i,j+1);if(success!=1&&maze[i+1][j]==0)visit(i+1,j);if(success!=1&&maze[i][j-1]==0)visit(i,j-1);if(success!=1&&maze[i-1][j]==0)visit(i-1,j);if(success!=1)maze[i][j]=0;returnsuccess;}6.老鼠走迷官（二）說(shuō)明由于迷宮的設(shè)計(jì)，老鼠走迷宮的入口至出口路徑可能不只一條，如何求出所有的路徑呢？解法求所有路徑看起來(lái)復(fù)雜但其實(shí)更簡(jiǎn)單，只要在老鼠走至出口時(shí)顯示經(jīng)過(guò)的路徑，然后退回上一格重新選擇下一個(gè)位置繼續(xù)遞回就可以了，比求出單一路徑還簡(jiǎn)單，我們的程式只要作一點(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}};intstartI=1,startJ=1;//入口intendI=7,endJ=7;//出口intmain(void){inti,j;printf("顯示迷宮：\n");for(i=0;i<7;i++){for(j=0;j<7;j++)if(maze[i][j]==2)printf("█");elseprintf("");printf("\n");}visit(startI,startJ);return0;}voidvisit(inti,intj){intm,n;maze[i][j]=1;if(i==endI&&j==endJ){printf("\n顯示路徑：\n");for(m=0;m<9;m++){for(n=0;n<9;n++)if(maze[m][n]==2)printf("█");elseif(maze[m][n]==1)printf("

");elseprintf("");printf("\n");}}if(maze[i][j+1]==0)visit(i,j+1);if(maze[i+1][j]==0)visit(i+1,j);if(maze[i][j-1]==0)visit(i,j-1);if(maze[i-1][j]==0)visit(i-1,j);maze[i][j]=0;}7.騎士走棋盤(pán)說(shuō)明騎士旅游（Knighttour）在十八世紀(jì)初倍受數(shù)學(xué)家與拼圖迷的注意，它什么時(shí)候被提出已不可考，騎士的走法為西洋棋的走法，騎士可以由任一個(gè)位置出發(fā)，它要如何走完[所有的位置？解法騎士的走法，基本上可以使用遞回來(lái)解決，但是純綷的遞回在維度大時(shí)相當(dāng)沒(méi)有效率，一個(gè)聰明的解法由J.C.Warnsdorff在1823年提出，簡(jiǎn)單的說(shuō)，先將最難的位置走完，接下來(lái)的路就寬廣了，騎士所要走的下一步，「為下一步再選擇時(shí)，所能走的步數(shù)最少的一步?！梗褂眠@個(gè)方法，在不使用遞回的情況下，可以有較高的機(jī)率找出走法（找不到走法的機(jī)會(huì)也是有的）。#include<stdio.h>intboard[8][8]={0};intmain(void){intstartx,starty;inti,j;printf("輸入起始點(diǎn)：");scanf("%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",board[i][j]);}putchar('\n');}return0;}inttravel(intx,inty){//對(duì)應(yīng)騎士可走的八個(gè)方向intktmove1[8]={-2,-1,1,2,2,1,-1,-2};intktmove2[8]={1,2,2,1,-1,-2,-2,-1};//測(cè)試下一步的出路intnexti[8]={0};intnextj[8]={0};//記錄出路的個(gè)數(shù)intexists[8]={0};inti,j,k,m,l;inttmpi,tmpj;intcount,min,tmp;i=x;j=y;board[i][j]=1;for(m=2;m<=64;m++){for(l=0;l<8;l++)exists[l]=0;l=0;//試探八個(gè)方向for(k=0;k<8;k++){tmpi=i+ktmove1[k];tmpj=j+ktmove2[k];//如果是邊界了，不可走if(tmpi<0||tmpj<0||tmpi>7||tmpj>7)continue;//如果這個(gè)方向可走，記錄下來(lái)if(board[tmpi][tmpj]==0){nexti[l]=tmpi;nextj[l]=tmpj;//可走的方向加一個(gè)l++;}}count=l;//如果可走的方向?yàn)?個(gè)，返回if(count==0){return0;}elseif(count==1){//只有一個(gè)可走的方向//所以直接是最少出路的方向min=0;}else{//找出下一個(gè)位置的出路數(shù)for(l=0;l<count;l++){for(k=0;k<8;k++){tmpi=nexti[l]+ktmove1[k];tmpj=nextj[l]+ktmove2[k];if(tmpi<0||tmpj<0||tmpi>7||tmpj>7){continue;}if(board[tmpi][tmpj]==0)exists[l]++;}}tmp=exists[0];min=0;//從可走的方向中尋找最少出路的方向for(l=1;l<count;l++){if(exists[l]<tmp){tmp=exists[l];min=l;}}}//走最少出路的方向i=nexti[min];j=nextj[min];board[i][j]=m;}return1;}8.八皇后說(shuō)明西洋棋中的皇后可以直線(xiàn)前進(jìn)，吃掉遇到的所有棋子，如果棋盤(pán)上有八個(gè)皇后，則這八個(gè)皇后如何相安無(wú)事的放置在棋盤(pán)上，1970年與1971年，E.W.Dijkstra與N.Wirth曾經(jīng)用這個(gè)問(wèn)題來(lái)講解程式設(shè)計(jì)之技巧。解法關(guān)于棋盤(pán)的問(wèn)題，都可以用遞回求解，然而如何減少遞回的次數(shù)？在八個(gè)皇后的問(wèn)題中，不必要所有的格子都檢查過(guò)，例如若某列檢查過(guò)，該該列的其它格子就不用再檢查了，這個(gè)方法稱(chēng)為分支修剪。#include<stdio.h>#include<stdlib.h>#defineN8intcolumn[N+1];//同欄是否有皇后，1表示有intrup[2*N+1];//右上至左下是否有皇后intlup[2*N+1];//左上至右下是否有皇后intqueen[N+1]={0};intnum;//解答編號(hào)voidbacktrack(int);//遞回求解intmain(void){inti;num=0;for(i=1;i<=N;i++)column[i]=1;for(i=1;i<=2*N;i++)rup[i]=lup[i]=1;backtrack(1);return0;}voidshowAnswer(){intx,y;printf("\n解答%d\n",++num);for(y=1;y<=N;y++){for(x=1;x<=N;x++){if(queen[y]==x){printf("Q");}else{printf(".");}}printf("\n");}}voidbacktrack(inti){intj;if(i>N){showAnswer();}else{for(j=1;j<=N;j++){if(column[j]==1&&rup[i+j]==1&&lup[i-j+N]==1){queen[i]=j;//設(shè)定為占用column[j]=rup[i+j]=lup[i-j+N]=0;backtrack(i+1);column[j]=rup[i+j]=lup[i-j+N]=1;}}}}9.八枚銀幣說(shuō)明現(xiàn)有八枚銀幣abcdefgh，已知其中一枚是假幣，其重量不同于真幣，但不知是較輕或較重，如何使用天平以最少的比較次數(shù)，決定出哪枚是假幣，并得知假幣比真幣較輕或較重。解法單就求假幣的問(wèn)題是不難，但問(wèn)題限制使用最少的比較次數(shù)，所以我們不能以單純的回圈比較來(lái)求解，我們可以使用決策樹(shù)（decisiontree），使用分析與樹(shù)狀圖來(lái)協(xié)助求解。一個(gè)簡(jiǎn)單的狀況是這樣的，我們比較a+b+c與d+e+f，如果相等，則假幣必是g或h，我們先比較g或h哪個(gè)較重，如果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));for(i=0;i<8;i++)coins[i]=10;printf("\n輸入假幣重量(比10大或小)：");scanf("%d",&i);coins[rand()%8]=i;eightcoins(coins);printf("\n\n列出所有錢(qián)幣重量：");for(i=0;i<8;i++)printf("%d",coins[i]);printf("\n");return0;}voidcompare(intcoins[],inti,intj,intk){if(coins[i]>coins[k])printf("\n假幣%d較重",i+1);elseprintf("\n假幣%d較輕",j+1);}voideightcoins(intcoins[]){if(coins[0]+coins[1]+coins[2]==coins[3]+coins[4]+coins[5]){if(coins[6]>coins[7])compare(coins,6,7,0);elsecompare(coins,7,6,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,2,5,0);elseif(coins[0]+coins[3]>coins[1]+coins[4])compare(coins,0,4,1);if(coins[0]+coins[3]<coins[1]+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[1]+coins[4])compare(coins,3,1,0);if(coins[0]+coins[3]<coins[1]+coins[4])compare(coins,4,0,1);}}10.生命游戲說(shuō)明生命游戲（gameoflife）為1970年由英國(guó)數(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ù)活：如果某位置原無(wú)細(xì)胞存活，而該位置的鄰居為三個(gè)，則該位置將復(fù)活一細(xì)胞。解法生命游戲的規(guī)則可簡(jiǎn)化為以下，并使用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#defineALIVE1intmap[MAXROW][MAXCOL],newmap[MAXROW][MAXCOL];voidinit();intneighbors(int,int);voidoutputMap();voidcopyMap();intmain(){introw,col;charans;init();while(1){outputMap();for(row=0;row<MAXROW;row++){for(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();printf("\nContinuenextGeneration?");getchar();ans=toupper(getchar());if(ans!='Y') break;}return0;}voidinit(){introw,col;for(row=0;row<MAXROW;row++)for(col=0;col<MAXCOL;col++)map[row][col]=DEAD;puts("GameoflifeProgram");puts("Enterx,ywherex,yislivingcell");printf("0<=x<=%d,0<=y<=%d\n",MAXROW-1,MAXCOL-1);puts("Terminatewithx,y=-1,-1");while(1){scanf("%d%d",&row,&col);if(0<=row&&row<MAXROW&&0<=col&&col<MAXCOL)map[row][col]=ALIVE;elseif(row==-1||col==-1)break;elseprintf("(x,y)exceedsmapranage!");}}intneighbors(introw,intcol){intcount=0,c,r;for(r=row-1;r<=row+1;r++)for(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\n");for(row=0;row<MAXROW;row++){printf("\n%20c",'');for(col=0;col<MAXCOL;col++)if(map[row][col]==ALIVE) putchar('#');else putchar('-');}}voidcopyMap(){introw,col;for(row=0;row<MAXROW;row++)for(col=0;col<MAXCOL;col++)map[row][col]=newmap[row][col];}11.字串核對(duì)說(shuō)明今日的一些高階程式語(yǔ)言對(duì)于字串的處理支援越來(lái)越強(qiáng)大（例如Java、Perl等），不過(guò)字串搜尋本身仍是個(gè)值得探討的課題，在這邊以Boyer-Moore法來(lái)說(shuō)明如何進(jìn)行字串說(shuō)明，這個(gè)方法快且原理簡(jiǎn)潔易懂。解法字串搜尋本身不難，使用暴力法也可以求解，但如何快速搜尋字串就不簡(jiǎn)單了，傳統(tǒng)的字串搜尋是從關(guān)鍵字與字串的開(kāi)頭開(kāi)始比對(duì)，例如Knuth-Morris-Pratt演算法字串搜尋，這個(gè)方法也不錯(cuò)，不過(guò)要花時(shí)間在公式計(jì)算上；Boyer-Moore字串核對(duì)改由關(guān)鍵字的后面開(kāi)始核對(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ì)跳過(guò)可能的位置，例如texture這個(gè)關(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]={'\0'};intm,n,p;printf("請(qǐng)輸入字串：");gets(str_input);printf("請(qǐng)輸入搜尋關(guān)鍵字：");gets(str_key);m=strlen(str_input);//計(jì)算字串長(zhǎng)度n=strlen(str_key);table(str_key);p=search(n-1,str_input,str_key);while(p!=-1){substring(str_input,tmp,p,m);printf("%s\n",tmp);p=search(p+n+1,str_input,str_key);}printf("\n");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]={'\0'};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){inti,j;for(i=s,j=0;i<=e;i++,j++) mp[j]=text[i];tmp[j]='\0';}12.雙色、三色河內(nèi)塔說(shuō)明雙色河內(nèi)塔與三色河內(nèi)塔是由之前所介紹過(guò)的河內(nèi)塔規(guī)則衍生而來(lái)，雙色河內(nèi)塔的目的是將下圖左上的圓環(huán)位置經(jīng)移動(dòng)成為右下的圓環(huán)位置：而三色河內(nèi)塔則是將下圖左上的圓環(huán)經(jīng)移動(dòng)成為右上的圓環(huán)：解法無(wú)論是雙色河內(nèi)塔或是三色河內(nèi)塔，其解法觀(guān)念與之前介紹過(guò)的河內(nèi)塔是類(lèi)似的，同樣也是使用遞回來(lái)解，不過(guò)這次遞回解法的目的不同，我們先來(lái)看只有兩個(gè)盤(pán)的情況，這很簡(jiǎn)單，只要將第一柱的黃色移動(dòng)至第二柱，而接下來(lái)第一柱的藍(lán)色移動(dòng)至第三柱。再來(lái)是四個(gè)盤(pán)的情況，首先必須用遞回完成下圖左上至右下的移動(dòng)：接下來(lái)最底層的就不用管它們了，因?yàn)樗鼈円呀?jīng)就定位，只要再處理第一柱的上面兩個(gè)盤(pán)子就可以了。那么六個(gè)盤(pán)的情況呢？一樣！首先必須用遞回完成下圖左上至右下的移動(dòng)：接下來(lái)最底層的就不用管它們了，因?yàn)樗鼈円呀?jīng)就定位，只要再處理第一柱上面的四個(gè)盤(pán)子就可以了，這又與之前只有四盤(pán)的情況相同，接下來(lái)您就知道該如何進(jìn)行解題了，無(wú)論是八個(gè)盤(pán)、十個(gè)盤(pán)以上等，都是用這個(gè)觀(guān)念來(lái)解題。那么三色河內(nèi)塔呢？一樣，直接來(lái)看九個(gè)盤(pán)的情況，首先必須完成下圖的移動(dòng)結(jié)果：接下來(lái)最底兩層的就不用管它們了，因?yàn)樗鼈円呀?jīng)就定位，只要再處理第一柱上面的三個(gè)盤(pán)子就可以了。雙色河內(nèi)塔C實(shí)作#include<stdio.h>voidhanoi(intdisks,charsource,chartemp,chartarget){if(disks==1){printf("movediskfrom%cto%c\n",source,target);printf("movediskfrom%cto%c\n",source,target);}else{hanoi(disks-1,source,target,temp);hanoi(1,source,temp,target);hanoi(disks-1,temp,source,target);}}voidhanoi2colors(intdisks){charsource='A';chartemp='B';chartarget='C';inti;for(i=disks/2;i>1;i--){hanoi(i-1,source,temp,target);printf("movediskfrom%cto%c\n",source,temp);printf("movediskfrom%cto%c\n",source,temp);hanoi(i-1,target,temp,source);printf("movediskfrom%cto%c\n",temp,target);}printf("movediskfrom%cto%c\n",source,temp);printf("movediskfrom%cto%c\n",source,target);}intmain(){intn;printf("請(qǐng)輸入盤(pán)數(shù)：");scanf("%d",&n);hanoi2colors(n);return0;}三色河內(nèi)塔C實(shí)作#include<stdio.h>voidhanoi(intdisks,charsource,chartemp,chartarget){if(disks==1){printf("movediskfrom%cto%c\n",source,target);printf("movediskfrom%cto%c\n",source,target);printf("movediskfrom%cto%c\n",source,target);}else{hanoi(disks-1,source,target,temp);hanoi(1,source,temp,target);hanoi(disks-1,temp,source,target);}}voidhanoi3colors(intdisks){charsource='A';chartemp='B';chartarget='C';inti;if(disks==3){printf("movediskfrom%cto%c\n",source,temp);printf("movediskfrom%cto%c\n",source,temp);printf("movediskfrom%cto%c\n",source,target);printf("movediskfrom%cto%c\n",temp,target);printf("movediskfrom%cto%c\n",temp,source);printf("movediskfrom%cto%c\n",target,temp);;}else{hanoi(disks/3-1,source,temp,target);printf("movediskfrom%cto%c\n",source,temp);printf("movediskfrom%cto%c\n",source,temp);printf("movediskfrom%cto%c\n",source,temp);hanoi(disks/3-1,target,temp,source);printf("movediskfrom%cto%c\n",temp,target);printf("movediskfrom%cto%c\n",temp,target);printf("movediskfrom%cto%c\n",temp,target);hanoi(disks/3-1,source,target,temp);printf("movediskfrom%cto%c\n",target,source);printf("movediskfrom%cto%c\n",target,source);hanoi(disks/3-1,temp,source,target);printf("movediskfrom%cto%c\n",source,temp);for(i=disks/3-1;i>0;i--){if(i>1){hanoi(i-1,target,source,temp);}printf("movediskfrom%cto%c\n",target,source);printf("movediskfrom%cto%c\n",target,source);if(i>1){hanoi(i-1,temp,source,target);}printf("movediskfrom%cto%c\n",source,temp);}}}intmain(){intn;printf("請(qǐng)輸入盤(pán)數(shù)：");scanf("%d",&n);hanoi3colors(n);return0;}13.背包問(wèn)題（KnapsackProblem）說(shuō)明假設(shè)有一個(gè)背包的負(fù)重最多可達(dá)8公斤，而希望在背包中裝入負(fù)重范圍內(nèi)可得之總價(jià)物品，假設(shè)是水果好了，水果的編號(hào)、單價(jià)與重量如下所示0李子4KGNT$45001蘋(píng)果5KGNT$57002橘子2KGNT$22503草莓1KGNT$11004甜瓜6KGNT$6700解法背包問(wèn)題是關(guān)于最佳化的問(wèn)題，要解最佳化問(wèn)題可以使用「動(dòng)態(tài)規(guī)劃」（Dynamicprogramming），從空集合開(kāi)始，每增加一個(gè)元素就先求出該階段的最佳解，直到所有的元素加入至集合中，最后得到的就是最佳解。以背包問(wèn)題為例，我們使用兩個(gè)陣列value與item，value表示目前的最佳解所得之總價(jià)，item表示最后一個(gè)放至背包的水果，假設(shè)有負(fù)重量1～8的背包8個(gè)，并對(duì)每個(gè)背包求其最佳解。逐步將水果放入背包中，并求該階段的最佳解：放入李子背包負(fù)重12345678value０００45004500450045009000item－－－０００００放入蘋(píng)果背包負(fù)重12345678value０００45005700570057009000item－－－０111０放入橘子背包負(fù)重12345678value０2250225045005700675079509000item－22０122０放入草莓背包負(fù)重12345678value11002250335045005700680079509050item323０1323放入甜瓜背包負(fù)重12345678value11002250335045005700680079509050item323０1323由最后一個(gè)表格，可以得知在背包負(fù)重8公斤時(shí)，最多可以裝入9050元的水果，而最后一個(gè)裝入的水果是3號(hào)，也就是草莓，裝入了草莓，背包只能再放入7公斤（8-1）的水果，所以必須看背包負(fù)重7公斤時(shí)的最佳解，最后一個(gè)放入的是2號(hào)，也就是橘子，現(xiàn)在背包剩下負(fù)重量5公斤（7-2），所以看負(fù)重5公斤的最佳解，最后放入的是1號(hào)，也就是蘋(píng)果，此時(shí)背包負(fù)重量剩下0公斤（5-5），無(wú)法再放入水果，所以求出最佳解為放入草莓、橘子與蘋(píng)果，而總價(jià)為9050元。實(shí)作C#include<stdio.h>#include<stdlib.h>#defineLIMIT8//重量限制#defineN5//物品種類(lèi)#defineMIN1//最小重量structbody{charname[20];intsize;intprice;};typedefstructbodyobject;intmain(void){intitem[LIMIT+1]={0};intvalue[LIMIT+1]={0};intnewvalue,i,s,p;objecta[]={{"李子",4,4500},{"蘋(píng)果",5,5700},{"橘子",2,2250},{"草莓",1,1100},{"甜瓜",6,6700}};for(i=0;i<N;i++){for(s=a[i].size;s<=LIMIT;s++){p=s-a[i].size;newvalue=value[p]+a[i].price;if(newvalue>value[s]){//找到階段最佳解value[s]=newvalue;item[s]=i;}}}printf("物品\