C语言超经典算法大全.pdf

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

1、.C C 语言经典算法大全语言经典算法大全老掉牙老掉牙河塔河塔费式数列费式数列巴斯卡三角形巴斯卡三角形三色棋三色棋老鼠走迷官（一）老鼠走迷官（一）老鼠走迷官（二）老鼠走迷官（二）骑士走棋盘骑士走棋盘八个皇后八个皇后八枚银币八枚银币生命游戏生命游戏字串核对字串核对双色、三色河塔双色、三色河塔背包问题（背包问题（Knapsack ProblemKnapsack Problem）数、运算数、运算蒙地卡罗法求蒙地卡罗法求 PI PIEratosthenesEratosthenes筛选求质数筛选求质数超长整数运算（大数运算）超长整数运算（大数运算）长长 PI PI最大公因数、最小公倍数、因式分解最大公因

2、数、最小公倍数、因式分解完美数完美数阿姆斯壮数阿姆斯壮数最大访客数最大访客数中序式转后序式（前序式）中序式转后序式（前序式）后序式的运算后序式的运算关于赌博关于赌博洗扑克牌（乱数排列）洗扑克牌（乱数排列）CrapsCraps赌博游戏赌博游戏约瑟夫问题（约瑟夫问题（Josephus ProblemJosephus Problem）集合问题集合问题排列组合排列组合格雷码（格雷码（Gray CodeGray Code）产生可能的集合产生可能的集合1/135.m m元素集合的元素集合的n n个元素子集个元素子集数字拆解数字拆解排序排序得分排行得分排行选择、插入、气泡排序选择、插入、气泡排序ShellS

3、hell 排序法排序法-改良的插入排序改良的插入排序ShakerShaker 排序法排序法-改良的气泡排序改良的气泡排序HeapHeap 排序法排序法-改良的选择排序改良的选择排序快速排序法（一）快速排序法（一）快速排序法（二）快速排序法（二）快速排序法（三）快速排序法（三）合并排序法合并排序法基数排序法基数排序法搜寻搜寻循序搜寻法（使用卫兵）循序搜寻法（使用卫兵）二分搜寻法（搜寻原则的代表）二分搜寻法（搜寻原则的代表）插补搜寻法插补搜寻法费氏搜寻法费氏搜寻法矩阵矩阵稀疏矩阵稀疏矩阵多维矩阵转一维矩阵多维矩阵转一维矩阵上三角、下三角、对称矩阵上三角、下三角、对称矩阵奇数魔方阵奇数魔方阵4N4N

4、 魔方阵魔方阵2(2N+1)2(2N+1)魔方阵魔方阵2/135.1.1.河之塔河之塔说明说明河之塔河之塔(Towers(Towers ofof Hanoi)Hanoi)是法国人是法国人M.Claus(Lucas)M.Claus(Lucas)于于18831883年从泰国带至法国的，河为越年从泰国带至法国的，河为越战时北越的首都，即现在的胡志明市；战时北越的首都，即现在的胡志明市；18831883年法国数学家年法国数学家 Edouard Lucas Edouard Lucas曾提与这个故事，据曾提与这个故事，据说创世纪时说创世纪时BenaresBenares有一座波罗教塔，是由三支钻石棒（有一座

5、波罗教塔，是由三支钻石棒（PagPag）所支撑，开始时神在第一根棒上）所支撑，开始时神在第一根棒上放置放置6464个由上至下依由小至大排列的金盘（个由上至下依由小至大排列的金盘（DiscDisc），并命令僧侣将所有的金盘从第一根石棒移，并命令僧侣将所有的金盘从第一根石棒移至第三根石棒，且搬运过程中遵守大盘子在小盘子之下的原则，若每日仅搬一个盘子，则当盘至第三根石棒，且搬运过程中遵守大盘子在小盘子之下的原则，若每日仅搬一个盘子，则当盘子全数搬运完毕之时，此塔将毁损，而也就是世界末日来临之时。子全数搬运完毕之时，此塔将毁损，而也就是世界末日来临之时。解法解法如果柱子标为如果柱子标为ABCABC，要

