C语言经典算法大全.pdf

《C语言经典算法大全.pdf》由会员分享，可在线阅读，更多相关《C语言经典算法大全.pdf（131页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、C C 语言经典算法大全语言经典算法大全老掉牙河内塔费式数列巴斯卡三角形三色棋老鼠走迷官（一）老鼠走迷官（二）骑士走棋盘八个皇后八枚银币生命游戏字串核对双色、三色河内塔背包问题（Knapsack Problem）数、运算蒙地卡罗法求 PIEratosthenes筛选求质数超长整数运算（大数运算）长 PI最大公因数、最小公倍数、因式分解完美数阿姆斯壮数最大访客数中序式转后序式（前序式）后序式的运算关于赌博洗扑克牌（乱数排列）Craps赌博游戏约瑟夫问题（Josephus Problem）集合问题排列组合格雷码（Gray Code）产生可能的集合1/131m元素集合的n个元素子集数字拆解排序得分排

2、行选择、插入、气泡排序Shell 排序法-改良的插入排序Shaker 排序法-改良的气泡排序Heap 排序法-改良的选择排序快速排序法（一）快速排序法（二）快速排序法（三）合并排序法基数排序法搜寻循序搜寻法（使用卫兵）二分搜寻法（搜寻原则的代表）插补搜寻法费氏搜寻法矩阵稀疏矩阵多维矩阵转一维矩阵上三角、下三角、对称矩阵奇数魔方阵4N 魔方阵2(2N+1)魔方阵2/1311.1.河内之塔河内之塔说明说明河内之塔(Towers of Hanoi)是法国人M.Claus(Lucas)于1883年从泰国带至法国的，河内为越战时北越的首都，即现在的胡志明市；1883年法国数学家 Edouard Luca

3、s曾提及这个故事，据说创世纪时Benares有一座波罗教塔，是由三支钻石棒（Pag）所支撑，开始时神在第一根棒上放置64个由上至下依由小至大排列的金盘（Disc），并命令僧侣将所有的金盘从第一根石棒移至第三根石棒，且搬运过程中遵守大盘子在小盘子之下的原则，若每日仅搬一个盘子，则当盘子全数搬运完毕之时，此塔将毁损，而也就是世界末日来临之时。解法解法如果柱子标为ABC，要由A搬至C，在只有一个盘子时，就将它直接搬至C，当有两个盘子，就将B当作辅助柱。如果盘数超过2个，将第三个以下的盘子遮起来，就很简单了，每次处理两个盘子，也就是：A-B、A-C、B-C这三个步骤，而被遮住的部份，其实就是进入程式的

4、递回处理。事实上，若有n个盘子，则移动完毕所需之次数为2n-1，所以当盘数为64时，则所需次数为：2-1=184467445为5.782e+16年，也就是约5000世纪，如果对这数字没什幺概念，就假设每秒钟搬一个盘子好了，也要约5850亿年左右。#include void hanoi(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

5、main()int n;printf(请输入盘数：);scanf(%d,&n);hanoi(n,A,B,C);return 0;643/1312.Algorithm Gossip:2.Algorithm Gossip:费式数列费式数列说明说明Fibonacci为1200年代的欧洲数学家，在他的着作中曾经提到：若有一只免子每个月生一只小免子，一个月后小免子也开始生产。起初只有一只免子，一个月后就有两只免子，二个月后有三只免子，三个月后有五只免子（小免子投入生产）.。如果不太理解这个例子的话，举个图就知道了，注意新生的小免子需一个月成长期才会投入生产，类似的道理也可以用于植物的生长，这就是Fibo

6、nacci数列，一般习惯称之为费氏数列，例如以下：1、1、2、3、5、8、13、21、34、55、89.解法解法依说明，我们可以将费氏数列定义为以下：fn=fn-1+fn-2fn=fn-1+fn-2if n 1if n 1fn=nfn=nif n=0,1if n=0,1#include#include#define N 20int 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;4/1313.3

7、.巴斯卡三角形巴斯卡三角形#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 p;void main()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();/*排版设定结束*/printf(%3d,combi(n,r);printf(n);5/1314.Algorithm Gossip:4.Algorit

