计算机编程常用算法.pdf

《计算机编程常用算法.pdf》由会员分享，可在线阅读，更多相关《计算机编程常用算法.pdf（55页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、常用算法要使计算机能完成人们预定的工作，首先必须为如何完成预定的工作设计一个算法，然后再根据算法编写程序。计算机程序要对问题的每个对象和处理规则给出正确详尽的描述，其中程序的数据结构和变量用来描述问题的对象，程序结构、函数和语句用来描述问题的算法。算法数据结构是程序的两个重要方面。算法是问题求解过程的精确描述，一个算法由有限条可完全机械地执行的、有确定结果的指令组成。指令正确地描述了要完成的任务和它们被执行的顺序。计算机按算法指令所描述的顺序执行算法的指令能在有限的步骤内终止，或终止于给出问题的解，或终止于指出问题对此输入数据无解。通常求解个问题可能会有多种算法可供选择，选择的主要标准是算法的

2、正确性和可靠性，简单性利易理解性。其次是算法所需要的存储空间少和执行更快等。算法设计是一件非常困难的工作，经常采用的算法设计技术主要有迭代法、穷举搜索法、递推法、贪婪法、回溯法、分治法、动态规划法等等。另外，为了更简洁的形式设计和藐视算法，在算法设计时又常常采用递归技术，用递归描述算法。一、迭代法迭代法是用于求方程或方程组近似根的一种常用的算法设计方法。设方程为f(x尸0,用某种数学方法导出等价的形式x=g(x),然后按以下步骤执行：(1)选一个方程的近似根，赋给变量xO；(2)将 x0的值保存于变量x l,然后计算g(x l),并将结果存于变量xO；(3)当 xO与 x l 的差的绝对值还小

3、于指定的精度要求时，重复步骤(2)的计算。若方程有根，并且用上述方法计算出来的近似根序列收敛，则按上述方法求得的xO就认为是方程的根。上述算法用C 程序的形式表示为：【算法】迭代法求方程的根 x0=初始近似根；do xl=x0；xO=g(xl)；/*按特定的方程计算新的近似根*/while(fabs(xO-x 1 )Epsilon)；printf(方 程的近似根是fn，xO)；迭代算法也常用于求方程组的根，令X=(xO,x l,，xn-1)设方程组为：xi=gi(X)(1=0,1,n-1)则求方程组根的迭代算法可描述如下：【算法】迭代法求方程组的根 for(i=0;in;i-H-)xi=初始近

4、似根；do for(i=0;in;i+)yi=xi；for(i=0;in;i+)xi=gi(X);for(delta=0.0,i=0;idelta)delta=fabs(yi-xi)；while(deltaEpsilon)；for(i=0;in;i+)printf(“变量 x%d的近似根是 f，I,xi)；printf(“n”)；具体使用迭代法求根时应注意以下两种可能发生的情况：(1)如果方程无解，算法求出的近似根序列就不会收敛，迭代过程会变成死循环，因此在使用迭代算法前应先考察方程是否有解，并在程序中对迭代的次数给予限制；(2)方程虽然有解，但迭代公式选择不当，或迭代的初始近似根选择不合理，

5、也会导致迭代失败。二、穷举搜索法穷举搜索法是对可能是解的众多候选解按某种顺序进行逐一枚举和检验，并从众找出那些符合要求的候选解作为问题的解。【问题】将A、B、C、D、E、F这六个变量排成如图所示的三角形，这六个变量分别取 1,6上的整数，且均不相同。求使三角形三条边上的变量之和相等的全部解。如图就是一个解。程序引入变量a、b、c、d、e、f,并让它们分别顺序取1至6的证书，在它们互不相同的条件下，测试山它们排成的如图所示的三角形三条边上的变量之和是否相等，如相等即为一种满足要求的排列，把它们输出。当这些变量取尽所有的组合后，程序就可得到全部可能的解。细节见下面的程序。【程 序1】#i n c

6、l u d e v o i d m a i n()i n t a,b,c,d,e,f;f o r (a=l;a =6;a-H-)f o r (b=1 ;b=6;b+)i f (b=a)c o n t i n u e;f o r (c=1 ;c =6;c-H-)i f (c=a)|(c=b)c o n t i n u e;f o r (d=1 ;d=6;d+)i f (d=a)1 1(d=b)11(d=c)c o n t i n u e;f o r (e=1 ;e =6;e-H-)i f (e=a)|(e=b)|(e=c)1 1(e=d)c o n t i n u e;f=2 1 -(a+b+c

7、+d+e);i f (a+b+c=c+d+e)&(a+b+c=e+任 a)p r i n t f(4 4%6d,a);p r i n t f(t 4%4 d%4 d,b,f)；p r i n t f C4%2 d%4 d%4 d,c,d,e);s c a n f T%*c);按穷举法编写的程序通常不能适应变化的情况。如问题改成有9 个变量排成三角形，每条边有4 个变量的情况，程序的循环重数就要相应改变。对一组数穷尽所有排列，还有更直接的方法。将一个排列看作一个长整数，则所有排列对应着一组整数。将这组整数按从小到大的顺序排列排成一个整数，从对应最小的整数开始。按数列的递增顺序逐一列举每个排列对应

