acm程序设计算法讲解.docx

《acm程序设计算法讲解.docx》由会员分享，可在线阅读，更多相关《acm程序设计算法讲解.docx（121页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、目录1 .河内之塔32 .Algorithm Gossip:费式数歹43 .巴斯卡三角形55 .Algorithm Gossip:老鼠走迷官（一）86 .Algorithm Gossip:老鼠走迷官（二）107 .Algorithm Gossip:骑士走棋盘118 .Algorithm Gossip:l皇后149 .Algorithm Gossip:枚银币1610 .Algorithm Gossip: 生命游戏1812 .Algorithm Gossip: 双色、二色河内塔2313 .Algorithm Gossip: 背包问题 （Knapsack Problem） 2714 .Algorit

2、hm Gossip: 蒙地卡罗法求 PI3215 .Algorithm Gossip: Eratosthenes 筛选求质数3316 .Algorithm Gossip:超长整数运算（大数运算）3517 .Algorithm Gossip:长 PI3718 .Algorithm Gossip:最大公因数、最小公倍数、因式分解4019 . Algorithm Gossip: 完美数4320 .Algorithm Gossip: B可姆斯壮数4621 .Algorithm Gossip: 最大访客数4822 .Algorithm Gossip:中序式转后丿予式 （冃序式）5023 .Algorit

3、hm Gossip:后序式的足算5324 .Algorithm Gossip:洗扑克牌（乱数排列）5525 .Algorithm Gossip: Craps 赌博戏5726 .Algorithm Gossip: 约瑟夫问题 （Josephus Problem） 5927 .Algorithm Gossip:却F歹组合6128 . Algorithm Gossip: 格雷码 （Gray Code） 6329 .Algorithm Gossip:产生可能的集合6530 .Algorithm Gossip: m 兀素集合的 n 个兀素子集6831 .Algorithm Gossip: 数字拆解703

4、2 .Algorithm Gossip:得分排行7333 .Algorithm Gossip: 选择、插入、泡排序7534 .Algorithm Gossip: Shel!排序法改良的插入排序7935 .Algorithm Gossip: Shaker排序法改良的气泡排序8236 .排序法-改良的选择排序8437 .Algorithm Gossip: 快速排序法（一）8838 .Algorithm Gossip:快速排序法（二）9039 .Algorithm Gossip: 快速HF丿予法 （二） 9240 . Algorithm Gossip:合并排手法9541 .Algorithm Gos

5、sip:基数排丿予法9842 .Algorithm Gossip:循序搜寻法（使用卫兵）10043 .Algorithm Gossip:二分搜寻法（搜寻原则的代表）10245 .Algorithm Gossip:费氏搜寻法10846 .Algorithm Gossip:稀疏矩阵11247 .Algorithm Gossip:多维矩阵转维矩阵11448 .Algorithm Gossip:上三角、 下二角、 对称矩阵11549 .Algorithm Gossip:奇数魔方阵11850 .Algorithm Gossip:4N 魔方阵11951 .Algorithm Gossip:2（2N+1）

6、魔方阵1211 .河内之塔 说 明河内之塔(Towers of Hanoi)是法国人M.Claus(Lucas)于1883年从泰国带至法国的,河内为越战时北越的首都,即现在的胡志明市;1883年法国数学家Edouard Lucas曾提及这个故事,据说 创世纪时Benares有一座波罗教塔,是由三支钻石棒(Pag)所支撑,开始时神在第一根棒上放 置64个由上至下依由小至大排列的金盘(Disc),并命令僧侣将所有的金盘从第一根石棒移至第 三根石棒,且搬运过程中遵守大盘子在小盘子之下的原则，若每日仅搬个盘子，则当盘子全 数搬运完毕之时，此塔将毁损，而也就是世界末日来临之时。解法如果柱子标为ABC,要

