史上最全最經(jīng)典數(shù)據(jù)結(jié)構(gòu)-100個(gè)經(jīng)典算法

..C語言經(jīng)典算法大全老掉牙河內(nèi)塔費(fèi)式數(shù)列巴斯卡三角形三色棋老鼠走迷官〔一老鼠走迷官〔二騎士走棋盤八個(gè)皇后八枚銀幣生命游戲字串核對(duì)雙色、三色河內(nèi)塔背包問題〔KnapsackProblem數(shù)、運(yùn)算蒙地卡羅法求PIEratosthenes篩選求質(zhì)數(shù)超長(zhǎng)整數(shù)運(yùn)算〔大數(shù)運(yùn)算長(zhǎng)PI最大公因數(shù)、最小公倍數(shù)、因式分解完美數(shù)阿姆斯壯數(shù)最大訪客數(shù)中序式轉(zhuǎn)后序式〔前序式后序式的運(yùn)算關(guān)于賭博洗撲克牌〔亂數(shù)排列Craps賭博游戲約瑟夫問題〔JosephusProblem集合問題排列組合格雷碼〔GrayCode產(chǎn)生可能的集合m元素集合的n個(gè)元素子集數(shù)字拆解排序得分排行選擇、插入、氣泡排序Shell排序法-改良的插入排序Shaker排序法-改良的氣泡排序Heap排序法-改良的選擇排序快速排序法〔一快速排序法〔二快速排序法〔三合并排序法基數(shù)排序法搜尋循序搜尋法〔使用衛(wèi)兵二分搜尋法〔搜尋原則的代表插補(bǔ)搜尋法費(fèi)氏搜尋法矩陣稀疏矩陣多維矩陣轉(zhuǎn)一維矩陣上三角、下三角、對(duì)稱矩陣奇數(shù)魔方陣4N魔方陣2<2N+1>魔方陣1.河內(nèi)之塔說明河內(nèi)之塔<TowersofHanoi>是法國(guó)人M.Claus<Lucas>于1883年從泰國(guó)帶至法國(guó)的,河內(nèi)為越戰(zhàn)時(shí)北越的首都,即現(xiàn)在的胡志明市；1883年法國(guó)數(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è)以下的盤子遮起來,就很簡(jiǎn)單了,每次處理兩個(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í),則所需次數(shù)為：264#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)輸入盤數(shù)：">;scanf<"%d",&n>;hanoi<n,'A','B','C'>;return0;}

2.AlgorithmGossip:費(fèi)式數(shù)列說明Fibonacci為1200年代的歐洲數(shù)學(xué)家,在他的著作中曾經(jīng)提到：「若有一只免子每個(gè)月生一只小免子,一個(gè)月后小免子也開始生產(chǎn)。起初只有一只免子,一個(gè)月后就有兩只免子,二個(gè)月后有三只免子,三個(gè)月后有五只免子〔小免子投入生產(chǎn)......。如果不太理解這個(gè)例子的話,舉個(gè)圖就知道了,注意新生的小免子需一個(gè)月成長(zhǎng)期才會(huì)投入生產(chǎn),類似的道理也可以用于植物的生長(zhǎng),這就是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>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è)定開始*/if<r==0>{for<i=0;i<=<N-n>;i++>printf<"">;}else{printf<"">;}/*排版設(shè)定結(jié)束*/printf<"%3d",combi<n,r>>;}printf<"\n">;}}

