经典算法大全

所需积分/C币:9 2014-01-22 16:11:49 1.19MB PDF
2
收藏 收藏
举报

27个经典算法实现,老鼠走迷宫、排列组合,河内塔、背包问题等。
37 Algorithm Gossip:快速排序法(-) 92 38: Algorithm Gossip:快速排序法(二) 39 Algorithm Gossip:快速排序法(三) 96 40 Algorithm Gossip:合并排序法 99 41 Algorithm Gossip:基数排序法 42 Algorithm Gossip:序搜寻法(使用卫兵) 43 Algorithm Gossip:二分搜寻法(搜寻原则的代表) 44 Algorithm Gossip:插补搜寻法 ····4·4··· 45 Algorithm Gossip:费氏搜寻法 12 46 Algorithm Gossip:稀疏矩阵… 116 47 Algorithm Gossip:多维矩阵转一维矩阵 …·······*··4··········· 118 48 Algorithm Gossip}上三角、下三角、对称矩阵 ,120 49 Algorithm Gossip:奇数魔方阵 …122 50 Algorithm Gossip:N魔方阵.124 51 Algorithm Gossip:2(2N+1)魔方阵 126 1河内之塔 说明 河内之塔( Towers of Hanoi)是法国人 M. Claus( Lucas于1883年从泰国带至法国的,河内为越战时 北越的首都,即现在的胡志明市;1883年法国数学家 Edouard lucas會提及这个故事,据说创世 纪时 Benares有一座波罗教塔,是由三支钻石棒(Pag)所支撑,开始时神在第一根棒上放置64 个由上至下依由小至大排列的金盘(Disc),并命合僧侣好所有的金盘从第一根石棒移至第三根 石棒,且搬运过程中遵守大盘子在小盘子之下的原则,若每日仅搬一个盘子,则当盘子全数搬 运完毕之时,此塔捋毁损,而也就是世界末日来临之时。 解法如果柱子标为ABC,要由A搬至C,在只有一个盘子时,就捋它直接搬至C,当有两个盘 子,就捋B当作辅助柱。如果盘数超过2个,第三个以下的盘子遮起来,就很简单了,每次处 理两个盘子,也就是:A->B、A~>C、B->C这三个步骤,而被遮住的部份,其实就是进入程式 的递回处理。事实上,若有n个盘子,则移动完毕所需之次数为2^n-1,所以当盘数为64时,则 所需次数为:2-118446744073709551615为505390248594782c+16年,也就是约5000世纪 如果对这数字没什幺概念,就假设每秒钟搬一个盘子好了,也要约5850亿年左右。 include <stdio .h> void hanoi(int n, char A, char B, char C)& if(n==1){ f("Move sheet %d from n",n,A,C); else i hanoi(n-1, A, C, B); printf("Move sheet %d from %c to %cn",n, A, C hanoi(n-1, B, A, C); int main( i Int n print("请输入盘数:"); f("od,&n) hanoi(n,A, B,'C) 2 Algorithm Gossip:费式数列 说明 Fibonacci.1200年代的欧洲数学家,在他的着作中會经提到:「若有一只免子每个月生一只小免 子,一个月后小免子也开始生产。起初只有一只免子,一个月后就有两只免子,二个月后有三 只免子,三个月后有五只免子(小免子投入生产)… 如果不太理解这个例子的话,举个图就知道了,注意新生的小免子需一个月成长期才会投入生 产,类似的道理也可以用于植物的生长,这就是 bonacci数列,一般习惯称之为费氏数列,例 如以下:1、1、2、3、5、8、13、21、34、55、89 解法 依说明,我们可以捋费氏数列定义为以下 fn=fn-1+ fn-2 if'n>1 ifn=0. 1 #include <stdio. h> #include <stdlib. h> #define n 20 int main(void)i int Fib[N-=0; int 1: Fib[0-0 Fib[1]=1; for(i=2; i<N; i++ F1b[]= Fib[i-1]+ Fibli-2] r(i=0;i<N;i++) printf("%d", Fib[i]; printf("n ); return 0; 3.帕斯卡三角形(杨辉三角) 斯卡三角B ooe 1 6 10105 52015 72135352171 1828567056288 936841261268436q1 104512021025221022045101 115516533045246233016555111 126622049579292479249522066121 include <stdio.h> #define 12 long combi (int n, int r)i int 1 long=1; for(i=1 p=p*(n-i计+1)/i; return void paint i tn r. t: for(n=0;n<=N;n++){ for(r=0; r<=n;r++)& nti;/*排版设定开始* 0){ for(i=0;i=(N-n);i++) printf("); felse i printf(") }/*排版设定结束 printf( %3d", combi(n, r)) printf("u"); 4 Algorithm Gossip:三色棋 说明 色旗的问题最早由 E. W Dijkstral提出,他所使用的用语为 Dutch Nation Flag(Dijkstra为荷兰 人),而多数的作者则使用 Three-Color Flag来称之。 假设有一条绳子,上面有红、白、蓝三种颜色的旗子,起初绳子上的旗子颜色并没有顺序,您 希望之分类,并排列为蓝、白、红的顺序,要如何移动次数才会最少,注意您只能在绳子上 进行这个动作,而且一次只能调换两个旗子。 解法 在一粲绳子上移动,在程式中也就意味只能使用一个阵列,而不使用其它的阵列来作辅助,问 题的解法很简单,您可以自己想像一下在移动旗子,从绳子开头进行,遇到蓝色往前移,遇到 白色留在中间,遇到红色往后移,如下所示 只是要让移动次数最少的话,就要有些技巧 如果图中W所在的位置为白色,则W+1,表示未处理的部份移至至白色群组。 如果W部份为蓝色,则B与W的元幸对调,而B与W必须各+1,表示两个群组都多了一个元素。 如果W所在的位置是红色,则烀W与R交换,但R要减1,表示未处理的部份减1 注意B、W、R并不是三色旗的个数,它们只是一个移动的指标;什丛时候移动结束呢?一开始 时未处理的R指标会是等于旗子的总数,当R的索引数减至少于W的索引数时,表示接下来的旗 子就都是红色了,此时就可以结束移动,如下所示 #include <stdio. h> #include <stdlib. h> #include <string. h> #define blue ' b #define whiten #define red r #define SWAP(x, y) char temp ip=colorx] color[x]-color[y]; colorly-temp, i int main( i char color[ =I'r, w,'b, w,w b,r,"b,"w,,"O"} int wflag =0 int fLag=0 int rFlag-- strlen(color)-1 int for(i=0; i<strlen(color); 1++) tf("%c",colori) f("n"); while(w Flag <=rFlag)( if(color[wFlag]--- WHItE) wFlag else if(color wFlag]== BLud& SWAP(bFlag, wFlag); bLag++; wFlag++ while(wFlag rFlag & color[rFlag]== RED) rH lag SWAP(fLag, wFlag rFlag-- for(i=0; i< strlen(color); 1++) printf" colorl]) printf ); return O 5 Algorithm Gossip:老鼠走迷官( 说明老凰走迷宫是递回求解的基本题型,我们在二维阵列中使用2表示迷宫墙壁,使用来表 示老鼠的行走路径,试以程式求出由入口至出口的路徑。 解法老風的走法有上、左、下、右四个方向,在每前进一格之后就选一个方向前进,无法前 进时退回选择下一个可前进方向,如此在阵列中依序测试四个方向,直到走到出口为止,这是 递回的基本题,请直接看程式应就可以理解。 #include <stdio. h> #include <stdlib. h> Int maze[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} int startI=1, start=1;∥入口 int end I=5,endJ=5;∥出口 int success 0; int main(void)i at 1,]: printi("显示迷宫:n"): fori=0;i<7;i++){ forge=0;j<7:j++) if(maze[10]==2) printf("o"); printf("); printf("u") if(visit(starti, start ==0) printf(("hn没有找到出口!mn"); else printi"显示路徑:mn"); for(i=0,i<7;i++){ for=0;j<7;j++){ i[j]==2) printf(""); else if(mazel[i==1) printf("o) printf( printf("n; return O int visit(int 1, inti mazei[j-1 if(i==endi &&j==endD) success =1 if(success !=1 & maze[il[j+1]-=0)visit(i, j+l if(success !1 & maze[i+10l-0) visit(i+1,j); if(success !=1 & maze[=0)visit(i, j-1); if(success ! =1 & maze[i-1[]-=0) visit(i-1,j) maz

...展开详情
试读 127P 经典算法大全
立即下载 身份认证后 购VIP低至7折
一个资源只可评论一次,评论内容不能少于5个字
您会向同学/朋友/同事推荐我们的CSDN下载吗?
谢谢参与!您的真实评价是我们改进的动力~
关注 私信
上传资源赚钱or赚积分
最新推荐
经典算法大全 9积分/C币 立即下载
1/127
经典算法大全第1页
经典算法大全第2页
经典算法大全第3页
经典算法大全第4页
经典算法大全第5页
经典算法大全第6页
经典算法大全第7页
经典算法大全第8页
经典算法大全第9页
经典算法大全第10页
经典算法大全第11页
经典算法大全第12页
经典算法大全第13页
经典算法大全第14页
经典算法大全第15页
经典算法大全第16页
经典算法大全第17页
经典算法大全第18页
经典算法大全第19页
经典算法大全第20页

试读结束, 可继续阅读

9积分/C币 立即下载