7、由A搬至C,在只有一个盘子时，就将它宜接搬至C,当有两个盘子,就将B当作辅助柱。如果盘数超过2个，将第三个以下的盘子遮起来，就很简单了，每次处 理两个盘子，也就是:A-B、A C、B-C这三个步骤,而被遮住的部份，其实就是进入程式 的递回处理。事实匕若有n个盘子，则移动完毕所需之次数为2n-1,所以当盘数为64时，则 所需次数为:2 1 = 18446744073709551615为5.05390248594782e+16年,也就是约5000世纪, 如果对这数字没什幺概念,就假设每秒钟搬个盘子好了,也要约5850亿年左右。#includc void hanoi(int n, char A, c

8、har B, char C) if(n = 1) printf(nMove sheet %d from %c to %cnH, n, A, C);)else hanoi(n-l, A, C, B);printffMove sheet %d from %c to %cn, n, A, C);hanoi(n-l, B, A, C);int main() int n;printf(”请输入盘数:); scanfid”, &n);hanoi(n, A, B, C,);return 0;2 .Algorithm Gossip:费式数列说明Fibonacci为1200年代的欧洲数学家,在他的着作中曾经提到

9、:若有一只免子每个月生只小免 子,个月后小免子也开始生产。起初只有一只免子,个月后就有两只免子,二个月后有三 只免子,三个月后有五只免子(小免子投入生产).如果不太理解这个例子的话,举个图就知道了,注意新生的小免子需一个月成长期才会投入生 产,类似的道理也可以用于植物的生长，这就是Fibonacci数列,一般习惯称之为费氏数列，例 如以下:1、1、2、3、5、8、13、21、34、55、89.解法依说明,我们可以将费氏数列定义为以下: fn = fn-1 + fn-2 if n 1fn = nif n = 0,1#include #include /define N 20int main(vo

10、id) int FibN = 0;inti;FibO = 0;Fibl = 1;fbr(i = 2;iN; i+)Fibi = Fibi-l + Fibi-2;fbr(i = 0;iN; i+)printf(n%d Fibi);printifn)；return 0;3 .巴斯卡三角形#include #define N 12long combi(int n, int r)int i;long p = 1；fbr(i= l；i=r; i+)p = p * (n-i+l)/i;return p;void paint() int n, r, t;fbr(n = 0; n = N; n-H-) fbr

11、(r = 0; r = n; r+) inti;/排版设定开始/ if(r = O) for(i = 0; i = (N-n); i-H-) printff );else printf(M M);/排版设定结束/printff%3d“，combi(n, r);printffn”);4.Algorithm Gossip:三色棋说明三色旗的问题最早由E.W.Dijkstra所提出,他所使用的用语为Dutch Nation Flag(Dijkstra为荷兰 人),而多数的作者则使用Three-Color Flag来称之。假设有一条绳子,上面有红、白、蓝三种颜色的旗子,起初绳子上的旗子颜色并没有顺序,

12、您 希望将之分类,并排列为蓝、白、红的顺序，要如何移动次数会最少，注意您只能在绳子上 进行这个动作，而且一次只能调换两个旗子。解法在一条绳子上移动,在程式中也就意味只能使用个阵列，而不使用其它的阵列来作辅助，问 题的解法很简单，您可以自己想像一下在移动旗子,从绳子开头进行，遇到蓝色往前移，遇到 白色留在中间，遇到红色往后移,如下所示:只是要让移动次数最少的话，就要有些技巧:如果图中W所在的位置为白色,则W+1,表示未处理的部份移至至白色群组。如果W部份为蓝色，则B与W的元素对调,而B与W必须各+1,表示两个群组都多了一个元素。如果W所在的位置是红色，则将W与R交换，但R要减1,表示未处理的部份

13、减1。注意B、W、R并不是三色旗的个数,它们只是个移动的指标;什幺时候移动结束呢? 一开始 时未处理的R指标会是等于旗子的总数，当R的索引数减至少于W的索引数时,表示接下来的旗 子就都是红色了，此时就可以结束移动，如下所示:#include #include /include #define BLUE V/define WHITE W#define RED T/define SWAP(x, y) char temp; temp = colorx;colorx = colory; colory = temp; int main() char color = TJw 丁bww；b, Y, b, *