8、的每个整数，这能更有效地完成排列的穷举。从一个排列找出对应数列的下一个排列可在当前排列的基础上作部分调整来实现。倘若当前排列为1,2,4,6,5,3,并令其对应的长整数为124653c要寻找比长整数124653更大的排列，可从该排列的最后一个数字顺序向前逐位考察，当发现排列中的某个数字比它前一个数字大时，如本例中的6 比它的前一位数字4 大，这说明还有对应更大整数的排列。但为了顺序从小到大列举出所有的排列，不能立即调整得太大，如本例中将数字6 与数字4 交换得到的排列126453就不是排列124653的下一个排列。为了得到排列124653的下一个排列，应从已经考察过的那部分数字中选出比数字大，

9、但又是它们中最小的那一个数字，比如数字5,与数字4 交换。该数字也是从后向前考察过程中第一个比4 大的数字。5 与 4 交换后，得到排列125643。在前面数字1,2,5 固定的情况下，还应选择对应最小整数的那个排列,为此还需将后面那部分数字的排列顺序颠倒，如将数字6,4,3 的排列顺序颠倒，得到排列1,2,5,3,4,6,这才是排列1,2,4,6,5,3 的下一个排列。按以上想法编写的程序如下。【程序2】#include#define SIDE_N 3#define LENGTH 3#define VARIABLES 6int A,B,C,D,E,F;int*pt=&A,&B,&C,&D,&

10、E,&F;int*sideSIDE_NLENGTH=&A,&B,&C,&C,&D,&E,&E,&F,&A;int side_totalSIDE_N;main int i,j,t,equal;for(j=O;jVARIABLES;j+)while(1)for(i=0;iSIDE_N;i4-+)for(t=j=O;jLENGTHg-H-)t+=*sideij;side_totali=t;for(equal=l,i=O;equal&iSIDE_N-l;i+)if(side_totali!=side_totali+l equal=0;if(equal)for(i=l;iO;j-)if(*ptj*ptj

11、-l)break;if(j=0)break;for(i=VARIABLES-l;i=j;i-)if(*pti*pti-l)break;t=*ptj-l;*ptj-l=*pti;*pti=t;fbr(i=VARIABLES-l;ij;i-j+)t=*ptj；*ptj=*pti;*pti=t;从上述问题解决的方法中，最重要的因素就是确定某种方法来确定所有的候选解。下面再用一个示例来加以说明。【问题】背包问题问题描述：有不同价值、不同重量的物品n 件，求从这n 件物品中选取一部分物品的选择方案，使选中物品的总重量不超过指定的限制重量，但选中物品的价值之和最大。设 n 个物品的重量和价值分别存储于数组

12、w 和 v 中，限制重量为tw o考虑一个n元 组(xO,x l,，x n-1),其中xi=0表示第i 个物品没有选取，而 xi=l则表示第i 个物品被选取。显然这个n 元组等价于一个选择方案。用枚举法解决背包问题，需要枚举所有的选取方案，而根据上述方法，我们只要枚举所有的n 元组，就可以得到问题的解。显然，每个分量取值为0 或 1 的 n 元组的个数共为2n个。而每个n 元组其实对应了个长度为n 的二进制数，且这些二进制数的取值范围为02n-l。因此，如果把02n-l分别转化为相应的二进制数，则可以得到我们所需要的2n 个 n 元组。【算法】maxv=0;for(i=0;i2n;i+)B0.

13、n-l=0;把 i 转化为二进制数，存储于数组B 中；temp_w=0;temp_v=0;for(j=O;jn;j+)if(Bj=l)temp_w=temp_w+wj;temp_v=temp_v+vj;)if(temp_wmaxv)maxv=temp_v;保存该B 数组；三、递推法递推法是利用问题本身所具有的一种递推关系求问题解的一种方法。设要求问题规模为 N 的解，当 N=1时，解或为已知，或能非常方便地得到解。能采用递推法构造算法的问题有重要的递推性质，即当得到问题规模为i-1的解后，由问题的递推性质，能从已求得的规 模 为 1,2,i-1 的一系列解，构造出问题规模为I 的解。这样，程序