8、hm Gossip:三色棋三色棋说明说明三色旗的问题最早由E.W.Dijkstra所提出，他所使用的用语为Dutch Nation Flag(Dijkstra为荷兰人)，而多数的作者则使用Three-Color Flag来称之。假设有一条绳子，上面有红、白、蓝三种颜色的旗子，起初绳子上的旗子颜色并没有顺序，您希望将之分类，并排列为蓝、白、红的顺序，要如何移动次数才会最少，注意您只能在绳子上进行这个动作，而且一次只能调换两个旗子。解法解法在一条绳子上移动，在程式中也就意味只能使用一个阵列，而不使用其它的阵列来作辅助，问题的解法很简单，您可以自己想像一下在移动旗子，从绳子开头进行，遇到蓝色往前移，

9、遇到白色留在中间，遇到红色往后移，如下所示：只是要让移动次数最少的话，就要有些技巧：如果图中W所在的位置为白色，则W+1，表示未处理的部份移至至白色群组。如果W部份为蓝色，则B与W的元素对调，而B与W必须各+1，表示两个群组都多了一个元素。如果W所在的位置是红色，则将W与R交换，但R要减1，表示未处理的部份减1。注意B、W、R并不是三色旗的个数，它们只是一个移动的指标；什幺时候移动结束呢？一开始时未处理的R指标会是等于旗子的总数，当R的索引数减至少于W的索引数时，表示接下来的旗子就都是红色了，此时就可以结束移动，如下所示：#include#include#include#define BLUE

10、 b#define WHITE w#define RED r#define SWAP(x,y)char temp;temp=colorx;colorx=colory;colory=temp;int main()char color=r,w,b,w,w,6/131b,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+;e

11、lse if(colorwFlag=BLUE)S,wFlag);bFlag+;wFlag+;else while(wFlag rFlag&colorrFlag=RED)rFlag-;S,wFlag);rFlag-;for(i=0;i strlen(color);i+)printf(%c,colori);printf(n);return 0;7/1315.Algorithm Gossip:5.Algorithm Gossip:老鼠走迷官（一）老鼠走迷官（一）说明说明老鼠走迷宫是递回求解的基本题型，我们在二维阵列中使用2表示迷宫墙壁，使用1来表示老鼠的行走路径，试以程式求出由入口至出口的路径。解法

12、解法老鼠的走法有上、左、下、右四个方向，在每前进一格之后就选一个方向前进，无法前进时退回选择下一个可前进方向，如此在阵列中依序测试四个方向，直到走到出口为止，这是递回的基本题，请直接看程式应就可以理解。#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;/入口int endI=5,endJ=5;/出口int succ

13、ess=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();elseprintf();printf(n);if(visit(startI,startJ)=0)printf(n没有找到出口！n);8/131else printf(n显示路径：n);for(i=0;i 7;i+)for(j=0;j 7;j+)if(mazeij=2)printf();else if(mazeij=1)printf();elseprintf();printf(n);return 0;int

14、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);if(success!=1&mazei-1j=0)visit(i-1,j);if(success!=1)mazeij=0;return success;9/1316.Algorithm Gossip:6.Algorithm Gossip:老鼠走迷官（二）老鼠走迷官

15、（二）说明说明由于迷宫的设计，老鼠走迷宫的入口至出口路径可能不只一条，如何求出所有的路径呢？解法解法求所有路径看起来复杂但其实更简单，只要在老鼠走至出口时显示经过的路径，然后退回上一格重新选择下一个位置继续递回就可以了，比求出单一路径还简单，我们的程式只要作一点修改就可以了。#include#include void visit(int,int);int maze99=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,

16、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;/出口int main(void)int i,j;printf(显示迷宫：n);for(i=0;i 7;i+)for(j=0;j 7;j+)if(mazeij=2)printf();elseprintf();printf(n);visit(startI,startJ);10/131return 0;void visit(int i,int j)int m,n;mazeij=1;if(i=endI&j=endJ)pr

17、intf(n显示路径：n);for(m=0;m 9;m+)for(n=0;n 9;n+)if(mazemn=2)printf();else if(mazemn=1)printf();elseprintf();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;11/1317.Algorithm Gossip:7.Algorithm Gossip:骑士走棋盘骑士走棋盘说明说明骑士旅游（Knight

18、 tour）在十八世纪初倍受数学家与拼图迷的注意，它什么时候被提出已不可考，骑士的走法为西洋棋的走法，骑士可以由任一个位置出发，它要如何走完 所有的位置？解法解法骑士的走法，基本上可以使用递回来解决，但是纯綷的递回在维度大时相当没有效率，一个聪明的解法由J.C.Warnsdorff在1823年提出，简单的说，先将最难的位置走完，接下来的路就宽广了，骑士所要走的下一步，为下一步再选择时，所能走的步数最少的一步。，使用这个方法，在不使用递回的情况下，可以有较高的机率找出走法（找不到走法的机会也是有的）。#include int board88=0;int main(void)int startx,