6、由，要由A A搬至搬至C C，在只有一个盘子时，就将它直接搬至，在只有一个盘子时，就将它直接搬至C C，当有两个盘子，当有两个盘子，就将就将B B当作辅助柱。如果盘数超过当作辅助柱。如果盘数超过2 2个，将第三个以下的盘子遮起来，就很简单了，每次处理两个，将第三个以下的盘子遮起来，就很简单了，每次处理两个盘子，也就是：个盘子，也就是：A-BA-B、A-CA-C、B-CB-C这三个步骤，而被遮住的部份，其实就是进入程式的递这三个步骤，而被遮住的部份，其实就是进入程式的递回处理。事实上，若有回处理。事实上，若有n n个盘子，则移动完毕所需之次数为个盘子，则移动完毕所需之次数为2n-12n-1，所以

7、当盘数为，所以当盘数为6464时，则所时，则所需次数为：需次数为：2 2-1=615-1=615为为5.782e+165.782e+16年，也就是约年，也就是约50005000世纪，如果对这数字没什幺概念，就假世纪，如果对这数字没什幺概念，就假设每秒钟搬一个盘子好了，也要约设每秒钟搬一个盘子好了，也要约58505850亿年左右。亿年左右。#include#include void hanoi(int n,char A,char B,char C)void hanoi(int n,char A,char B,char C)if(n=1)if(n=1)printf(Move sheet%d fro

8、m%c to%cn,n,A,C);printf(Move sheet%d from%c to%cn,n,A,C);else else hanoi(n-1,A,C,B);hanoi(n-1,A,C,B);printf(Move sheet%d from%c to%cn,n,A,C);printf(Move sheet%d from%c to%cn,n,A,C);hanoi(n-1,B,A,C);hanoi(n-1,B,A,C);int main()int main()int n;int n;printf(printf(请输入盘数：请输入盘数：););scanf(%d,&n);scanf(%d,&

9、n);hanoi(n,A,B,C);hanoi(n,A,B,C);return 0;return 0;64643/135.2.Algorithm Gossip:2.Algorithm Gossip:费式数列费式数列说明说明FibonacciFibonacci为为12001200年代的欧洲数学家，在他的着作中曾经提到：年代的欧洲数学家，在他的着作中曾经提到：若有一只免子每个月生一只小若有一只免子每个月生一只小免子，一个月后小免子也开始生产。起初只有一只免子，一个月后就有两只免子，二个月后有免子，一个月后小免子也开始生产。起初只有一只免子，一个月后就有两只免子，二个月后有三只免子，三个月后有五只免

10、子（小免子投入生产）三只免子，三个月后有五只免子（小免子投入生产）.。如果不太理解这个例子的话，举个图就知道了，注意新生的小免子需一个月成长期才会投入生如果不太理解这个例子的话，举个图就知道了，注意新生的小免子需一个月成长期才会投入生产，类似的道理也可以用于植物的生长，这就是产，类似的道理也可以用于植物的生长，这就是 FibonacciFibonacci数列，一般习惯称之为费氏数列，数列，一般习惯称之为费氏数列，例如以下：例如以下：1 1、1 1、2 2、3 3、5 5、8 8、1313、2121、3434、5555、89.89.解法解法依说明，我们可以将费氏数列定义为以下：依说明，我们可以将

11、费氏数列定义为以下：fn=fn-1+fn-2 if n 1fn=fn-1+fn-2 if n 1fn=n if n=0,1fn=n if n=0,1#include#include#include#include#define N 20#define N 20int main(void)int main(void)int FibN=0;int FibN=0;int i;int i;Fib0=0;Fib0=0;Fib1=1;Fib1=1;for(i=2;i N;i+)for(i=2;i N;i+)Fibi=Fibi-1+Fibi-2;Fibi=Fibi-1+Fibi-2;for(i=0;i N;

12、i+)for(i=0;i N;i+)printf(%d,Fibi);printf(%d,Fibi);printf(n);printf(n);return 0;return 0;4/135.3.3.巴斯卡三角形巴斯卡三角形#include#include#define N 12#define N 12long combi(int n,int r)long combi(int n,int r)int i;int i;long p=1;long p=1;for(i=1;i=r;i+)for(i=1;i=r;i+)p=p*(n-i+1)/i;p=p*(n-i+1)/i;return p;return