14、可从i=0或 i=l出发，重复地，由已知至i-1规模的解，通过递推，获得规模为i 的解，直至得到规模为N的解。【问题】阶乘计算问题描述：编写程序，对给定的n(n=1 0 0),计算并输出k 的阶乘k!(k=l,2,，n)的全部有效数字。由于要求的整数可能大大超出一般整数的位数，程序用一维数组存储长整数，存储长整数数组的每个元素只存储长整数的一位数字。如有m 位成整数N 用数组a存储：N=am x 10m-1+am-1 x 10m-2+.+a2xl01+alxl00并用a0存储长整数N 的位数m,即 a0=m。按上述约定，数组的每个元素存储k 的阶乘k!的一位数字，并从低位到高位依次存于数组的第

15、二个元素、第三个元素。例如,5!=1 2 0,在数组中的存储形式为：3 0 2 1 .首元素3 表示长整数是一个3 位数，接着是低位到高位依次是0、2、1,表示成整数120o计算阶乘k!可采用对己求得的阶乘(k-1)!连续累加k-1次后求得。例 如,已 知 4!=24,计算5!,可对原来的24累加4 次 24后得到120。细节见以下程序。#include#include#define MAXN 1000void pnext(int a,int k)int*b,m=a0,i,j,r,carry;b=(int*)malloc(sizeof(int)*(m+1);for(i=l;i=m;i+)bi=

16、ai;fbr(j=l;j=k;j+)for(carry=O,i=1 ;i=m;i+)r=(i0;i-)printf(d”,ai);printf(nn)；void main()int aMAXN,n,k;printfifEnter the number n:);scanfT%d”,&n);a0=l;al=l；write(a,l);for(k=2;kl 时)。写成递归函数有：int fib(int n)if(n=0)return 0;if(n 1)return 1;if(nl)return fib(n-l)+fib(n-2);)递归算法的执行过程分递推和回归两个阶段。在递推阶段，把较复杂的问题(规

17、模为n)的求解推到比原问题简单一些的问题(规模小于n)的求解。例如上例中，求解fib(n),把它推到求解fib(n-l)和 fib(n-2)。也就是说，为计算fib(n),必须先计算fib(n-l)和 fib(n-2),而计算fib(n-l)和 fib(n-2),又必须先计算fib(n-3)和 fib(n4)。依次类推，直至计算flb(l)和fib(0),分别能立即得到结果1 和 0。在递推阶段，必须要有终止递归的情况。例如在函数fib中，当 n 为 1和。的情况。在回归阶段，当获得最简单情况的解后，逐级返回，依次得到稍复杂问题的解，例如得至I fib 和 fib(O)后，返回得到fib(2)

18、的结果,在得到了 fib(n-l)和 fib(n-2)的结果后,返回得到fib(n)的结果。在编写递归函数时要注意，函数中的局部变量和参数知识局限于当前调用层，当递推进入“简单问题”层时，原来层次上的参数和局部变量便被隐蔽起来。在一系列“简单问题”层，它们各有自己的参数和局部变量。由于递归引起系列的函数调用，并且可能会有一系列的重复计算，递归算法的执行效率相对较低。当某个递归算法能较方便地转换成递推算法时，通常按递推算法编写程序。例如上例计算斐波那契数列的第n 项的函数fib(n)应采用递推算法，即从斐波那契数列的前两项出发,逐次山前两项计算出下一项，直至计算出要求的第n 项。【问题】组合问题