19、starty;int i,j;printf(输入起始点：);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,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;12/131/测试下一步

20、的出路int nexti8=0;int nextj8=0;/记录出路的个数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;/如果是边界了，不可走if(tmpi 0|tmpj 7|tmpj 7)continue;/如果这个方向可走，记录下来if(boardtmpitmpj=0)nextil=tm

21、pi;nextjl=tmpj;/可走的方向加一个l+;count=l;/如果可走的方向为0个，返回if(count=0)13/131return 0;else if(count=1)/只有一个可走的方向/所以直接是最少出路的方向min=0;else/找出下一个位置的出路数for(l=0;l count;l+)for(k=0;k 8;k+)tmpi=nextil+ktmove1k;tmpj=nextjl+ktmove2k;if(tmpi 0|tmpj 7|tmpj 7)continue;if(boardtmpitmpj=0)existsl+;tmp=exists0;min=0;/从可走的方向中寻

22、找最少出路的方向for(l=1;l count;l+)if(existsl tmp)tmp=existsl;min=l;/走最少出路的方向i=nextimin;j=nextjmin;boardij=m;return 1;14/1318.Algorithm Gossip:8.Algorithm Gossip:八皇后八皇后说明说明西洋棋中的皇后可以直线前进，吃掉遇到的所有棋子，如果棋盘上有八个皇后，则这八个皇后如何相安无事的放置在棋盘上，1970年与1971年，E.W.Dijkstra与N.Wirth曾经用这个问题来讲解程式设计之技巧。解法解法关于棋盘的问题，都可以用递回求解，然而如何减少递回的次

23、数？在八个皇后的问题中，不必要所有的格子都检查过，例如若某列检查过，该该列的其它格子就不用再检查了，这个方法称为分支修剪。#include#include#define N 8int columnN+1;/同栏是否有皇后，1表示有int rup2*N+1;/右上至左下是否有皇后int lup2*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;back

24、track(1);return 0;void showAnswer()int x,y;15/131printf(n解答%dn,+num);for(y=1;y=N;y+)for(x=1;x N)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;16/1319.Algorithm Gossip:9.Algorithm Gossip:八枚银币八枚银币说明说明

25、现有八枚银币a b c d e f g h，已知其中一枚是假币，其重量不同于真币，但不知是较轻或较重，如何使用天平以最少的比较次数，决定出哪枚是假币，并得知假币比真币较轻或较重。解法解法单就求假币的问题是不难，但问题限制使用最少的比较次数，所以我们不能以单纯的回圈比较来求解，我们可以使用决策树（decision tree），使用分析与树状图来协助求解。一个简单的状况是这样的，我们比较a+b+c与d+e+f，如果相等，则假币必是 g或h，我们先比较g或h哪个较重，如果g较重，再与a比较（a是真币），如果g等于a，则g为真币，则h为假币，由于h比g轻而 g是真币，则h假币的重量比真币轻。#incl

26、ude#include#include void compare(int,int,int,int);void eightcoins(int);int main(void)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);elseprintf(n假币%d 较轻,j+1)

27、;void eightcoins(int coins)if(coins0+coins1+coins2=coins3+coins4+coins5)if(coins6 coins7)compare(coins,6,7,0);elsecompare(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(coi

28、ns0+coins3 coins1+coins4)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);18/13110.Algorithm Gossip:10.Algorithm Gossip:生命游戏生命游戏说明说明生命游戏（game of life）为1970年由英国数学家J.H.Conway所提出，某一细胞的邻居包括上、下、左、右、左上、左下、右上与右下相邻之细胞，游戏

29、规则如下：孤单死亡：如果细胞的邻居小于一个，则该细胞在下一次状态将死亡。拥挤死亡：如果细胞的邻居在四个以上，则该细胞在下一次状态将死亡。稳定：如果细胞的邻居为二个或三个，则下一次状态为稳定存活。复活：如果某位置原无细胞存活，而该位置的邻居为三个，则该位置将复活一细胞。解法解法生命游戏的规则可简化为以下，并使用CASE比对即可使用程式实作：邻居个数为0、1、4、5、6、7、8时，则该细胞下次状态为死亡。邻居个数为2时，则该细胞下次状态为复活。邻居个数为3时，则该细胞下次状态为稳定。#include#include#include#define MAXROW 10#define MAXCOL 25