14、w/r丁、0七int wFlag = 0;int bFlag = 0;int rFlag = strlen(color) - 1;inti;fbr(i = 0; i strlen(color); i-H-) printf(M%c H, colori);printf(Mn);while(wFlag = rFlag) if(colorwFlag = WHITE)wHag+;else if(colorwFlag = BLUE) SWAP(bFlag, wFlag);bFlag-H-; wFlag-H-;)else while(wFlag rFlag & colorrFlag = RED) rFlag

15、-；SWAP(rFlag, wFlag);rFlag-；fbr(i = 0; i strlen(color); i-H-) printf(c ”，colori);printf(n)；return 0;5 .Algorithm Gossip:老鼠走迷官（一）说明老鼠走迷宫是递回求解的基本题型,我们在二维阵列中使用2表示迷宫墙壁,使用1来表 示老鼠的行走路径,试以程式求出由入口至出口的路径。解法老鼠的走法有上、左、下、右四个方向，在每前进一格之后就选个方向前进,无法前 进时退回选择下个可前进方向，如此在阵列中依序测试四个方向，直到走到出口为止，这是 递回的基本题,请直接看程式应就可以理解。#inc

16、lude #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 startl = 1, startJ = 1; 入口 int endl = 5, endJ = 5J 出口 int success = 0;int main(void) int i,j;printf(显示迷宫:n);f

17、or(i = 0; i 7; i+) fbr(j = 0；j7；j+)if(mazeij = 2) printf(.);elseprintf(); printf(n);if(visit(startl, startJ) = 0)primf(”n没有找到出口! W”)； else printf(n显示路径:n”);fbr(i = 0; i 7; i+) for(j = 0;j7;j+) if(mazeij = 2) printf(;else if(mazeij = 1) prin氓。);elseprintf(M ;printf(,nM);return 0;int visit(int i, int

18、j) mazeij = 1;ifi = endl & j = endJ)success = 1;if(success != 1 & mazeij+l = 0) visit(i, j+1);if(success != 1 & mazei+lj = 0) visit(i+l, j);if(success != 1 & mazeij-l = 0) visit(i, j-1);if(success != 1 & mazei-lj = 0) visit(i-l, j);ifi(success != 1)mazeij = 0;return success;6 .Algorithm Gossip:老鼠走迷官

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

20、 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;int startl = 1, start1 = 1; 入口int endl = 7, endJ = 7; 出口int main(void) int i,j;printf(显示迷宫:nn);for(i = 0; i 7; i+) for(j = 0;j7;j-H-)if(mazeij = 2) printfC.);elseprints ;printf(

21、Mnn);visit(startl, start!);return 0;void visit(int i, int j) int m, n;mazeij = 1;if( = endl & j = endJ) printf(n显示路径:nM); fbr(m = 0; m 9; m+) fbr(n = 0; n 9; n+) ifi(mazemn = 2) printf(.);else ifmazemn = 1) printff”)；elseprintf(H w); printf(unM);if(mazeij+l = 0) visit(i, j+1); if(mazei+lj = 0) visit

22、(i+l, j); if(mazeij-l = 0) visit(i, j-1);if(mazei-lj = 0) visit(i-l, j);mazeij = 0;7 .Algorithm Gossip:骑士走棋盘说明骑士旅游(Knight tour)在十八世纪初倍受数学家与拼图迷的注意,它什么时候被提出 已不可考,骑士的走法为西洋棋的走法,骑士可以由任一个位置出发,它要如何走完所有的位 置?解法骑士的走法,基本上可以使用递回来解决,但是纯粹的递回在维度大时相当没有效率,个聪明的解法由J.C.Wamsdorffffil823年提出,简单的说,先将最难的位置走完,接下来的路 就宽广了,骑士所要

23、走的下步,为下步再选择时,所能走的步数最少的步。，使用这个 方法,在不使用递回的情况下,可以有较高的机率找出走法（找不到走法的机会也是有的）。#include int board 网网=0;int main(void) int startx, starty;inti J;prin氓输入起始点:);scanfin%d %d”，&startx, &starty);if(travel(startx, starty) printf(游历完成! n);)else printf(”游历失败! n);)fbr(i = 0; i 8; i+) for(j = 0;j8;j+) printf(u%2d , bo