19、问题描述:找出从自然数1、2、.、n 中任取r 个数的所有组合。例 如 n=5,r=3的所有组合为:(1)5、4、3(2)5、4、2(3)5、4、1(4)5、3、2(5)5、3、1(6)5、2、1(7)4、3、2(8)4、3、1(9)4、2、1(10)3、2、1分析所列的10个组合，可以采用这样的递归思想来考虑求组合函数的算法。设函数为void comb(int m,int k)为找出从自然数1、2、.、m 中任取k 个数的所有组合。当组合的第一个数字选定时，其后的数字是从余下的m-l个数中取k-1数的组合。这就将求m 个数中取k 个数的组合问题转化成求m-1个数中取k-l个数的组合问题。设函

20、数引入工作数组a 存放求HI的组合的数字，约定函数将确定的k 个数字组合的第一个数字放在ak中，当一个组合求出后，才将a中的一个组合输出。第一-个数可以是m、m-l.、k,函数将确定组合的第一个数字放入数组后，有两种可能的选择，因还未去顶组合的其余元素，继续递归去确定;或因已确定了组合的全部元素,输出这个组合。细节见以下程序中的函数comb。【程序】#include#define MAXN 100int aMAXN;void comb(int m,int k)int i,j;for(i=m;i=k;i-)ak=i;if(kl)comb(i-l,k-l);else for(j=aO;jO;j-)

21、printfC%4d,aj);printf(“n”)；)void main()a0=3;comb(5,3)；)【问题】背包问题问题描述：有不同价值、不同重量的物品n 件，求从这n 件物品中选取一部分物品的选择方案，使选中物品的总重量不超过指定的限制重量，但选中物品的价值之和最大。设 n 件物品的重量分别为wO、w l、w n-1,物品的价值分别为vO、v l、v n-L 采用递归寻找物品的选择方案。设前面已有了多种选择的方案，并保留了其中总价值最大的方案于数组option,该方案的总价值存于变量maxv。当前正在考察新方案，其物品选择情况保存于数组cop口。假定当前方案已考虑了前i-1件物品，

22、现在要考虑第i 件物品；当前方案已包含的物品的重量之和为tw；至此，若其余物品都选择是可能的话，本方案能达到的总价值的期望值为tv。算法引入tv 是当旦当前方案的总价值的期望值也小于前面方案的总价值maxv时，继续考察当前方案变成无意义的工作，应终止当前方案，立即去考察下一个方案。因为当方案的总价值不比maxv大时，该方案不会被再考察，这同时保证函数后找到的方案一定会比前面的方案更好。对于第i 件物品的选择考虑有两种可能：（1）考虑物品i 被选择，这种可能性仅当包含它不会超过方案总重量限制时才是可行的。选中后，继续递归去考虑其余物品的选择。（2）考虑物品i 不被选择，这种可能性仅当不包含物品i

23、 也有可能会找到价值更大的方案的情况。按以上思想写出递归算法如下：try（物品i,当前选择已达到的重量和，本方案可能达到的总价值tv）/*考虑物品i 包含在当前方案中的可能性*/if（包含物品i 是可以接受的）（将物品i 包含在当前方案中；if（in-l）try（i+l,tw+物品 i 的重量,tv）;else/*又一个完整方案，因为它比前面的方案好，以它作为最佳方案*/以当前方案作为临时最佳方案保存；恢复物品i 不包含状态；）/*考虑物品i 不包含在当前方案中的可能性*/if（不包含物品i 仅是可男考虑的）if（in-l）try（i+l,tw,tv-物品 i 的价值）；else/*又一个完整

24、方案，因它比前面的方案好，以它作为最佳方案*/以当前方案作为临时最佳方案保存；为了理解上述算法，特举以下实例。设有4 件物品，它们的重量和价值见表：物品 0 1 2 3重量 5321价值 4431并设限制重量为7。则按以上算法，下图表示找解过程。由图知，一旦找到一个解，算法就进一步找更好的佳。如能判定某个查找分支不会找到更好的解，算法不会在该分支继续查找,而是立即终止该分支，并去考察下一个分支。按上述算法编写函数和程序如下：【程序】#include#define N 100double limitW,totV,maxV;int optionN,copN;struct double weight