30、#define DEAD 0#define ALIVE 1int 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:19/131cas

31、e 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;row+)for(col=0;col MAXCOL;col+)maprow

32、col=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&20/1310=col&col MAXCOL)maprowcol=ALIVE;else if(row=-1|col=-1)break;elseprintf(x,y)exceeds map ranage!

33、);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(co

34、l=0;col MAXCOL;col+)if(maprowcol=ALIVE)putchar(#);elseputchar(-);void copyMap()int row,col;for(row=0;row MAXROW;row+)for(col=0;col MAXCOL;col+)maprowcol=newmaprowcol;21/13111.Algorithm Gossip:11.Algorithm Gossip:字串核对字串核对说明说明今日的一些高阶程式语言对于字串的处理支援越来越强大（例如Java、Perl等），不过字串搜寻本身仍是个值得探讨的课题，在这边以Boyer-Moore法来

35、说明如何进行字串说明，这个方法快且原理简洁易懂。解法解法字串搜寻本身不难，使用暴力法也可以求解，但如何快速搜寻字串就不简单了，传统的字串搜寻是从关键字与字串的开头开始比对，例如 Knuth-Morris-Pratt 演算法 字串搜寻，这个方法也不错，不过要花时间在公式计算上；Boyer-Moore字串核对改由关键字的后面开始核对字串，并制作前进表，如果比对不符合则依前进表中的值前进至下一个核对处，假设是 p好了，然后比对字串中p-n+1至p的值是否与关键字相同。如果关键字中有重复出现的字元，则前进值就会有两个以上的值，此时则取前进值较小的值，如此就不会跳过可能的位置，例如texture这个关键

36、字，t的前进值应该取后面的3而不是取前面的7。#include#include#include void table(char*);/建立前进表int search(int,char*,char*);/搜寻关键字void substring(char*,char*,int,int);/取出子字串int skip256;int main(void)char str_input80;char str_key80;char tmp80=0;int m,n,p;printf(请输入字串：);gets(str_input);printf(请输入搜寻关键字：);gets(str_key);m=strlen

37、(str_input);/计算字串长度n=strlen(str_key);table(str_key);p=search(n-1,str_input,str_key);while(p!=-1)substring(str_input,tmp,p,m);22/131printf(%sn,tmp);p=search(p+n+1,str_input,str_key);printf(n);return 0;void table(char*key)int k,n;n=strlen(key);for(k=0;k=255;k+)skipk=n;for(k=0;k n-1;k+)skipkeyk=n-k-1;i

38、nt search(int p,char*input,char*key)int i,m,n;char tmp80=0;m=strlen(input);n=strlen(key);while(p m)substring(input,tmp,p-n+1,p);if(!strcmp(tmp,key)/比较两字串是否相同return p-n+1;p+=skipinputp;return-1;void substring(char*text,char*tmp,int s,int e)int i,j;for(i=s,j=0;i=e;i+,j+)mpj=texti;tmpj=0;23/13112.Algor

39、ithm Gossip:12.Algorithm Gossip:双色、三色河内塔双色、三色河内塔说明说明双色河内塔与三色河内塔是由之前所介绍过的河内塔规则衍生而来，双色河内塔的目的是将下图左上的圆环位置经移动成为右下的圆环位置：而三色河内塔则是将下图左上的圆环经移动成为右上的圆环：解法解法无论是双色河内塔或是三色河内塔，其解法观念与之前介绍过的河内塔是类似的，同样也是使用递回来解，不过这次递回解法的目的不同，我们先来看只有两个盘的情况，这很简单，只要将第一柱的黄色移动至第二柱，而接下来第一柱的蓝色移动至第三柱。再来是四个盘的情况，首先必须用递回完成下图左上至右下的移动：接下来最底层的就不用管它

40、们了，因为它们已经就定位，只要再处理第一柱的上面两个盘子就可以了。那么六个盘的情况呢？一样！首先必须用递回完成下图左上至右下的移动：24/131接下来最底层的就不用管它们了，因为它们已经就定位，只要再处理第一柱上面的四个盘子就可以了，这又与之前只有四盘的情况相同，接下来您就知道该如何进行解题了，无论是八个盘、十个盘以上等，都是用这个观念来解题。那么三色河内塔呢？一样，直接来看九个盘的情况，首先必须完成下图的移动结果：接下来最底两层的就不用管它们了，因为它们已经就定位，只要再处理第一柱上面的三个盘子就可以了。双色河内塔 C 实作#include void hanoi(int disks,char

41、 source,char temp,char target)if(disks=1)printf(move disk from%c to%cn,source,target);printf(move disk from%c to%cn,source,target);else hanoi(disks-1,source,target,temp);hanoi(1,source,temp,target);hanoi(disks-1,temp,source,target);void hanoi2colors(int disks)char source=A;char temp=B;char target=C;

42、int i;for(i=disks/2;i 1;i-)hanoi(i-1,source,temp,target);printf(move disk from%c to%cn,source,temp);printf(move disk from%c to%cn,source,temp);hanoi(i-1,target,temp,source);printf(move disk from%c to%cn,temp,target);25/131printf(move disk from%c to%cn,source,temp);printf(move disk from%c to%cn,sourc

43、e,target);int main()int n;printf(请输入盘数：);scanf(%d,&n);hanoi2colors(n);return 0;三色河内塔 C 实作#include void hanoi(int disks,char source,char temp,char target)if(disks=1)printf(move disk from%c to%cn,source,target);printf(move disk from%c to%cn,source,target);printf(move disk from%c to%cn,source,target);e

44、lse hanoi(disks-1,source,target,temp);hanoi(1,source,temp,target);hanoi(disks-1,temp,source,target);void hanoi3colors(int disks)char source=A;char temp=B;char target=C;int i;if(disks=3)printf(move disk from%c to%cn,source,temp);printf(move disk from%c to%cn,source,temp);printf(move disk from%c to%cn

45、,source,target);printf(move disk from%c to%cn,temp,target);printf(move disk from%c to%cn,temp,source);printf(move disk from%c to%cn,target,temp);26/131else hanoi(disks/3-1,source,temp,target);printf(move disk from%c to%cn,source,temp);printf(move disk from%c to%cn,source,temp);printf(move disk from%

46、c to%cn,source,temp);hanoi(disks/3-1,target,temp,source);printf(move disk from%c to%cn,temp,target);printf(move disk from%c to%cn,temp,target);printf(move disk from%c to%cn,temp,target);hanoi(disks/3-1,source,target,temp);printf(move disk from%c to%cn,target,source);printf(move disk from%c to%cn,tar

47、get,source);hanoi(disks/3-1,temp,source,target);printf(move disk from%c to%cn,source,temp);for(i=disks/3-1;i 0;i-)if(i1)hanoi(i-1,target,source,temp);printf(move disk from%c to%cn,target,source);printf(move disk from%c to%cn,target,source);if(i1)hanoi(i-1,temp,source,target);printf(move disk from%c

48、to%cn,source,temp);int main()int n;printf(请输入盘数：);scanf(%d,&n);hanoi3colors(n);return 0;27/13113.Algorithm Gossip:13.Algorithm Gossip:背包问题（背包问题（Knapsack ProblemKnapsack Problem）说明说明假设有一个背包的负重最多可达8公斤，而希望在背包中装入负重范围内可得之总价物品，假设是水果好了，水果的编号、单价与重量如下所示：0李子4KG1苹果5KG2橘子2KG3草莓1KG4甜瓜6KGNT$4500NT$5700NT$2250NT$1

49、100NT$6700解法解法背包问题是关于最佳化的问题，要解最佳化问题可以使用动态规划（Dynamicprogramming），从空集合开始，每增加一个元素就先求出该阶段的最佳解，直到所有的元素加入至集合中，最后得到的就是最佳解。以背包问题为例，我们使用两个阵列value与item，value表示目前的最佳解所得之总价，item表示最后一个放至背包的水果，假设有负重量 18的背包8个，并对每个背包求其最佳解。逐步将水果放入背包中，并求该阶段的最佳解：放入李子背12345678包负重valu450450450450900e00000item放入苹果背12345678包负重valu45057057

50、0570900e00000item111放入橘子28/131背1包负重valueitem放入草莓背包负重valueitem放入甜瓜背包负重valueitem11234567822502225024500570016750279502900023456781100322502335034500570016800379502905032345678110032250233503450057001680037950290503由最后一个表格，可以得知在背包负重8公斤时，最多可以装入9050元的水果，而最后一个装入的 水果是3号，也就是草莓，装入了草莓，背包只能再放入7公斤（8-1）的水果，所以必须看