1、第第7章章 算算 法法7.1 算法概述7.2 迭代法7.3 穷举搜索法7.4 递推法7.5 递归法7.6 分治法7.7 回溯法7.8 贪婪法习题7 实验7 7.1 算算 法法 概概 述述7.1.1 算法定义算法定义对于计算机科学来说，算法(algorithm)的概念是至关重要的。例如在一个大型软件系统的开发中，设计出更有效的算法将对开发起决定性的作用。通俗地讲，算法是指解决问题的一种方法或一个过程。更严格地讲，算法是由若干条指令组成的有穷序列，其中每个指令表示一个或多个操作，且算法满足下述几条性质：(1)输入：有零个或多个由外部提供的量作为算法的输入。(2)输出：算法产生至少一个量作为输出。(
2、3)确定性：组成算法的每条指令是清晰的、无歧义的。(4)可行性：要求算法中有待实现的运算都是基本的，每种运算至少在原理上能由人用纸和笔在有限的时间内完成。(5)有限性：算法中每条指令的执行次数是有限的，执行每条指令的时间也是有限的。程序(program)与算法不同，程序是算法用某种程序设计语言的具体实现，程序可以不满足算法的性质(5)。例如操作系统，它是一个在无限循环中执行的程序，因而不是一个算法。但是我们可把操作系统的各种任务看成是一些单独的问题，每一个问题由操作系统中的一个子程序通过特定的算法来实现，该子程序得到输出结果后便终止。7.1.2 算法设计要求算法设计要求当我们用算法来解决某问题
3、时，算法设计要达到的目标是正确、可读、健壮、高效率和低存储量。1.正确性正确性算法的正确性是指算法应该满足具体问题的需求。其中“正确”的含义大体上可以分为四个层次：(1)所设计的程序没有语法错误。(2)对于几组输入数据能够得出满足要求的结果。(3)对于精心选择的典型、苛刻而带有刁难性的几组输入数据能够得到满足要求的结果。(4)对于一切合法的输入数据都能产生满足要求的结果。对于这四层含义，要达到第(4)层正确是极为困难的。一般情况下，以第(3)层含义正确作为衡量一个程序是否正确的标准。例如：要求n个数的最大值问题，给出示意算法如下：max=0;for(i=1;imax)max=x;求最大值的算法
4、无语法错误；虽当输入n个数全为正数时，结果也对，但对输入n个数全为负数时，求得的最大值为0，显然这个结果不对。由这个简单的例子可以说明算法正确性的内涵。思考：上面求最大值算法到底应当算第几层次？是否能算是正确算法？2.可读性可读性一个好的算法首先应该便于人们理解和相互交流，其次才是机器可执行。可读性好的算法有助于人对算法的理解，而难懂的算法易于隐藏错误且难于调试和修改。3.健壮性健壮性(鲁棒性鲁棒性)健壮性即对非法输入的抵抗能力。它强调的是，如果输入非法数据，算法应能加以识别并作出处理，而不是产生误动作或陷入瘫痪。4.高效率和低存储量高效率和低存储量算法的效率通常是指算法的执行时间。对于一个具
5、体问题的解决通常可以有多个算法，其中执行时间短的算法其效率就高。所谓的存储量需求，是指算法在执行过程中所需要的最大存储空间，这两者都与问题的规模有关。7.1.3 算法的描述工具算法的描述工具描述算法可以有多种方式，如自然语言方式、传统流程图、N-S流程图，伪代码、计算机语言等。1.自然语言方式自然语言方式自然语言就是人们日常生活中交流所用的语言，如汉语、英语或其他语言。用自然语言表示的算法虽然通俗易懂，但文字冗长，容易出现“歧义”性，并且难以描述包含分支和循环的算法，因此，一般不使用自然语言描述算法。比如，描述计算并输出z=y/x的流程，可以用自然语言描述如下：(1)输入x、y。(2)判断x是
6、否为0：若x=0，则输出错误信息；否则计算y/xz，且输出z。2.传统流程图传统流程图在程序设计过程中，一般不可能在一开始就用某种程序设计语言编制计算机程序，而是先用某种简单、直观、灵活的描述工具来描述处理问题的流程。当方案确定以后，再将这样的流程转换成计算机程序，这种转换往往是机械的，已经不涉及功能的重新设计或控制流程的变化，而只需考虑程序设计语言所规定的语法要求以及一些细节问题即可。流程图就是用一些约定的几何图形来描述算法的。美国标准化协会(ANSI)规定了一些常用的流程图符号，已为世界各国程序工作者普遍采用。一些常用的流程图符号参见表7.1。其中，起止框：表示算法的开始和结束。一般内部只
7、写“开始”或“结束”。处理框：表示算法的某个处理步骤，一般内部常常填写赋值操作。输入/输出框：表示算法请求输入需要的数据或算法将某些结果输出。一般内部常常填写“输入”，“打印/显示”等内容。判断框：主要是对一个给定条件进行判断，决定如何执行其后的操作。它有一个入口，两个出口。连接点：用于将画在不同地方的流程线连接起来。同一个编号的点是相互连接在一起的，实际上同一编号的点是同一个点，只因画不下才分开画的。使用连接点，还可以避免流程线的交叉或过长，使流程图更加清晰。注释框：注释框不是流程图中必需的部分，不反映流程和操作，它只是对流程图中某些框的操作作必要的补充说明，以帮助阅读流程图的人更好地理解算
8、法。表表7.1 常用流程图符号及含义常用流程图符号及含义例如，求n个数之和的算法用流程图描述如图7.1所示。图7.1 n个数之和的传统流程图3.N-S流程图流程图N-S流程图适于结构化程序设计，是美国学者I.Nasii和B.Shneiderman于1973年提出的一种新的流程图形式。它将全部算法写在一个矩形框内，完全去掉了带箭头的流程线。这种流程图称为N-S结构化流程图(盒图)。图7.2是用于结构化程序设计的三种基本语句的N-S流程图。图7.3是n个数之和的N-S流程图。图7.2 N-S流程图图7.3 n个数之和的N-S流程图4.伪代码伪代码用传统流程图、N-S图表示算法，直观易懂，但绘制比较
9、麻烦。在设计一个算法时，可能要反复修改，而修改流程图是比较麻烦的，因此，流程图适合表示算法，但在设计算法过程中使用它并不理想。为了设计算法方便，常使用伪代码工具。伪代码是用介于自然语言和计算机语言之间的文字和符号来描述算法的。它结构性较强，比较容易书写和理解，修改起来也相对方便。其特点是不拘泥于语言的语法结构，而着重以灵活的形式表现被描述对象。它利用自然语言的功能和若干基本控制结构来描述算法。伪代码没有统一的标准，可以自己定义，也可以采用与程序设计语言类似的形式。5.计算机语言计算机语言直接使用某种程序设计语言编写的程序本质上也是问题处理方案的描述，并且是最终的描述。在一般的程序设计过程中，不
10、提倡一开始就编写程序，特别是对于大型的程序。程序是程序设计的最终产品，需要经过每一步的细致加工才能得到。如果试图一开始就编写出程序，往往会适得其反，达不到预想的结果。算法设计是一件非常复杂的工作，经常采用的算法设计技术主要有迭代法、穷举搜索法、递推法、贪婪法、回溯法、分治法、动态规划法等。另外，为了以更简洁的形式设计和实现算法，在算法设计时又常常采用递归技术。7.2 迭迭 代代 法法迭代法也称辗转法，是一种不断用变量的旧值递推新值的过程。与迭代法相对应的是直接法(或者称为一次解法)，即一次性解决问题。迭代法又分为精确迭代和近似迭代。“二分法”和“牛顿迭代法”属于近似迭代法。迭代法是用计算机解决
11、问题的一种基本方法。它利用计算机运算速度快、适合做重复性操作的特点，让计算机对一组指令(或一定步骤)进行重复执行，在每次执行这组指令(或这些步骤)时，都从变量的原值推出它的一个新值。利用迭代法解决问题，需要做好以下三个方面的工作：(1)确定迭代变量。在可以用迭代法解决的问题中，至少存在一个直接或间接地不断由旧值递推出新值的变量，这个变量就是迭代变量。(2)建立迭代关系式。所谓迭代关系式，指如何从变量的前一个值推出其下一个值的公式(或关系)。迭代关系式的建立是解决迭代问题的关键，通常可以使用递推或倒推的方法来完成。(3)对迭代过程进行控制。在什么时候结束迭代过程？这是编写迭代程序必须考虑的问题。
12、不能让迭代过程无休止地重复执行下去。迭代过程的控制通常可分为两种情况：一种是所需的迭代次数是个确定的值，可以计算出来；另一种是所需的迭代次数无法确定。对于前一种情况，可以构建一个固定次数的循环来实现对迭代过程的控制；对于后一种情况，需要进一步分析出用来结束迭代过程的条件。【程序7.1】一个饲养场引进一只刚出生的新品种兔子，这种兔子从出生的下一个月开始，每月新生一只兔子，新生的兔子也如此繁殖。如果所有的兔子都不死去，到第12个月时，该饲养场共有兔子多少只？分析：这是一个典型的递推问题。我们不妨假设第1个月时兔子的只数为n1，第2个月时兔子的只数为n2，第3个月时兔子的只数为n3根据题意，“这种兔
13、子从出生的下一个月开始，每月新生一只兔子”，则有：ni=ni-12首先，确定迭代变量：设x代表第i-1月的兔子，y代表第i个月的兔子。其次，确定迭代关系：y=2x，x=y。最后，确定迭代次数。本题的迭代次数是个确定的值，由于第一个月的兔子数是已知值，因此，迭代次数为11，即经过11次迭代后，求y表示的第12个月的兔子数。参考程序如下：main()int x=1,y=0,i=1;while(i0):);scanf(%d,&n);printf(The procedure is:n);printf(%d,n);while(n1)if(n%2=0)/*偶数*/n=n/2;elsen=n*3+1;pri
14、ntf(-%d,n);迭代法还经常用于求方程或方程组的近似根。设方程为f(x)=0，先设f(x)=g(x)-x，则方程f(x)=0可化为x=g(x)，然后按以下步骤执行：(1)选一个方程的近似根，赋给变量x0；(2)将x0的值保存于变量x1，然后计算g(x1)，并将结果存于变量x0；(3)当x0与x1差的绝对值还小于指定的精度要求时，重复步骤(2)的计算。若方程有根，并且用上述方法计算出来的近似根序列收敛，则按上述方法求得的x0就认为是方程的根。需要注意的是，以上g(x)的构造比较严格，需要满足条件|g(x)|Epsilon)；printf(方程的近似根是%fn，x0)；迭代法也常用于求方程组
15、的根，令X=(x0，x1，xn-1)设方程组为：xi=gi(X)(i=0，1，n-1)迭代法求方程组的根的C语言算法描述如下：for(i=0;in;i+)xi=初始近似根;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)；【程序程序7.3】用迭代法求方程f(x)=3x3-4x2-5x+13=0的满足精度为10-6的一个近似实根。分
16、析：本题给出牛顿迭代法求方程根的思路。牛顿迭代法中，利用f(x)的导数，采用公式x=x0-f(x0)/f(x0)计算出下一个x，重复不断地用刚计算出的x取代上一个x值，接着再用迭代公式计算新的x，直至两次计算出的x的差额不超过10-6为止。#include main()float x,x0,d,f,fd;scanf(%f,&x0);do f=3*x0*x0*x0-4*x0*x0-5*x0+13;fd=9*x0*x0-8*x0-5;d=f/fd;x=x0-d;x0=x;while(fabs(d)1e-5);printf(x=%fn,x);具体使用迭代法求根时应注意以下两种可能发生的情况：(1)如
17、果方程无解，算法求出的近似根序列就不会收敛，迭代过程会变成死循环，因此在使用迭代法前应先考察方程是否有解，并在程序中对迭代的次数给予限制。(2)方程虽然有解，但迭代公式选择不当或迭代的初始近似根选择不合理，也会导致迭代失败。7.3 穷穷举举搜搜索索法法穷举搜索法也叫枚举法或蛮干法，它对所有可能的解按某种顺序进行逐一枚举和检验，并从中找出那些符合要求的候选解作为问题的解。穷举所有可能情况，最直接的是使用循环的算法。穷举搜索法看起来是一种笨办法，但它恰好利用了计算机高速运算的能力，可以避免复杂的逻辑推理过程，使问题简单化。而对于穷举搜索法而言，我们又必须预先对搜索的范围做出选择和筛选，尽量缩小搜索
18、范围，减少循环次数，提高算法效率。【程序程序7.4】找出自然数1，2，n中r个数的组合。例n=5，r=3，所有组合为：543542541532531521432431421321分析：可以看出，r个数不能两两相同。例如，5、4、3与3、4、5。为此，约定前一个数应大于后一个数，实现时可用三重循环进行搜索。/*程序设计方法：穷举法问题描述：NR问题。N个数中选R个数的所有组合。本算法解决5个中选3个。*/#include main()int i,j,k;for(i=5;i=1;i-)for(j=5;j=1;j-)for(k=5;k=1;k-)if(i!=j)&(i!=k)&(j!=k)&(i j
19、)&(j k)printf(%3d%3d%3dn,i,j,k);为了减少循环次数，改进程序如下：#include void main()int i,j,k;for(i=5;i=1;i-)for(j=i-1;j=1;j-)for(k=j-1;k=1;k-)if(i!=j)&(i!=k)&(j!=k)printf(%3d%3d%3dn,i,j,k);【程序程序7.5】有这样的一个四位数，它的前2位数字相同，后两位数字也相同，并且还是一个完全平方数，请确定这个四位数。分析：此题求解显然用枚举法，但是如果搜索范围定为10009999，比较费时。通过分析思考，可以做以下化简，只组合4位完全平方数。/*程
20、序设计方法：穷举法问题描述：求前2位数字相同，后2位数字也相同，且为完全平方数的4位数。*/main()int n,m,a,b,c,d,i;for(i=32;i=99;i+)n=i*i;m=n;a=(int)m/1000;/*千位*/m=m-a*1000;b=(int)m/100;/*百位*/m=m-b*100;c=(int)m/10;/*十位*/d=m%10;/*个位*/if(a=b)&(c=d)printf(%d,n);可以看出，该解法循环次数少，又避免了开方运算，效率较高。7.4 递递 推推 法法递推法是利用问题本身所具有的一种递推关系求问题解的一种方法。设所求问题的规模为N，当取初值(
21、例如N=1)时，解或为已知，或能方便地得到。能采用递推法构造算法的问题有重要的递推性质，即当得到问题规模为i-1的解后，由问题的递推性质，能从已求得的规模为1，2，i-1的一系列解，构造出问题规模为i的解。这样，程序可从i=0或i=1出发，由已知推至i-1规模的解，再通过递推，获得规模为i的解，直至得到规模为N的解。递推常有顺推和倒推两种。从1开始，最终获得问题规模为i时的解，这个过程为顺推过程；如果知道初始条件为i时的解，最终要获得规模为1时的解，则为倒推过程。【程序程序7.6】斐波那契数的计算。逆推公式为：f(1)=f(2)=1，f(n)=f(n-1)+f(n-2)。/*程序设计方法：递推
22、法问题描述：输入n，求第n个斐波那契数。*/#include long int Fiboacci(int n);main()int n;long int result;printf(please input the value of n:n);scanf(%d,&n);result=Fiboacci(n);printf(result=%ldn,result);/*函数说明功能说明：斐波那契数计算参数说明：n，斐波那契数序号返回值：=1,返回结果；-1，无效计算。*/long int Fiboacci(int n)int i;long int Fib1,Fib2,Fib;Fib1=1;Fib2=
23、1;if(n=0)return-1;if(n=1)return Fib1;if(n=2)return Fib2;for(i=3;i=n;i+)Fib=Fib2+Fib1;Fib1=Fib2;Fib2=Fib;return Fib;【程序程序7.7】编写程序，求出 2!，3!，n!。设n2并且n12。分析：为求i!，可利用已求得的(i-1)!乘以i即可。特别地，1!=1是立即可得到的，所以程序可采用递推法，由1！求出2!，由2！求出3！，由(i-1)!求出i！，直至求出n!。为了使程序便于理解，该程序简化了问题，设n12。/*程序设计方法：递推法问题描述：求 0！，1！，2！，3!，n!说明：因
24、n值较小，在长整型所能表达的范围之内，所以可用长整型记录结果n!*/*n 12*/#include long int Fn(int n);main()int n;long int result;printf(please input the value of n(n=12):n);scanf(%d,&n);result=Fn(n);printf(solution=%dn,result);/*函数说明参数说明：n,阶乘的数功能说明：得到并返回n!*/long int Fn(int n)int i;long int result=1;if(n=1)return result;for(i=2;i0)
25、/*第一天的桃子数是第2天桃子数加1后的2倍*/x1=(x2+1)*2;/*求出x1为第day天的桃子数*/x2=x1;day-;printf(the total is%dn,x1);7.5 递递 归归 法法递归法是设计和描述算法的一种有力的工具，由于它在复杂算法的描述中被经常采用，为此在进一步介绍其他算法设计方法之前先讨论它。递归的定义：若一个对象部分地包含它自己,或用它自己给自己定义,则称这个对象是递归的；若一个过程直接地或间接地调用自己,则称这个过程是递归的过程。能采用递归描述的算法通常有这样的特征：为求解规模为N的问题，设计将它分解成一些规模较小的问题，然后从这些小问题的解方便地构造出
26、大问题的解，并且这些规模较小的问题也能采用同样的分解和综合方法，分解成规模更小的问题，并从这些更小问题的解构造出规模稍大问题的解。特别地，当规模N=1时，能直接得到解。这样的求解算法就可用递归来描述。前面所提及的递推法，以及后面要叙述的回溯法和分治法等都可以用递归法来求解。编写递归函数的一般模型时将程序分成二部分：第一部分是问题分解，也称递推，就是为得到问题的解，将原问题递推到比原问题简单的问题的求解。例如，求n!=f(n)，为计算f(n)，将它推到f(n-1)，即f(n)=nf(n-1)，这就是说，为计算f(n)，将问题推到计算f(n-1)，而计算f(n-1)比计算f(n)简单，因为f(n-
27、1)比f(n)更接近于已知解0!=1。使用递推时应注意：(1)递推应有终止点。例如，求n!，当n=0时，0!=1为递推的终止条件。所谓“终止条件”，就是在此条件下问题的解是明确的。缺少终止条件便会使算法失败。(2)“简单问题”表示离递推终止条件更为接近的问题。简单问题与原问题的算法是一致的，其差别主要反映在参数上。例如，f(n-1)与f(n)其参数差1。参数的变化使问题可以递推到有明确解的问题上。编写递归函数程序的第二部分是问题的回归，即从已分解的小问题的解构造出大问题的解，回归到原问题上来。例如，当计算完(n-1)!后，回归计算n(n-1)!，即得到n!的值。进行回归时应注意：(1)回归到原
28、问题的解时，算法中所涉及的处理对象应是关于当前问题的。亦即递归算法所涉及的参数与局部处理对象是有层次的。当递推进入一“简单问题”时，使用的是它自己的一套参数和局部处理对象，原问题的参数与局部对象便隐蔽起来。但当回归时，原问题的一套参数与局部处理对象又活跃起来了(2)有时回归到原问题时已得到问题的解，即回归并不引起其他动作。由于递归引起一系列的函数调用，并且可能会有一系列的重复计算，因此其执行效率相对较低，消耗的计算时间和存储空间都比非递归算法要多。所以，当某个递归算法能方便地转换成递推算法时，通常按递推算法编写程序更省时间和空间。在以下三种情况下，常常用到递归方法。(1)问题的定义是递归的。(
29、2)数据结构是递归的。(3)问题的解法是递归的 1.问题的定义是递归的例如，Ackman函数为：求解Ackman函数的递归算法为：long Ackman(long m,long n)if(m=0)return n+1;else if(n=0)return Ackman(m-1,1);else return Ackman(m-1,Ackman(m,n-1);),1,n,Ackman(m1Ackman(m),1,1Ackman(m,1nn)Ackman(m,当m=0时当n=0时当m0且n0时2.数据结构是递归的数据结构是递归的例如，单链表结构如图7.4所示。图7.4 单链表结构在链表中寻找等于给定
30、值的结点并打印其数值的递归算法为：void Print(ListNode*f,Type x)if(f)if(fdata=x)printf(fdata);else Print(flink);3.问题的解法是递归的问题的解法是递归的例如，汉诺塔(Tower of Hanoi)问题：传说婆罗门庙里有一个塔台，台上有三根标号分别为A、B、C的用钻石做成的柱子。在A柱上放着64个金盘，每一个都比下面的略小一些。把A柱上的金盘全部移到C柱上的那一天就是世界末日。移动的条件是：一次只能移动一个金盘，移动过程中大金盘不能放在小金盘上面。庙里的僧人一直不停地移动。因为全部的移动需264-1次，如果移动一次需要一
31、秒的话，需要500亿年。解决汉诺塔问题的算法如下：void Hanoi(int n,char A,char B,char C)if(n=1)printf(move:%c-%cn,A,B);elseHanoi(n-1,A,C,B);printf(move:%c-%c,A,C);Hanoi(n-1,B,A,C);【程序程序7.9】斐波那契数计算的递归程序。/*程序设计方法：递归法问题描述：斐波那契数计算*/long Fiboacci(int n);main()int n;printf(Please inout n=);scanf(%d,&n);printf(The solution is:%ldn
32、,Fiboacci(n);long Fiboacci(int n)if(n=0)/*初值处理*/return 1;else if(n=1)/*初值处理*/return 1;elsereturn(Fiboacci(n-2)+Fiboacci(n-1);/*分解问题，递推求解，求和回归*/【程序程序7.10】求两个整数M和N的最大公约数和最小公倍数。/*程序设计方法：递归*/int GetComDivisor(int m,int n);void main()int m,n;int big,small;printf(Please input m,n:);scanf(%d,%d,&m,&n);big=
33、GetComDivisor(m,n);printf(The biggest common divisor is:%dn,big);printf(The smallest common multiple is:%dn,(m*n)/big);/*函数说明GetComDivisor()功能说明：求两个整数m、m的最大公约数参数说明：两任意整数m、n返回值：m、n的最大公约数算法说明：假定r为m、n的最大公约数，k是m除以n的余数，则存在整数a,使m=a*n+k。情况1：若k=0,显然m、n的最大公约数是n。情况2：若k!=0,由于m%r=0，所以有：(a*n+k)%r=(a*n)%r+k%r=0。由
34、于 n%r=0,因此(a*n)%r=0,则必有k%r=0,由 n%r=0,k%r=0可以说明r 为n、k的最大公约数。所以求m、n的最大公约数的问题转化为求n、k的最大公约数问题。*/int GetComDivisor(int m,int n)int k;k=m%n;if(k=0)return n;else return GetComDivisor(n,k);/*转化为新的小问题*/【程序程序7.11】利用递归算法，将所输入的n个字符以相反顺序打印出来。/*程序设计方法：递归法问题描述：输入n个字符，按相反顺序打印说明：本程序只解决输入5个字符的问题*/#include stdio.hvoid
35、 palin(int n);main()palin(5);void palin(int n)char next;if(n=1)next=getchar();printf(n0:);putchar(next);elsenext=getchar();palin(n-1);putchar(next);7.6 分分 治治 法法1.分治法的基本思想分治法的基本思想任何一个可以用计算机求解的问题所需的计算时间都与其规模有关。问题的规模越小，越容易直接求解，解题所需的计算时间也越少。例如，对于n个元素的排序问题，当n=1时，不需任何计算；n=2时，只要作一次比较即可排好序；n=3时只要作3次比较即可而当n较
36、大时，问题就不那么容易处理了。要想直接解决一个规模较大的问题，有时是相当困难的。分治法的设计思想是，将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。如果原问题可分割成k个子问题，1kn，且这些子问题都可解，并可利用这些子问题的解求出原问题的解，那么分治法就是可行的。由分治法产生的子问题往往是原问题的较小模式，这就为使用递归技术提供了方便。在这种情况下，反复应用分治手段，可以使子问题与原问题类型一致而其规模却不断缩小，最终使子问题缩小到很容易直接求出其解。这自然导致递归过程的产生。分治与递归像一对孪生兄弟，经常同时应用在算法设计之中，并由此产生许多高效算法。2.
37、分治法的适用条件分治法的适用条件分治法所能解决的问题一般具有以下几个特征：(1)该问题的规模缩小到一定的程度就可以容易地解决。(2)该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质。(3)利用该问题分解出的子问题的解可以合并为该问题的解。(4)该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子子问题。上述的第一条特征是绝大多数问题都可以满足的，因为问题的计算复杂性一般是随着问题规模的增加而增加的；第二条特征是应用分治法的前提，它也是大多数问题可以满足的，此特征反映了递归思想的应用；第三条特征是关键，能否利用分治法完全取决于问题是否具有第三条特征，如果具备了第
38、一条和第二条特征，而不具备第三条特征，则可以考虑贪心法或动态规划法；第四条特征涉及到分治法的效率，如果各子问题是不独立的，则分治法要做许多不必要的工作，重复地解公共的子问题，此时虽然可用分治法，但一般用动态规划法更好。3.分治法的基本步骤分治法的基本步骤分治法在每一层递归上都有三个步骤：(1)分解：将原问题分解为若干个规模较小、相互独立、与原问题形式相同的子问题。(2)解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题。(3)合并：将各个子问题的解合并为原问题的解。根据分治法的分割原则，原问题应该分为多少个子问题才较适宜？各个子问题的规模应该怎样才为适当？这些问题很难予以准确的
39、回答。但人们从大量实践中发现，在用分治法设计算法时，最好使子问题的规模大致相同。换句话说，将一个问题分成大小相等的k个子问题的处理方法是行之有效的。许多问题可以取k=2。这种使子问题规模大致相等的做法是出自一种平衡(balancing)子问题的思想，它几乎总是比子问题规模不等的做法要好。分治法的合并步骤是算法的关键所在。有些问题的合并方法比较明显，有些问题的合并方法比较复杂，究竟应该怎样合并，没有统一的模式，需要具体问题具体分析。【程序程序7.12】设有n个选手的循环比赛。其中n=2m，要求每名选手要与其他n-1名选手都赛一次。每名选手每天比赛一次，循环赛共进行n-1天。要求每天没有选手轮空。
40、请写出赛程表。这里给出一个88的例子，如图7.5所示。图7.5 八选手方案图中第i行的第2列到第N-1列的各数表示第i个选手在第1天到第N-1天的对手。分析：将2k2k矩阵分成四块，每块是2(k-1)2(k-1)的矩阵，它应是对称的(如图7.6所示)：A与A；B与B。然后将A与B(均是2(k-1)2(k-1)的矩阵)分成四块，直至22的矩阵。此时定出每个元素的值，再按对称关系构造成赛程表。A BB A图7.6 赛程表分治法/*程序设计方法：分治法问题描述：赛程表*/#defineN64#include int contesttab(int*solu,int k,int maxx);main()
41、int soluNN,x,y,maxx,maxy,k;printf(指定n(=2的k次幂)为选手。输入 k 值:n);scanf(%d,&k);maxx=N;maxy=contesttab(solu,k,maxx);printf(选手|日期);for(x=1;x=maxy;x+)/*输出天*/printf(%3d|,x);printf(n);for(x=0;x maxy;x+)printf(_);printf(n);for(y=0;y maxy;y+)for(x=0;x maxy;x+)if(x=0)printf(%12d|,soluyx);else printf(%3d ,soluyx);p
42、rintf(n);/*函数说明:1.参数说明1)solu：解数组；2)k ：指数；3)maxx：数组的列数。2.功能：得到载有结果的数组，并返回参赛人员总数。3.算法说明：以小问题的解决为基础，按照对称的思想构造大问题的解。A|B -B|A*/int contesttab(int*solu,int k,int maxx)int halfNum,Num,x,y,m;/*赋初值*/*(solu+0*maxx+0)=1;*(solu+0*maxx+1)=2;*(solu+1*maxx+0)=2;*(solu+1*maxx+1)=1;m=1;halfNum=1;while(m k)m+;halfNum
43、*=2;Num=halfNum*2;/*填写日程表的左下角：根据左上角生成左下角*/for(y=halfNum;y Num;y+)for(x=0;x halfNum;x+)*(solu+y*maxx+x)=*(solu+(y-halfNum)*maxx+x)+halfNum;/*填写日程表的右上角：将左下角搬到右上角*/for(y=0;y halfNum;y+)for(x=halfNum;x Num;x+)*(solu+y*maxx+x)=*(solu+(y+halfNum)*maxx+x-halfNum);/*填写日程表的右下角：将左上角搬到右下角*/for(y=halfNum;y Num;
44、y+)for(x=halfNum;x Num;x+)*(solu+y*maxx+x)=*(solu+(y-halfNum)*maxx+x-halfNum);return Num;二分法是运用分治策略的典型例子。给定已排好序的n个元素，放在数组a中，现要在这n个元素中找出一个特定的元素x。首先能想到的方法是逐个与数组a中的n个元素比较，搜索完后确定x是否在其中。该方法没有很好地利用n个元素已排好序这个条件，因此在最坏情况下，需要比较n次。二分法充分利用了元素间的次序关系，其基本思想是：将n个元素分成个数大致相同的两半，取an/2与x比较，如果x=an/2，则找到，算法中止；如果xan/2，则只要
45、在数组的右半段继续搜索。具体为：int BinSrchint a,int x)low=0;high=n-1;/*置区间初值*/while(low=high)mid=(low+high)/2;if (x=amid)return mid;/*找到待查元素*/else if(xa2，则max=a1，min=a2，否则max=a2，min=a1。如果n2，则将它们分成两组，若组内元素等于2，就用上面的办法，否则再分组，最后合并。int a7=1,6,7,-3,5,9,2;/*i表示起始下标，j表示终止下标max和min中分别存放数组中从i到j的最大和最小值*/void maxmin(int i,int
46、 j,int*max,int*min)int lmax,lmin,rmax,rmin,mid;if(i=j)*max=ai;*min=aj;else if(i=j-1)if(aiaj)*max=aj;*min=ai;else *max=ai;*min=aj;else mid=(int)(i+j)/2);/*分治求解数组前半段的最大、最小值*/maxmin(i,mid,&lmax,&lmin);/*分治求解数组后半段的最大、最小值*/maxmin(mid+1,j,&rmax,&rmin);if(lmaxrmax)*max=rmax;/*开始合并结果*/else *max=lmax;if(lmin
47、0);doxm=(x1+x2)/2;fxm=2*xm*xm*xm-4*xm*xm+3*xm-6;if(fxm*fx1=1e-5);printf(gen is%6.2fn,x0);7.7 回回 溯溯 法法回溯法是一种优选搜索方法。它按设置的优选条件向前搜索，以达到目标。若搜索到某一步时，发现当前选择并不优或达不到目标，就“退回一步”回溯重新选择。这种走不通就退回再走的技术就是回溯法。而满足回溯条件的某个状态称为“回溯点”。用它可以系统地搜索一个问题的所有解或任一解。因为搜索试探过程是由计算机完成的，所以对于搜索试探要避免重复和循环，即要对搜索过的点做标记。【程序程序7.15】老鼠走迷宫问题。分析
48、：假设迷宫情况已经存入mazemn中，若(i，j)位置上可以通过，则值为0，否则为1，如图7.7所示。对于迷宫中的每个点，按东、南、西、北顺序用试探法钻迷宫。图7.7 迷宫问题#define m 5#define n 6int sf=0;int mazemn=0,0,0,1,0,0,0,1,0,0,0,0,0,1,1,1,1,0,0,0,0,0,0,1,1,0,1,1,0,0;void search(int x,int y)mazexy=2;if(x=m-1)&(y=n-1)sf=1;else if(sf!=1)&(y!=n-1)&mazexy+1=0)search(x,y+1);if(sf!
49、=1)&(x!=m-1)&mazex+1y=0)search(x+1,y);if(sf!=1)&(y!=0)&mazexy-1=0)search(x,y-1);if(sf!=1)&(x!=0)&(mazex-1y=0)search(x-1,y);if(sf!=1)mazexy=1;/*回溯，标记该点为1，避免下次再走到这儿*/main()int i,j;clrscr();search(0,0);for(i=0;im;i+)printf(n);for(j=0;jn;j+)printf(%d,mazeij);程序执行结果如下：211111211111211111222221101122可以看出，最
50、后将屏幕上所有值为2的点连接起来，就是老鼠走迷宫的路线。【程序程序7.16】八皇后问题是一个古老而著名的问题，该问题是著名的数学家高斯1850年提出的：在88格的国际象棋盘上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法？#include#include int crosscheck(int,int);/*检查对角线是否有冲突*/int verticalcheck(int,int);/*检查4个方向是否有冲突*/int safe(int,int);/*安全性检查*/void print(int 8);/*打印*/void tryrow(int