25、;double value;aN;int n;void find(int i,double tw,double tv)int k;/*考虑物品i 包含在当前方案中的可能性*/if(tw+ai.weight=limitW)copi=l;if(in-l)find(i+l,tw+ai.weight,tv);else for(k=0;kmaxV)if(in-l)find(i+1 ,tw,tv-ai.value);else for(k=O;kn;k+)optionk=copk;maxv=tv-ai.value;void main()int k;double w,v;printf(“输入物品种数n”)；s

26、canR(“d”,&n);printf(“输入各物品的重量和价值n);for(totv=0.0,k=0;kn;k+)scanfC%lf%lF,&w,&v);ak.weight=w;ak.value=v;totV+=V;)prints”输入限制重量n);scanCu%ir,&limitV);maxv=0.0;for(k=0;kn;k+)copk=0;find(0,0.0,totV);for(k=0;kn;k+)if(optionk)printff%4d”,k+1);prints n 总价值为.2仇”，maxv);作为对比，下面以同样的解题思想，考虑非递归的程序解。为了提高找解速度，程序不是简单地

27、逐一生成所有候选解，而是从每个物品对候选解的影响来形成值得进步考虑的候选解，一个候选解是通过依次考察每个物品形成的。对物品i 的考察有这样几种情况：当该物品被包含在候选解中依旧满足解的总重量的限制，该物品被包含在候选解中是应该继续考虑的；反之，该物品不应该包括在当前正在形成的候选解中。同样地，仅当物品不被包括在候选解中，还是有可能找到比目前临时最佳解更好的候选解时，才去考虑该物品不被包括在候选解中；反之，该物品不包括在当前候选解中的方案也不应继续考虑。对于任一值得继续考虑的方案，程序就去进一步考虑下一个物品。【程序】#include#define N 100double limitW;int

28、copN;struct ele double weight;double value;aN;int k,n;struct int fig;double tw;double tv;twvN;void next(int i,double tw,double tv)twvi.flg=l;twvi.tw=tw;twvi.tv=tv;)double find(struct ele*a,int n)int i,k,f；double maxv,tw,tv,totv;maxv=0;for(totv=0.0,k=0;k=0)ftwvi.flg;tw=twvi.tw;tv=twvi.tv;switch case

29、1:twvi.flg+;if(tw+ai.weight=limitW)if(in-l)next(i+1 ,tw+ai.weight,tv);i+;else maxv=tv;for(k=0;kmaxv)if(in-l)next(i+l,tw,tv-ai.value);i+；else maxv=tv-ai.value;for(k=0;kn;k+)copk=twvk.flg!=0;break;)return maxv;void main()double maxv;printf(“输入物品种数n”)；scanR(“d”,&n);printf(输入限制重量W);scanf%ir,&limitW);pr血