4.AlgorithmGossip:三色棋說明三色旗的問題最早由所提出,他所使用的用語為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è)陣列,而不使用其它的陣列來作輔助,問題的解法很簡(jiǎn)單,您可以自己想像一下在移動(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>#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.AlgorithmGossip:老鼠走迷官〔一說明老鼠走迷宮是遞回求解的基本題型,我們?cè)诙S陣列中使用2表示迷宮墻壁,使用1來表示老鼠的行走路徑,試以程式求出由入口至出口的路徑。解法老鼠的走法有上、左、下、右四個(gè)方向,在每前進(jìn)一格之后就選一個(gè)方向前進(jìn),無法前進(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沒有找到出口！\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.AlgorithmGossip:老鼠走迷官〔二說明由于迷宮的設(shè)計(jì),老鼠走迷宮的入口至出口路徑可能不只一條,如何求出所有的路徑呢？解法求所有路徑看起來復(fù)雜但其實(shí)更簡(jiǎn)單,只要在老鼠走至出口時(shí)顯示經(jīng)過的路徑,然后退回上一格重新選擇下一個(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.AlgorithmGossip:騎士走棋盤說明騎士旅游〔Knighttour在十八世紀(jì)初倍受數(shù)學(xué)家與拼圖迷的注意,它什么時(shí)候被提出已不可考,騎士的走法為西洋棋的走法,騎士可以由任一個(gè)位置出發(fā),它要如何走完[所有的位置？解法騎士的走法,基本上可以使用遞回來解決,但是純綷的遞回在維度大時(shí)相當(dāng)沒有效率,一個(gè)聰明的解法由J.C.Warnsdorff在1823年提出,簡(jiǎn)單的說,先將最難的位置走完,接下來的路就寬廣了,騎士所要走的下一步,「為下一步再選擇時(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è)方向可走,記錄下來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.AlgorithmGossip:八皇后說明西洋棋中的皇后可以直線前進(jìn),吃掉遇到的所有棋子,如果棋盤上有八個(gè)皇后,則這八個(gè)皇后如何相安無事的放置在棋盤上,1970年與1971年,E.W.Dijkstra與N.Wirth曾經(jīng)用這個(gè)問題來講解程式設(shè)計(jì)之技巧。解法關(guān)于棋盤的問題,都可以用遞回求解,然而如何減少遞回的次數(shù)？在八個(gè)皇后的問題中,不必要所有的格子都檢查過,例如若某列檢查過,該該列的其它格子就不用再檢查了,這個(gè)方法稱為分支修剪。#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.AlgorithmGossip:八枚銀幣說明現(xiàn)有八枚銀幣abcdefgh,已知其中一枚是假幣,其重量不同于真幣,但不知是較輕或較重,如何使用天平以最少的比較次數(shù),決定出哪枚是假幣,并得知假幣比真幣較輕或較重。解法單就求假幣的問題是不難,但問題限制使用最少的比較次數(shù),所以我們不能以單純的回圈比較來求解,我們可以使用決策樹〔decisiontree,使用分析與樹狀圖來協(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列出所有錢幣重量：">;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.AlgorithmGossip:生命游戲說明生命游戲〔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ù)活：如果某位置原無細(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.AlgorithmGossip:字串核對(duì)說明今日的一些高階程式語言對(duì)于字串的處理支援越來越強(qiáng)大〔例如Java、Perl等,不過字串搜尋本身仍是個(gè)值得探討的課題,在這邊以Boyer-Moore法來說明如何進(jìn)行字串說明,這個(gè)方法快且原理簡(jiǎn)潔易懂。解法字串搜尋本身不難,使用暴力法也可以求解,但如何快速搜尋字串就不簡(jiǎn)單了,傳統(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而不是取前面的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.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)：解法無論是雙色河內(nèi)塔或是三色河內(nèi)塔,其解法觀念與之前介紹過的河內(nèi)塔是類似的,同樣也是使用遞回來解,不過這次遞回解法的目的不同,我們先來看只有兩個(gè)盤的情況,這很簡(jiǎn)單,只要將第一柱的黃色移動(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\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)輸入盤數(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)輸入盤數(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$45001蘋果5KGNT$57002橘子2KGNT$22503草莓1KGNT$11004甜瓜6KGNT$6700解法背包問題是關(guān)于最佳化的問題,要解最佳化問題可以使用「動(dòng)態(tài)規(guī)劃」〔Dynamicprogramming,從空集合開始,每增加一個(gè)元素就先求出該階段的最佳解,直到所有的元素加入至集合中,最后得到的就是最佳解。以背包問題為例,我們使用兩個(gè)陣列value與item,value表示目前的最佳解所得之總價(jià),item表示最后一個(gè)放至背包的水果,假設(shè)有負(fù)重量1～8的背包8個(gè),并對(duì)每個(gè)背包求其最佳解。逐步將水果放入背包中,并求該階段的最佳解：放入李子背包負(fù)重12345678value０００45004500450045009000item－－－０００００放入蘋果背包負(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),也就是蘋果,此時(shí)背包負(fù)重量剩下0公斤〔5-5,無法再放入水果,所以求出最佳解為放入草莓、橘子與蘋果,而總價(jià)為9050元。實(shí)作C#include<stdio.h>#include<stdlib.h>#defineLIMIT8//重量限制#defineN5//物品種類#defineMIN1//最小重量structbody{charname[20];intsize;intprice;};typedefstructbodyobject;intmain<void>{intitem[LIMIT+1]={0};intvalue[LIMIT+1]={0};intnewvalue,i,s,p;objecta[]={{"李子",4,4500},{"蘋果",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<"物品\t價(jià)格\n">;for<i=LIMIT;i>=MIN;i=i-a[item[i]].size>{printf<"%s\t%d\n",a[item[i]].name,a[item[i]].price>;}printf<"合計(jì)\t%d\n",value[LIMIT]>;return0;}JavaclassFruit{privateStringname;privateintsize;privateintprice;publicFruit<Stringname,intsize,intprice>{=name;this.size=size;this.price=price;}publicStringgetName<>{returnname;}publicintgetPrice<>{returnprice;}publicintgetSize<>{returnsize;}}publicclassKnapsack{publicstaticvoidmain<String[]args>{finalintMAX=8;finalintMIN=1;int[]item=newint[MAX+1];int[]value=newint[MAX+1];Fruitfruits[]={newFruit<"李子",4,4500>,newFruit<"蘋果",5,5700>,newFruit<"橘子",2,2250>,newFruit<"草莓",1,1100>,newFruit<"甜瓜",6,6700>};for<inti=0;i<fruits.length;i++>{for<ints=fruits[i].getSize<>;s<=MAX;s++>{intp=s-fruits[i].getSize<>;intnewvalue=value[p]+fruits[i].getPrice<>;if<newvalue>value[s]>{//找到階段最佳解value[s]=newvalue;item[s]=i;}}}System.out.println<"物品\t價(jià)格">;for<inti=MAX;i>=MIN;i=i-fruits[item[i]].getSize<>>{System.out.println<fruits[item[i]].getName<>+"\t"+fruits[item[i]].getPrice<>>;}System.out.println<"合計(jì)\t"+value[MAX]>;}}14.AlgorithmGossip:蒙地卡羅法求PI說明蒙地卡羅為摩洛哥王國(guó)之首都,該國(guó)位于法國(guó)與義大利國(guó)境,以賭博聞名。蒙地卡羅的基本原理為以亂數(shù)配合面積公式來進(jìn)行解題,這種以機(jī)率來解題的方式帶有賭博的意味,雖然在精確度上有所疑慮,但其解題的思考方向卻是個(gè)值得學(xué)習(xí)的方式。解法蒙地卡羅的解法適用于與面積有關(guān)的題目,例如求PI值或橢圓面積,這邊介紹如何求PI值；假設(shè)有一個(gè)圓半徑為1,所以四分之一圓面積就為PI,而包括此四分之一圓的正方形面積就為1,如下圖所示：如果隨意的在正方形中投射飛標(biāo)〔點(diǎn)好了,則這些飛標(biāo)〔點(diǎn)有些會(huì)落于四分之一圓內(nèi),假設(shè)所投射的飛標(biāo)〔點(diǎn)有n點(diǎn),在圓內(nèi)的飛標(biāo)〔點(diǎn)有c點(diǎn),則依比例來算,就會(huì)得到上圖中最后的公式。至于如何判斷所產(chǎn)生的點(diǎn)落于圓內(nèi),很簡(jiǎn)單,令亂數(shù)產(chǎn)生X與Y兩個(gè)數(shù)值,如果X^2+Y^2等于1就是落在圓內(nèi)。#include<stdio.h>#include<stdlib.h>#include<time.h>#defineN50000intmain<void>{inti,sum=0;doublex,y;srand<time<NULL>>;for<i=1;i<N;i++>{x=<double>rand<>/RAND_MAX;y=<double>rand<>/RAND_MAX;if<<x*x+y*y><1>sum++;}printf<"PI=%f\n",<double>4*sum/N>;return0;}

15.AlgorithmGossip:Eratosthenes篩選求質(zhì)數(shù)說明除了自身之外,無法被其它整數(shù)整除的數(shù)稱之為質(zhì)數(shù),要求質(zhì)數(shù)很簡(jiǎn)單,但如何快速的求出質(zhì)數(shù)則一直是程式設(shè)計(jì)人員與數(shù)學(xué)家努力的課題,在這邊介紹一個(gè)著名的Eratosthenes求質(zhì)數(shù)方法。解法首先知道這個(gè)問題可以使用回圈來求解,將一個(gè)指定的數(shù)除以所有小于它的數(shù),若可以整除就不是質(zhì)數(shù),然而如何減少回圈的檢查次數(shù)？如何求出小于N的所有質(zhì)數(shù)？首先假設(shè)要檢查的數(shù)是N好了,則事實(shí)上只要檢查至N的開根號(hào)就可以了,道理很簡(jiǎn)單,假設(shè)A*B=N,如果A大于N的開根號(hào),則事實(shí)上在小于A之前的檢查就可以先檢查到B這個(gè)數(shù)可以整除N。不過在程式中使用開根號(hào)會(huì)精確度的問題,所以可以使用i*i<=N進(jìn)行檢查,且執(zhí)行更快。再來假設(shè)有一個(gè)篩子存放1～N,例如：23456789101112131415161718192021........N先將2的倍數(shù)篩去：23579111315171921........N再將3的倍數(shù)篩去：235711131719........N再來將5的倍數(shù)篩去,再來將7的質(zhì)數(shù)篩去,再來將11的倍數(shù)篩去........,如此進(jìn)行到最后留下的數(shù)就都是質(zhì)數(shù),這就是Eratosthenes篩選方法〔EratosthenesSieveMethod。檢查的次數(shù)還可以再減少,事實(shí)上,只要檢查6n+1與6n+5就可以了,也就是直接跳過2與3的倍數(shù),使得程式中的if的檢查動(dòng)作可以減少。實(shí)作C#include<stdio.h>#include<stdlib.h>#defineN1000intmain<void>{inti,j;intprime[N+1];for<i=2;i<=N;i++>prime[i]=1;for<i=2;i*i<=N;i++>{//這邊可以改進(jìn)if<prime[i]==1>{for<j=2*i;j<=N;j++>{if<j%i==0>prime[j]=0;}}}for<i=2;i<N;i++>{if<prime[i]==1>{printf<"%4d",i>;if<i%16==0>printf<"\n">;}}printf<"\n">;return0;}

16.AlgorithmGossip:超長(zhǎng)整數(shù)運(yùn)算〔大數(shù)運(yùn)算說明解法一個(gè)變數(shù)無法表示超長(zhǎng)整數(shù),則就使用多個(gè)變數(shù),當(dāng)然這使用陣列最為方便,假設(shè)程式語言的最大資料型態(tài)可以儲(chǔ)存至65535的數(shù)好了,為了計(jì)算方便及符合使用十進(jìn)位制的習(xí)慣,讓每一個(gè)陣列元素可以儲(chǔ)存四個(gè)位數(shù),也就是0到9999的數(shù),例如：很多人問到如何計(jì)算像50!這樣的問題,解法就是使用程式中的乘法函式,至于要算到多大,就看需求了。由于使用陣列來儲(chǔ)存數(shù)值,關(guān)于數(shù)值在運(yùn)算時(shí)的加減乘除等各種運(yùn)算、位數(shù)的進(jìn)位或借位就必須自行定義,加、減、乘都是由低位數(shù)開始運(yùn)算,而除法則是由高位數(shù)開始運(yùn)算,這邊直接提供加減乘除運(yùn)算的函式供作參考,以下的N為陣列長(zhǎng)度。voidadd<int*a,int*b,int*c>{inti,carry=0;for<i=N-1;i>=