24、ard口口)；)putchar(n);)return 0;int travel(int x, int y) /Z对应骑士可走的八个方向int ktmovel8 = -251, 2, 2, 1, -1, -2;int ktmove28 = 1,2,2, 1, -1, -2, -2, -1);测试下步的出路int nexti8 = 0;int nextj8 = 0;/记录出路的个数int exists8 = 0;int i, j, k, m, 1;int tmpi, tmpj;int count, min, tmp;1 = X；j = y;boardij = 1;fbr(m = 2; m = 64

25、; m+) fbr(l = 0; 1 8; 1+) existsl = 0;1 = 0;/Z试探个方向for(k = 0; k 8; k+) tmpi = i + ktmovelk; tmpj = j + ktmove2k;/如果是边界了,不可走if(tmpi 0 | tmpj 7 | tmpj 7) continue;/如果这个方向可走,记录下来 ifi(boardtmpitmpj = 0) nextil = tmpi;nextjl = tmpj;可走的方向加一个 1+;count = 1;/如果可走的方向为。个,返回ififcount = 0) return 0;else ififcoun

26、t = 1) /Z只有一个可走的方向/所以直接是最少出路的方向 min = 0;)else (/Z找出下个位置的出路数 fbr(l = 0; 1 count; 1-H-) fbr(k = 0; k 8; k+) tmpi = nextil + ktmovelk;tmpj = nextjl + ktmove2k;iRtmpi 0 | tmpj 7 | tmpj 7) continue;)ifl；boardtmpitmpj = 0) existsl-H-;)tmp = exists0;min = 0;/从可走的方向中寻找最少出路的方向 for(l = 1; 1 count; 1-H-) ifi(e

27、xistsl tmp) tmp = existsl; min = 1;/Z走最少出路的方向 i = nextimin;j = nextjmin; boardi|j = m;)return 1;8 .Algorithm Gossip:皇后说明西洋棋中的皇后可以直线前进,吃掉遇到的所有棋子,如果棋盘有八个皇后,则这 个皇后如何相安无事的放置在棋盘上,1970年与1971年,E.W.Dijkstra与N.Wirth曾经用这个问 题来讲解程式设计之技巧。解法关于棋盘的问题,都可以用递冋求解,然而如何减少递回的次数?在八个皇后的问题中, 不必要所有的格子都检查过,例如若某列检查过,该该列的其它格子就不用

28、再检查了,这个方 法称为分支修剪。#include #include /define N 8int columnN+l; /同栏是否有皇后,1表示有int rup2*N+l;/右上至左下是否有皇后int lup2*N+l;/Z左上至右下是否有皇后int queenN+l = ;int num; /Z解答编号void backtrack(int); /Z 递回求解int main(void) int i;num = 0;for(i= l;i=N; i+)columni = 1;fbr(i = 1; i = 2*N; i+) rupi = lupi = 1;backtrack(l);return

29、0;)void showAnswer() int x, y;printffn解答 %dnM, +num);for(y = l；y= N; y+) fbr(x = 1; x N) showAnswer();)else for(j = l;j=N;j-H-) iftcolumnj = 1 &rupi+j = 1 & lupi-j+N = 1) queeni =j;/Z设定为占用columnj = rup=lupi-j+N = 0;backtrack(i-l-l);column|j = rup =lupiJ+N = 1;)9 .Algorithm Gossip:枚银币说明现有八枚银币abcdefgh

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