30、f(“输入各物品的重量和价值n”)；for(k=0;kn;k+)scanf(u%1 f%1 f&ak.weight,&ak.value);maxv=find(a,n);printf(n选中的物品为n);for(k=0;k j。因此，对于约束集D具有完备性的问题P,一旦检测断定某个j 元 组(x l,x 2,，x j)违 反 D中仅涉及x l,x 2,，x j 的一个约束，就可以肯定，以(x l,x 2,，x j)为前缀的任何n 元 组(x l(x 2,x j,x j+1,，x n)都不会是问题P的解，因而就不必去搜索它们、检测它们。回溯法正是针对这类问题，利用这类问题的上述性质而提出来的比枚举

31、法效率更高的算法。回溯法首先将问题P的 n 元组的状态空间E表示成一棵高为n 的带权有序树T,把在E中求问题P的所有解转化为在T中搜索问题P的所有解。树 T类似于检索树，它可以这样构造：设 S i 中的元素可排成 x i，x i(2)，x i(mi-l),|S i|=mi,i=l,2,n。从根开始，让 T的第I 层的每一个结点都有m i 个儿子。这 m i 个儿子到它们的双亲的边，按从左到右的次序，分别带权 x i+l(l)，x i+l(2)，,x i+l(mi),i=0,1,2,n-1。照这种构造方式，E中的一个n 元 组(x l,x 2,，x n)对应于T中的个叶子结点，T的根到这个叶子结

32、点的路径上依次的n 条边的权分别为x l,x 2,，x n,反之亦然。另外，对于任意的 O W i W n-1,E 中 n 元 组(x l,x 2,x n)的一个前缀 I 元 组(x l,x 2,x i)对应于T中的个非叶子结点，T的根到这个非叶子结点的路径.上依次的I 条边的权分别为x l,x 2,，x i,反之亦然。特别，E中的任意一个n 元组的空前缀()，对应于T的根。因而，在 E中寻找问题P的一个解等价于在T中搜索一个叶子结点，要求从T的根到该叶子结点的路径上依次的n 条边相应带的n 个权x l,x 2,，x n满足约束集D的全部约束。在 T 中搜索所要求的叶子结点，很自然的种方式是从

33、根出发，按深度优先的策略逐步深入，即依次搜索满足约束条件的前缀1 元 组(x l i)、前 缀 2元 组(x l,x 2)、，前 缀 I 元组(x l,x 2,x i),直到 i=n 为止。在回溯法中，上述引入的树被称为问题P的状态空间树：树 T 上任意个结点被称为问题 P的状态结点；树 T上的任意一个叶子结点被称为问题P的一个解状态结点；树 T上满足约束集D的全部约束的任意一个叶子结点被称为问题P的一个回答状态结点，它对应于问题P的一个解。【问题】组合问题问题描述：找出从自然数1、2、n 中任取r 个数的所有组合。例如n=5,r=3 的所有组合为：(1)1、2、3 (2)1、2、4 (3)1

34、、2、5(4)1、3、4 (5)1、3、5 (6)1、4、5(7)2、3、4 (8)2、3、5 (9)2、4、5(1 0)3、4、5则该问题的状态空间为：E=(x l,x 2,x 3)I x i E S ,i=l,2,3 其中：S=1,2,3,4,5 约束集为：x l x 2 ai,后一个数字比前一个大;(2)ai-i=n-r+1 o按回溯法的思想，找解过程可以叙述如下：首先放弃组合数个数为r 的条件，候选组合从只有个数字1 开始。因该候选解满足除问题规模之外的全部条件，扩大其规模，并使其满足上述条件(1),候选组合改为1,2。继续这一过程，得到候选组合1,2,3。该候选解满足包括问题规模在内

35、的全部条件，因而是一个解。在该解的基础上，选下一个候选解，因 a2上的3 调整为4,以及以后调整为5都满足问题的全部要求，得到解1,2,4 和 1,2,5。由于对-5 不能再作调整，就要从a2回溯到a l,这时，al=2,可以调整为3,并向前试探，得到解1,3,4。重复上述向前试探和向后回溯，直至要从a0再回溯时，说明己经找完问题的全部解。按上述思想写成程序如下：【程序】#define MAXN 100int aMAXN;void comb(int m,int r)int ij;i=0;ai=l；do if(ai-i=m-r+1 if(i=r-l)for(j=O;jr;j+)printfC%4

36、d”,aj);printffn”)；ai+;continue;)else if(i=O)return;a-i+；while(1)main()comb(5,3)；【问题】填字游戏问题描述：在 3 X 3 个方格的方阵中要填入数字1 到 N(N 2 1 0)内的某9 个数字，每个方格填一个整数，似的所有相邻两个方格内的两个整数之和为质数。试求出所有满足这个要求的各种数字填法。可用试探发找到问题的解，即从第一个方格开始，为当前方格寻找一个合理的整数填入，并在当前位置正确填入后，为下方格寻找可填入的合理整数。如不能为当前方格找到个合理的可填证书，就要回退到前一方格，调整前一方格的填入数。当第九个方格也

37、填入合理的整数后，就找到了一个解，将该解输出，并调整第九个的填入的整数，寻找下一个解。为找到一个满足要求的9 个数的填法，从还未填一个数开始，按某种顺序(如从小到大的顺序)每次在当前位置填入个整数，然后检查当前填入的整数是否能满足要求。在满足要求的情况下，继续用同样的方法为下一方格填入整数。如果最近填入的整数不能满足要求，就改变填入的整数。如对当前方格试尽所有可能的整数，都不能满足要求，就得回退到前一方格，并调整前一方格填入的整数。如此重复执行扩展、检查或调整、检查，直到找到一个满足问题要求的解，将解输出。回溯法找一个解的算法：int m=0,ok=l;int n=8;doif(o k)扩展;