13、p;void paint()void paint()int n,r,t;int n,r,t;for(n=0;n=N;n+)for(n=0;n=N;n+)for(r=0;r=n;r+)for(r=0;r=n;r+)int i;/*int i;/*排版设定开始排版设定开始*/*/if(r=0)if(r=0)for(i=0;i=(N-n);i+)for(i=0;i=(N-n);i+)printf();printf();else else printf();printf();/*/*排版设定完毕排版设定完毕*/*/printf(%3d,combi(n,r);printf(%3d,combi(n,r);

14、printf(n);printf(n);5/135.4.Algorithm Gossip:4.Algorithm Gossip:三色棋三色棋说明说明三色旗的问题最早由三色旗的问题最早由E.W.DijkstraE.W.Dijkstra所提出，他所使用的用语为所提出，他所使用的用语为Dutch Nation Flag(DijkstraDutch Nation Flag(Dijkstra为为荷兰人荷兰人)，而多数的作者则使用，而多数的作者则使用Three-Color FlagThree-Color Flag来称之。来称之。假设有一条绳子，上面有红、白、蓝三种颜色的旗子，起初绳子上的旗子颜色并没有顺序

15、，您假设有一条绳子，上面有红、白、蓝三种颜色的旗子，起初绳子上的旗子颜色并没有顺序，您希望将之分类，并排列为蓝、白、红的顺序，要如何移动次数才会最少，注意您只能在绳子上希望将之分类，并排列为蓝、白、红的顺序，要如何移动次数才会最少，注意您只能在绳子上进行这个动作，而且一次只能调换两个旗子。进行这个动作，而且一次只能调换两个旗子。解法解法在一条绳子上移动，在程式中也就意味只能使用一个阵列，而不使用其它的阵列来作辅助，问在一条绳子上移动，在程式中也就意味只能使用一个阵列，而不使用其它的阵列来作辅助，问题的解法很简单，您可以自己想像一下在移动旗子，从绳子开头进行，遇到蓝色往前移，遇到题的解法很简单，

16、您可以自己想像一下在移动旗子，从绳子开头进行，遇到蓝色往前移，遇到白色留在中间，遇到红色往后移，如下所示：白色留在中间，遇到红色往后移，如下所示：只是要让移动次数最少的话，就要有些技巧：只是要让移动次数最少的话，就要有些技巧：如果图中如果图中W W所在的位置为白色，则所在的位置为白色，则W+1W+1，表示未处理的部份移至至白色群组。，表示未处理的部份移至至白色群组。如果如果W W部份为蓝色，则部份为蓝色，则B B与与W W的元素对调，而的元素对调，而B B与与W W必须各必须各+1+1，表示两个群组都多了一个元素。，表示两个群组都多了一个元素。如果如果W W所在的位置是红色，则将所在的位置是红

17、色，则将W W与与R R交换，但交换，但R R要减要减1 1，表示未处理的部份减，表示未处理的部份减1 1。注意注意B B、W W、R R并不是三色旗的个数，它们只是一个移动的指标；什幺时候移动完毕呢？一开始并不是三色旗的个数，它们只是一个移动的指标；什幺时候移动完毕呢？一开始时未处理的时未处理的R R指标会是等于旗子的总数，当指标会是等于旗子的总数，当R R的索引数减至少于的索引数减至少于W W的索引数时，表示接下来的旗的索引数时，表示接下来的旗子就都是红色了，此时就可以完毕移动，如下所示：子就都是红色了，此时就可以完毕移动，如下所示：#include#include#include#inc

18、lude#include#include#define BLUE b#define BLUE b#define WHITE w#define WHITE w#define RED r#define RED r#define SWAP(x,y)char temp;#define SWAP(x,y)char temp;temp=colorx;temp=colorx;colorx=colory;colorx=colory;colory=temp;colory=temp;int main()int main()char color=r,w,b,w,w,char color=r,w,b,w,w,6/13

19、5.b,r,b,w,r,0;b,r,b,w,r,0;int wFlag=0;int wFlag=0;int bFlag=0;int bFlag=0;int rFlag=strlen(color)-1;int rFlag=strlen(color)-1;int i;int i;for(i=0;i strlen(color);i+)for(i=0;i strlen(color);i+)printf(%c,colori);printf(%c,colori);printf(n);printf(n);while(wFlag=rFlag)while(wFlag=rFlag)if(colorwFlag=WH

20、ITE)if(colorwFlag=WHITE)wFlag+;wFlag+;else if(colorwFlag=BLUE)else if(colorwFlag=BLUE)SWAP(bFlag,wFlag);SWAP(bFlag,wFlag);bFlag+;wFlag+;bFlag+;wFlag+;else else while(wFlag rFlag&colorrFlag=RED)while(wFlag rFlag&colorrFlag=RED)rFlag-;rFlag-;SWAP(rFlag,wFlag);SWAP(rFlag,wFlag);rFlag-;rFlag-;for(i=0;i

21、strlen(color);i+)for(i=0;i strlen(color);i+)printf(%c,colori);printf(%c,colori);printf(n);printf(n);return 0;return 0;7/135.5.Algorithm Gossip:5.Algorithm Gossip:老鼠走迷官（一）老鼠走迷官（一）说明说明老鼠走迷宫是递回求解的基此题型，我们在二维阵列中使用老鼠走迷宫是递回求解的基此题型，我们在二维阵列中使用2 2表示迷宫墙壁，使用表示迷宫墙壁，使用1 1来表来表示老鼠的行走路径，试以程式求出由入口至出口的路径。示老鼠的行走路径，试以程式

22、求出由入口至出口的路径。解法解法老鼠的走法有上、左、下、右四个方向，在每前进一格之后就选一个方向前进，无法前老鼠的走法有上、左、下、右四个方向，在每前进一格之后就选一个方向前进，无法前进时退回选择下一个可前进方向，如此在阵列中依序测试四个方向，直到走到出口为止，这是进时退回选择下一个可前进方向，如此在阵列中依序测试四个方向，直到走到出口为止，这是递回的基此题，请直接看程式应就可以理解。递回的基此题，请直接看程式应就可以理解。#include#include#include#include int visit(int,int);int visit(int,int);int maze77=2,2,

23、2,2,2,2,2,int maze77=2,2,2,2,2,2,2,2,0,0,0,0,0,2,2,0,0,0,0,0,2,2,0,2,0,2,0,2,2,0,2,0,2,0,2,2,0,0,2,0,2,2,2,0,0,2,0,2,2,2,2,0,2,0,2,2,2,2,0,2,0,2,2,2,0,0,0,0,0,2,2,0,0,0,0,0,2,2,2,2,2,2,2,2;2,2,2,2,2,2,2;int startI=1,startJ=1;/int startI=1,startJ=1;/入口入口int endI=5,endJ=5;/int endI=5,endJ=5;/出口出口int s

24、uccess=0;int success=0;int main(void)int main(void)int i,j;int i,j;printf(printf(显示迷宫：显示迷宫：n);n);for(i=0;i 7;i+)for(i=0;i 7;i+)for(j=0;j 7;j+)for(j=0;j 7;j+)if(mazeij=2)if(mazeij=2)printf();printf();elseelse printf();printf();printf(n);printf(n);if(visit(startI,startJ)=0)if(visit(startI,startJ)=0)pr

25、intf(n printf(n没有找到出口！没有找到出口！n);n);8/135.else else printf(n printf(n显示路径：显示路径：n);n);for(i=0;i 7;i+)for(i=0;i 7;i+)for(j=0;j 7;j+)for(j=0;j 7;j+)if(mazeij=2)if(mazeij=2)printf();printf();else if(mazeij=1)else if(mazeij=1)printf();printf();else else printf();printf();printf(n);printf(n);return 0;retur

26、n 0;int visit(int i,int j)int visit(int i,int j)mazeij=1;mazeij=1;if(i=endI&j=endJ)if(i=endI&j=endJ)success=1;success=1;if(success!=1&mazeij+1=0)visit(i,j+1);if(success!=1&mazeij+1=0)visit(i,j+1);if(success!=1&mazei+1j=0)visit(i+1,j);if(success!=1&mazei+1j=0)visit(i+1,j);if(success!=1&mazeij-1=0)vis

27、it(i,j-1);if(success!=1&mazeij-1=0)visit(i,j-1);if(success!=1&mazei-1j=0)visit(i-1,j);if(success!=1&mazei-1j=0)visit(i-1,j);if(success!=1)if(success!=1)mazeij=0;mazeij=0;return success;return success;9/135.6.Algorithm Gossip:6.Algorithm Gossip:老鼠走迷官（二）老鼠走迷官（二）说明说明由于迷宫的设计，老鼠走迷宫的入口至出口路径可能不只一条，如何求出所有的路

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

29、aze99=2,2,2,2,2,2,2,2,2,int maze99=2,2,2,2,2,2,2,2,2,2,0,0,0,0,0,0,0,2,2,0,0,0,0,0,0,0,2,2,0,2,2,0,2,2,0,2,2,0,2,2,0,2,2,0,2,2,0,2,0,0,2,0,0,2,2,0,2,0,0,2,0,0,2,2,0,2,0,2,0,2,0,2,2,0,2,0,2,0,2,0,2,2,0,0,0,0,0,2,0,2,2,0,0,0,0,0,2,0,2,2,2,0,2,2,0,2,2,2,2,2,0,2,2,0,2,2,2,2,0,0,0,0,0,0,0,2,2,0,0,0,0,0,0

30、,0,2,2,2,2,2,2,2,2,2,2;2,2,2,2,2,2,2,2,2;int startI=1,startJ=1;/int startI=1,startJ=1;/入口入口int endI=7,endJ=7;/int endI=7,endJ=7;/出口出口int main(void)int main(void)int i,j;int i,j;printf(printf(显示迷宫：显示迷宫：n);n);for(i=0;i 7;i+)for(i=0;i 7;i+)for(j=0;j 7;j+)for(j=0;j 7;j+)if(mazeij=2)if(mazeij=2)printf();

31、printf();else else printf();printf();printf(n);printf(n);visit(startI,startJ);visit(startI,startJ);10/135.return 0;return 0;void visit(int i,int j)void visit(int i,int j)int m,n;int m,n;mazeij=1;mazeij=1;if(i=endI&j=endJ)if(i=endI&j=endJ)printf(n printf(n显示路径：显示路径：n);n);for(m=0;m 9;m+)for(m=0;m 9;m+

32、)for(n=0;n 9;n+)for(n=0;n 9;n+)if(mazemn=2)if(mazemn=2)pri printf();ntf();else if(mazemn=1)else if(mazemn=1)printf();printf();else else printf();printf();printf(n);printf(n);if(mazeij+1=0)visit(i,j+1);if(mazeij+1=0)visit(i,j+1);if(mazei+1j=0)visit(i+1,j);if(mazei+1j=0)visit(i+1,j);if(mazeij-1=0)visi

33、t(i,j-1);if(mazeij-1=0)visit(i,j-1);if(mazei-1j=0)visit(i-1,j);if(mazei-1j=0)visit(i-1,j);mazeij=0;mazeij=0;11/135.7.Algorithm Gossip:7.Algorithm Gossip:骑士走棋盘骑士走棋盘说明说明骑士旅游（骑士旅游（Knight tourKnight tour）在十八世纪初倍受数学家与拼图迷的注意，它什么时候被提）在十八世纪初倍受数学家与拼图迷的注意，它什么时候被提出已不可考，骑士的走法为西洋棋的走法，骑士可以由任一个位置出发，它要如何走完出已不可考，骑士的

34、走法为西洋棋的走法，骑士可以由任一个位置出发，它要如何走完 所有所有的位置？的位置？解法解法骑士的走法，基本上可以使用递回来解决，但是纯綷的递回在维度大时相当没有效率，骑士的走法，基本上可以使用递回来解决，但是纯綷的递回在维度大时相当没有效率，一个聪明的解法由一个聪明的解法由J.C.WarnsdorffJ.C.Warnsdorff在在18231823年提出，简单的说，先将最难的位置走完，接下来年提出，简单的说，先将最难的位置走完，接下来的路就宽广了，骑士所要走的下一步，的路就宽广了，骑士所要走的下一步，为下一步再选择时，所能走的步数最少的一步。为下一步再选择时，所能走的步数最少的一步。，使，使

35、用这个方法，在不使用递回的情况下，可以有较高的机率找出走法（找不到走法的机会也是有用这个方法，在不使用递回的情况下，可以有较高的机率找出走法（找不到走法的机会也是有的）的）。#include#include int board88=0;int board88=0;int main(void)int main(void)int startx,starty;int startx,starty;int i,j;int i,j;printf(printf(输入起始点：输入起始点：););scanf(%d%d,&startx,&starty);scanf(%d%d,&startx,&starty);if

36、(travel(startx,starty)if(travel(startx,starty)printf(printf(游历完成！游历完成！n);n);else else printf(printf(游历失败！游历失败！n);n);for(i=0;i 8;i+)for(i=0;i 8;i+)for(j=0;j 8;j+)for(j=0;j 8;j+)printf(%2d,boardij);printf(%2d,boardij);putchar(n);putchar(n);return 0;return 0;int travel(int x,int y)int travel(int x,int

37、y)/对应骑士可走的八个方向对应骑士可走的八个方向 int ktmove18=-2,-1,1,2,2,1,-1,-2;int ktmove18=-2,-1,1,2,2,1,-1,-2;12/135.int ktmove28=1,2,2,1,-1,-2,-2,-1;int ktmove28=1,2,2,1,-1,-2,-2,-1;/测试下一步的出路测试下一步的出路 int nexti8=0;int nexti8=0;int nextj8=0;int nextj8=0;/记录出路的个数记录出路的个数 int exists8=0;int exists8=0;int i,j,k,m,l;int i,j

38、,k,m,l;int tmpi,tmpj;int tmpi,tmpj;int count,min,tmp;int count,min,tmp;i=x;i=x;j=y;j=y;boardij=1;boardij=1;for(m=2;m=64;m+)for(m=2;m=64;m+)for(l=0;l 8;l+)for(l=0;l 8;l+)existsl=0;existsl=0;l=0;l=0;/试探八个方向试探八个方向 for(k=0;k 8;k+)for(k=0;k 8;k+)tmpi=i+ktmove1k;tmpi=i+ktmove1k;tmpj=j+ktmove2k;tmpj=j+ktmo

39、ve2k;/如果是边界了，不可走如果是边界了，不可走 if(tmpi 0|tmpj 7|tmpj 7)if(tmpi 0|tmpj 7|tmpj 7)continue;continue;/如果这个方向可走，记录下来如果这个方向可走，记录下来 if(boardtmpitmpj=0)if(boardtmpitmpj=0)nextil=tmpi;nextil=tmpi;nextjl=tmpj;nextjl=tmpj;/可走的方向加一个可走的方向加一个 l+;l+;count=l;count=l;/如果可走的方向为如果可走的方向为0 0个，返回个，返回13/135.if(count=0)if(coun

40、t=0)return 0;return 0;else if(count=1)else if(count=1)/只有一个可走的方向只有一个可走的方向 /所以直接是最少出路的方向所以直接是最少出路的方向 min=0;min=0;else else /找出下一个位置的出路数找出下一个位置的出路数 for(l=0;l count;l+)for(l=0;l count;l+)for(k=0;k 8;k+)for(k=0;k 8;k+)tmpi=nextil+ktmove1k;tmpi=nextil+ktmove1k;tmpj=nextjl+ktmove2k;tmpj=nextjl+ktmove2k;if

41、(tmpi 0|tmpj 0|if(tmpi 0|tmpj 7|tmpj 7)tmpi 7|tmpj 7)continue;continue;if(boardtmpitmpj=0)if(boardtmpitmpj=0)existsl+;existsl+;tmp=exists0;tmp=exists0;min=0;min=0;/从可走的方向中寻找最少出路的方向从可走的方向中寻找最少出路的方向for(l=1;l count;l+)for(l=1;l count;l+)if(existsl tmp)if(existsl tmp)tmp=existsl;tmp=existsl;min=l;min=l;

42、/走最少出路的方向走最少出路的方向 i=nextimin;i=nextimin;j=nextjmin;j=nextjmin;boardij=m;boardij=m;return 1;return 1;14/135.15/135.8.Algorithm Gossip:8.Algorithm Gossip:八皇后八皇后说明说明西洋棋中的皇后可以直线前进，吃掉遇到的所有棋子，如果棋盘上有八个皇后，则这八西洋棋中的皇后可以直线前进，吃掉遇到的所有棋子，如果棋盘上有八个皇后，则这八个皇后如何相安无事的放置在棋盘上，个皇后如何相安无事的放置在棋盘上，19701970年与年与19711971年，年，E.W.

43、Dijkstra E.W.Dijkstra与与N.WirthN.Wirth曾经用这个曾经用这个问题来讲解程式设计之技巧。问题来讲解程式设计之技巧。解法解法关于棋盘的问题，关于棋盘的问题，都可以用递回求解，都可以用递回求解，然而如何减少递回的次数？在八个皇后的问题中，然而如何减少递回的次数？在八个皇后的问题中，不必要所有的格子都检查过，例如若某列检查过，该该列的其它格子就不用再检查了，这个方不必要所有的格子都检查过，例如若某列检查过，该该列的其它格子就不用再检查了，这个方法称为分支修剪。法称为分支修剪。#include#include#include#include#define N 8#def

44、ine N 8int columnN+1;/int columnN+1;/同栏是否有皇后，同栏是否有皇后，1 1表示有表示有int rup2*N+1;/int rup2*N+1;/右上至左下是否有皇后右上至左下是否有皇后int lup2*N+1;/int lup2*N+1;/左上至右下是否有皇后左上至右下是否有皇后int queenN+1=0;int queenN+1=0;int num;/int num;/解答编号解答编号void backtrack(int);/void backtrack(int);/递回求解递回求解int main(void)int main(void)int i;in

45、t i;num=0;num=0;for(i=1;i=N;i+)for(i=1;i=N;i+)columni=1;columni=1;for(i=1;i=2*N;i+)for(i=1;i=2*N;i+)rupi=lupi=1;rupi=lupi=1;backtrack(1);backtrack(1);return 0;return 0;void showAnswer()void showAnswer()int x,y;int x,y;16/135.printf(nprintf(n解答解答%dn,+num);%dn,+num);for(y=1;y=N;y+)for(y=1;y=N;y+)for(x

46、=1;x=N;x+)for(x=1;x N)if(i N)showAnswer();showAnswer();else else for(j=1;j=N;j+)for(j=1;j=N;j+)if(columnj=1&if(columnj=1&rupi+j=1&lupi-j+N=1)rupi+j=1&lupi-j+N=1)queeni=j;queeni=j;/设定为占用设定为占用 columnj=rupi+j=lupi-j+N=0;columnj=rupi+j=lupi-j+N=0;backtrack(i+1);backtrack(i+1);columnj=rupi+j=lupi-j+N=1;c

47、olumnj=rupi+j=lupi-j+N=1;17/135.9.Algorithm Gossip:9.Algorithm Gossip:八枚银币八枚银币说明说明现有八枚银币现有八枚银币a b c d e f g ha b c d e f g h，已知其中一枚是假币，其重量不同于真币，但不知是，已知其中一枚是假币，其重量不同于真币，但不知是较轻或较重，如何使用天平以最少的比较次数，决定出哪枚是假币，并得知假币比真币较轻或较轻或较重，如何使用天平以最少的比较次数，决定出哪枚是假币，并得知假币比真币较轻或较重。较重。解法解法单就求假币的问题是不难，但问题限制使用最少的比较次数，所以我们不能以单纯

48、的回单就求假币的问题是不难，但问题限制使用最少的比较次数，所以我们不能以单纯的回圈比较来求解，我们可以使用决策树（圈比较来求解，我们可以使用决策树（decision treedecision tree），使用分析与树状图来协助求解。一个，使用分析与树状图来协助求解。一个简单的状况是这样的，我们比较简单的状况是这样的，我们比较a+b+ca+b+c与与d+e+fd+e+f，如果相等，则假币必是，如果相等，则假币必是g g或或h h，我们先比较，我们先比较g g或或h h哪个较重，如果哪个较重，如果g g较重，再与较重，再与a a比较（比较（a a是真币）是真币），如果，如果g g等于等于a a，则

49、，则g g为真币，则为真币，则h h为假币，由于为假币，由于h h比比g g轻而轻而 g g是真币，则是真币，则h h假币的重量比真币轻。假币的重量比真币轻。#include#include#include#include#include#include void compare(int,int,int,int);void compare(int,int,int,int);void eightcoins(int);void eightcoins(int);int main(void)int main(void)int coins8=0;int coins8=0;int i;int i;sran

50、d(time(NULL);srand(time(NULL);for(i=0;i 8;i+)for(i=0;i 8;i+)coinsi=10;coinsi=10;printf(n printf(n输入假币重量输入假币重量(比比1010大或小大或小)：););scanf(%d,&i);scanf(%d,&i);coinsrand()%8=i;coinsrand()%8=i;eightcoins(coins);eightcoins(coins);printf(nn printf(nn列出所有钱币重量：列出所有钱币重量：););for(i=0;i 8;i+)for(i=0;i coinsk)if(co