31、 void comparc(int, int, int, int);void eightcoins(int);int main(void) int coins8 = ;inti;srand(time(NULL);fdr(i = 0； i 8; i-H-)coinsi = 10;printf(n输入假币重量(比10大或小)：*1);scanfiC%d &i);coinsrand() % 8 = i;eightcoins(coins);printf(nn列出所有钱币重量:;fbr(i = 0; i coinsk)printf(n假币 %d 较重”,i+1);elseprintf(n假币 %d 较轻

32、”,j+1);void eightcoins(int coins) ifi(coins0+coins 1 +coins2=coins3+coins4+coins5) if(coins6 coins7)comparc(coins, 6, 7, 0);elsecompare(coins, 7, 6, 0);else if(coins0+coins 1 +coins2 coins3+coins4+coins5) if(coins0+coins3 = coinsl+coins4)compare(coins, 2, 5, 0);else if(coins0+coins3 coinsl+coins4) c

33、ompare(coins, 0, 4, 1);if(coins0+coins3 coinsl+coins4)comparc(coins, 1, 3, 0);else if(coins0+coins 1 +coins2 coinsl+coins4) compare(coins, 3, 1, 0);if(coins0+coins3 coins l+coins4)compare(coins, 4, 0, 1);10 .Algorithm Gossip:生命游戏说明生命游戏(game of life)为1970年由英国数学家J. H. Conway所提出,某细胞的邻居包括上、下、左、右、左上、左下、右

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

35、 MAXCOL25#define DEAD 0/define ALIVE 1int m叩MAXROWMAXCOL, newmapMAXROWMAXCOL;void init();int neighbors(int, int);void outputMap();void copyMap();int main() int row, col;char ans;init();while(l) outputMap();fbr(row = 0; row MAXROW; row+) fbr(col = 0; col MAXCOL; col卄)switch (neighbors(row, col) case

36、0:case 1:case 4:case 5:case 6:case 7:case 8:newmaprowcol = DEAD;break;case 2:newmaprowcol = maprowcol;break;case 3:newirmprowcol = ALIVE;break;)IcopyMapO;printfl(MnContinue next Generation ? M);getchar();ans = toupper(getchar();ififans != Y) break;)return 0;void init() int row, col;fbr(row = 0; row

37、MAXROW; row-H-)fbr(col = 0; col MAXCOL; col) maprowcol = DEAD;puts(nGame of life Program*);puts(*Enter x, y where x, y is living cell*); print*0 = x = %d, 0 = y = %dn*, MAXROW-1, MAXCOL-1);puts(*Terminate with x, y = -1, -1*);while(l) scanfi(*%d %d*, &row, &col);if(0 = row & row MAXROW &0 = col & co

38、l MAXCOL) maprowcol = ALIVE;else if(row = -1 | col = -1) break;elseprintfl(*(x, y) exceeds map ranagc!*);int neighbors(int row, int col) int count = 0, c, r;fbr(r = row-1; r = row+1; rH-)fbr(c = col-1; c = col+1; c+) if(r = MAXROW | c = MAXCOL) continue;ifl(maprc = ALIVE) count-H-；if(maprowcol = ALI

39、VE)count-;return count;void outputMap() int row, col;printf(nnn%20cGame of life cell statusnM);fbr(row = 0; row MAXROW; row+) printf(Mn%20cn,1);fbr(col = 0; col MAXCOL; col-H-)if(maprowcol = ALIVE)putchar(即)；else putcharf)； void copyMapO int row, col;fbr(row = 0; row MAXROW; row-H-)fbr(col = 0; col

40、MAXCOL; col+) maprowcol = newmaprowcol;)11 .Algorithm Gossip:字串核对说明今日的一些高阶程式语言对于字串的处理支援越来越强大(例如Java、Perl等),不过字串搜寻本身仍是个值得探讨的课题,在这边以Boyer- Moore法来说明如何进行字串说明,这个 方法快旦原理简洁易懂。解法字串搜寻本身不难,使用暴力法也可以求解,但如何快速搜寻字串就不简单了,传统的 字串搜是从关键字与字串的开头开始比对,例如Knuth-Morris-Pratt演算法字串搜寻,这个 方法也不错,不过耍花时间在公式计算上;Boyer-Moore字串核对改由关键字的

41、后面开始核对字 串,并制作前进表,如果比对不符合则依前进表中的值前进至下个核对处,假设是p好了,然 后比对字串中pn+l至p的值是否与关键字相同。如果关键字中有重复出现的字元,则前进值就会有两个以上的值,此时则取前进值较小的值, 如此就不会跳过可能的位置,例如texture这个关键字,t的前进值应该取后面的3而不是取前面的#include #include #include void table(char*); /Z 建立前进表int search(int, char*, char*); /Z 搜寻关键字void substring(char*, char*, int, int); /Z 取出子字串int skip256;int main(void) char str_input80;char str_key80;chartmp80 = ;int m, n, p;printf(请输入字串:)；gets(strinput);printf(”请输入搜寻关键字:);