38、else 调整；ok=检查前m 个整数填放的合理性；while(!ok|m!=n)&(m!=0)if(m!=0)输出解；else 输出无解报告；如果程序要找全部解，则在将找到的解输出后，应继续调整最后位置上填放的整数，试图去找下一个解。相应的算法如下：回溯法找全部解的算法：int m=0,ok=1;int n=8;doif(ok)if(m=n)(输出解；调整；else 扩展；else 调整；ok=检查前m 个整数填放的合理性；while(m!=0);为了确保程序能够终止，调整时必须保证曾被放弃过的填数序列不会再次实验，即要求按某种有许模型生成填数序列。给解的候选者设定一个被检验的顺序，按这个顺

39、序逐 形成候选者并检验。从小到大或从大到小，都是可以采用的方法。如扩展时，先在新位置填入整数1,调整时，找当前候选解中下一个还未被使用过的整数。将上述扩展、调整、检验都编写成程序，细节见以下找全部解的程序。【程序】#include#define N 12void write(int a)int ij;for(i=0;i0;i+)if(m=primesi)return 1;fbr(i=3;i*i=m;)if(m%i=0)return 0;i+=2;return 1;)mtcheckmatrix3=2,4,-1,3,-1,4,6,-1),5,7,-1);int selectnum(int star

40、t)intj;for(j=start;j=Nif(bj)return jreturn 0;int check(int pos)int ij;if(pos=0;i+4-)if(!isprime(apos+aj)return 0;return 1;int extend(int pos)a-H-pos=selectnum(1);bapos=0;return pos;)int change(int pos)intj；while(pos=0&(j=selectnum(apos+1)=0)bapos-=l;if(pos=0)void main()int i；for(i=l;i=N;i-+)bi=l；fin

41、d。；【问题】n 皇后问题问题描述：求 出 在 个 n X n 的棋盘上，放置n 个不能互相捕捉的国际象棋“皇后”的所有布局。这是来源于国际象棋的一个问题。皇后可以沿着纵横和两条斜线4 个方向相互捕捉。如图所示，一个皇后放在棋盘的第4 行第3 列位置上，则棋盘上凡打“X”的位置上的皇后就能与这个皇后相互捕捉。1 2 3 4 5 6 7 8XXXXXXXXXQXXXX XXXXXXXXXXX从图中可以得到以下启示：一个合适的解应是在每列、每行上只有 个皇后，且一条斜线上也只有一个皇后。求解过程从空配置开始。在 第1列至第m列为合理配置的基础上，再配置第m+1歹I J,直至第n列配置也是合理时，就

42、找到了一个解。接着改变第n列配置，希望获得下个解。另外，在任一列上，可能有n种配置。开始时配置在第1行，以后改变时，顺次选择第2行、第3行、直到第n行。当第n行配置也找不到一个合理的配置时，就要回溯，去改变前一列的配置。得到求解皇后问题的算法如下：输入棋盘大小值n；m=0;g o o d=l;d o if (g o o d)if (m=n)(输出解；改变之，形成下一个候选解;els e 扩展当前候选接至下一列；els e 改变之，形成下一个候选解；8 0 0(1=检查当前候选解的合理性；w h ile(m!=0);在编写程序之前，先确定边式棋盘的数据结构。比较直观的方法是采用一个二维数组，但仔

43、细观察就会发现，这种表示方法给调整候选解及检查其合理性带来困难。更好的方法乃是尽可能直接表示那些常用的信息。对于本题来说，“常用信息”并不是皇后的具体位置，而 是“一个皇后是否已经在某行和某条斜线合理地安置好了”。因在某一列上恰好放一个皇后，引入一个一维数组（col）,值 coli表示在棋盘第i 歹 h coli行有一个皇后。例如：col3=4,就表示在棋盘的第3 歹 IJ、第 4 行上有一个皇后。另外，为了使程序在找完了全部解后回溯到最初位置，设定col的初值为0 当回溯到第0 列时，说明程序已求得全部解，结束程序运行。为使程序在检查皇后配置的合理性方面简易方便，引入以下三个工作数组：（1）

44、数组a口，ak表示第k 行上还没有皇后；（2）数组b,bk表示第k 列右高左低斜线上没有皇后；（3）数 组 c,ck表示第k 列左高右低斜线上没有皇后；棋盘中同一右高左低斜线上的方格，他们的行号与列号之和相同；同-左高右低斜线上的方格，他们的行号与列号之差均相同。初始时，所有行和斜线上均没有皇后，从 第 1列的第1行配置第一个皇后开始，在第m列 colm行放置了一个合理的皇后后，准备考察第m+1列时，在数组a、b和c中为第m 歹 lj,colm行的位置设定有皇后标志；当从第m 列回溯到第m-1歹 U，并准备调整第m-1列的皇后配置时，清除在数组a、b 口和c 口中设置的关于第m-1歹 U，行有

45、皇后的标志。一个皇后在m 列，colm行方格内配置是合理的，由数组a、b和c对应位置的值都为1来确定。细节见以下程序：【程序】#include#include#define MAXN 20int n,m,good;int colMAXN+1 ,aMAXN+1 ,b2*MAXN+l,c2*MAXN+l;void main()in t j；c h ar aw n;p r in t f(t 4E n t er n:)；s c an f T%d”,&n);f b r (j=O;j v=n;j+)a j =l;f o r (j=0;j=2*n;j+)c b j =c j =l;m=l;c o l l =

46、l;g o o d=l;c o l 0=0;d o i f (g o o d)i f (m=n)pr i n t f(“列 t 行”);f o r (j=l j=n;j+)pr i n t R 3d t%d n”,j,c o l j D；pr i n t f(uE n t e r a c h a r a c t e r (Q/q f o r e x i t)!n,);s c a n f f%c”,&a w n);i f (awn=，Q|a w n=q)e x i t(O);w h i l e (c o l m =n)m-;a c o l m =b m 4-c o l m =c n+m-c o

47、l m =1;)c o l m +4-；e l s e a c o l m =b m+c o l m =c n 4-m-c o l m =0;c o l -H-m =l;e l s e w h i l e (c o l m =n)m；a c o l m =b m 4-c o l m =c n+m-c o l m =l;colm+;good=acolm&bm+colm&cn+m-colm;while(m!=0);)试探法找解算法也常常被编写成递归函数，下面两程序中的函数queen_all()和函数queen_one()能分别用来解皇后问题的全部解和一个解。【程序】#include#include

48、#define MAXN 20int n;int colMAXN+l,aMAXN+l,b2*MAXN+l,c2*MAXN+l;void main()intj；printf(Enter n:)；scanf(d”,&n);for(j=O;j=n;j+)aj=l；for(j=0;j=2*n;j+)cbj=cj=l;queen_all(1 ,n);void queen_all(int k,int n)int i,j;char awn;for(i=l;i=n;i+)if(ai&bk+i&cn+k-i)colk=i;ai=bk+i=cn+k-i=0;if(k=n)printf(“列t 行”);fbr(j=

49、ljv=n;j+)printfT%3dt%dn”,j,colj);printfEnter a character(Q/q for exit)!n);scanRc”,&awn);if(aw n=，Q|awn=q)exit(O);queen_all(k+l,n);ai=bk+i=cn+k-i;)采用递归方法找一个解与找全部解稍有不同，在找个解的算法中，递归算法要对当前候选解最终是否能成为解要有回答。当它成为最终解时，递归函数就不再递归试探，立即返回；若不能成为解，就得继续试探。设函数queen_one()返 回 1 表示找到解，返 回 0 表示当前候选解不能成为解。细节见以下函数。【程序】#def

50、ine MAXN 20int n;int colMAXN+l,aMAXN+l,b2*MAXN+l,c2*MAXN+1 ;int queen_one(int k,int n)int i,found;i=found=0;While(!fbund&in)i fif(ai&bk+i&cn+k-i)colk=i;ai=bk+i=cn+k-i=O;if(k=n)return 1;elsefbund=queen_one(k-l,n);ai=bk+i=cn+k-i=1;return found;六、贪婪法贪婪法是一种不追求最优解，只希望得到较为满意解的方法。贪婪法一般可以快速得到满意的解，因为它省去了为找最优