1、软考软件设计师专题十算法分析与设计专题十:算法分析与设计1常用的算法设计方法：1.1 迭代法1.2 穷举搜索法1.3 递推法1.4 递归法1.5 贪婪法1.6 分治法1.7 动态规划法1.8 回溯法算法基础部分:算法是对特定问题求解步骤的一种描述，算法是指令的有限序列，其中每一条指令表示一个或多个操作。算法具有以下5个属性：有穷性：一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。确定性：算法中每一条指令必须有确切的含义。不存在二义性。只有一个入口和一个出口可行性：一个算法是可行的就是算法描述的操作是可以通过已经实现的基本运算执行有限次来实现的。输入：一个算法有零个或多个输入，
2、这些输入取自于某个特定对象的集合。输出：一个算法有一个或多个输出，这些输出同输入有着某些特定关系的量。所以对应的算法设计的要求：正确性：算法应满足具体问题的需求；可读性：算法应该好读，以有利于读者对程序的理解；健壮性：算法应具有容错处理，当输入为非法数据时，算法应对其作出反应，而不是产生莫名其妙的输出结果。效率与存储量需求：效率指的是算法执行的时间；存储量需求指算法执行过程中所需要的最大存储空间。一般这两者与问题的规模有关。1.1 迭代法：迭代法是用于求方程或方程组近似根的一种常用的算法设计方法。设方程为f(x)=0，用某种数学方法导出等价的形式x=g(x)，然后按以下步骤执行：（1）选一个方
3、程的近似根，赋给变量x0；（2）将x0的值保存于变量x1，然后计算g(x1)，并将结果存于变量x0；（3）当x0与x1的差的绝对值还小于指定的精度要求时，重复步骤（2）的计算。若方程有根，并且用上述方法计算出来的近似根序列收敛，则按上述方法求得的x0就认为是方程的根。上述算法用C程序的形式表示为：【算法】迭代法求方程的根 x0=初始近似根； do x1=x0； x0=g(x1)； /*按特定的方程计算新的近似根*/ while ( fabs(x0-x1)Epsilon)； printf(“方程的近似根是%fn”，x0)；迭代算法也常用于求方程组的根，令 X=（x0，x1，xn-1）设方程组为：
4、 xi=gi(X) (I=0，1，n-1)则求方程组根的迭代算法可描述如下：【算法】迭代法求方程组的根 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”)； 具体使用迭代法求根时应注意以下两种可能发生的情况：（1）如果方程无解，算法求出的近似根序
5、列就不会收敛，迭代过程会变成死循环，因此在使用迭代算法前应先考察方程是否有解，并在程序中对迭代的次数给予限制；（2）方程虽然有解，但迭代公式选择不当，或迭代的初始近似根选择不合理，也会导致迭代失败。1.2 穷举搜索法：穷举搜索法是对可能是解的众多候选解按某种顺序进行逐一枚举和检验，并从中找出那些符合要求的候选解作为问题的解。要解决的问题只有有限种可能，在没有更好算法时总可以用穷举搜索的办法解决，即逐个的检查所有可能的情况。可以想象，情况较多时这种方法极为费时。实际上并不需要机械的检查每一种情况，常常是可以提前判断出某些情况不可能取到最优解，从而可以提前舍弃这些情况。这样也是隐含的检查了所有可能
6、的情况，既减少了搜索量，又保证了不漏掉最优解。【问题】将A、B、C、D、E、F这六个变量排成如图所示的三角形，这六个变量分别取1，6上的整数，且均不相同。求使三角形三条边上的变量之和相等的全部解。如图就是一个解。程序引入变量a、b、c、d、e、f，并让它们分别顺序取1至6的整数，在它们互不相同的条件下，测试由它们排成的如图所示的三角形三条边上的变量之和是否相等，如相等即为一种满足要求的排列，把它们输出。当这些变量取尽所有的组合后，程序就可得到全部可能的解。细节见下面的程序。# include void main() int a,b,c,d,e,f; for (a=1;a=6;a+)/a,b,c
7、,d,e依次取不同的值 for (b=1;b=6;b+) if (b=a) continue; for (c=1;c=6;c+) if (c=a)|(c=b) continue; for (d=1;d=6;d+) if (d=a)|(d=b)|(d=c) continue;for (e=1;e=6;e+) if (e=a)|(e=b)|(e=c)|(e=d) continue;f=21-(a+b+c+d+e);/最后一个用减法算if (a+b+c=c+d+e)&(a+b+c=e+f+a) printf(“%6d,a); printf(“%4d%4d”,b,f); printf(“%2d%4d%
8、4d”,c,d,e); scanf(“%c”); 按穷举法编写的程序通常不能适应变化的情况。如问题改成有9个变量排成三角形，每条边有4个变量的情况，程序的循环重数就要相应改变，循环的重数和变量的个数相关。从上述问题解决的方法中，最重要的因素就是确定某种方法来确定所有的候选解。下1.3 递推法： 递推法是利用问题本身所具有的一种递推关系求问题解的一种方法。设要求问题规模为N的解，当N=1时，解或为已知，或能非常方便地得到解。能采用递推法构造算法的问题有重要的递推性质，即当得到问题规模为i-1的解后，由问题的递推性质，能从已求得的规模为1，2，i-1的一系列解，构造出问题规模为I的解。这样，程序可
9、从i=0或i=1出发，重复地，由已知至i-1规模的解，通过递推，获得规模为i的解，直至得到规模为N的解。【问题】阶乘计算问题描述：编写程序，对给定的n（n100），计算并输出k的阶乘k！（k=1，2，n）的全部有效数字。由于要求的整数可能大大超出一般整数的位数，程序用一维数组存储长整数，存储长整数数组的每个元素只存储长整数的一位数字。如有m位成整数N用数组a 存储： N=am10m-1+am-110m-2+ +a2101+a1100并用a0存储长整数N的位数m，即a0=m。按上述约定，数组的每个元素存储k的阶乘k！的一位数字，并从低位到高位依次存于数组的第二个元素、第三个元素。例如，5！=12
10、0，在数组中的存储形式为：3021 首元素3表示长整数是一个3位数，接着是低位到高位依次是0、2、1，表示成整数120。计算阶乘k！可采用对已求得的阶乘(k-1)！连续累加k-1次后求得。例如，已知4！=24，计算5！，可对原来的24累加4次24后得到120。细节见以下程序。# include # include # define MAXN 1000void pnext(int a ,int k)/已知a中的（k-1）!,求出k！在a中。 int *b,m=a0,i,j,r,carry; b=(int * ) malloc(sizeof(int)* (m+1); for ( i=1;i=m;i
11、+) bi=ai; for ( j=1;jk;j+) /控制累加k-1次 for ( carry=0,i=1;i=m;i+)/i存放的是整数的位数 r=(i0;i-) printf(“%d”,ai);printf(“nn”);void main() int aMAXN,n,k; printf(“Enter the number n: “); scanf(“%d”,&n); a0=1; a1=1; write(a,1); for (k=2;k1时）。写成递归函数有： int fib(int n)if (n=0) return 0;if (n=1) return 1;if (n1)return f
12、ib(n-1)+fib(n-2); 递归算法的执行过程分递推和回归两个阶段。在递推阶段，把较复杂的问题（规模为n）的求解推到比原问题简单一些的问题（规模小于n）的求解。例如上例中，求解fib(n)，把它推到求解fib(n-1)和fib(n-2)。也就是说，为计算fib(n)，必须先计算fib(n-1)和fib(n-2)，而计算fib(n-1)和fib(n-2)，又必须先计算fib(n-3)和fib(n-4)。依次类推，直至计算fib(1)和fib(0)，分别能立即得到结果1和0。在递推阶段，必须要有终止递归的情况。例如在函数fib中，当n为1和0的情况。 在回归阶段，当获得最简单情况的解后，逐
13、级返回，依次得到稍复杂问题的解，例如得到fib(1)和fib(0)后，返回得到fib(2)的结果，在得到了fib(n-1)和fib(n-2)的结果后，返回得到fib(n)的结果。在编写递归函数时要注意，函数中的局部变量和参数只是局限于当前调用层，当递推进入“简单问题”层时，原来层次上的参数和局部变量便被隐蔽起来。在一系列“简单问题”层，它们各有自己的参数和局部变量。 由于递归引起一系列的函数调用，并且可能会有一系列的重复计算，递归算法的执行效率相对较低。当某个递归算法能较方便地转换成递推算法时，通常按递推算法编写程序。例如上例计算斐波那契数列的第n项的函数fib(n)应采用递推算法，即从斐波那
14、契数列的前两项出发，逐次由前两项计算出下一项，直至计算出要求的第n项。【问题】背包问题问题描述：有不同价值、不同重量的物品n件，求从这n件物品中选取一部分物品的选择方案，使选中物品的总重量不超过指定的限制重量，但选中物品的价值之和最大。设n件物品的重量分别为w0、w1、wn-1，物品的价值分别为v0、v1、vn-1。采用递归寻找物品的选择方案。设前面已有了多种选择的方案，并保留了其中总价值最大的方案于数组option ，该方案的总价值存于变量maxv。当前正在考察新方案，其物品选择情况保存于数组cop 。假定当前方案已考虑了前i-1件物品，现在要考虑第i件物品；当前方案已包含的物品的重量之和为
15、tw；至此，若其余物品都选择是可能的话，本方案能达到的总价值的期望值为tv。算法引入tv是当一旦当前方案的总价值的期望值也小于前面方案的总价值maxv时，继续考察当前方案变成无意义的工作，应终止当前方案，立即去考察下一个方案。因为当方案的总价值不比maxv大时，该方案不会被再考察，这同时保证函数后找到的方案一定会比前面的方案更好。对于第i件物品的选择考虑有两种可能：（1）考虑物品i被选择，这种可能性仅当包含它不会超过方案总重量限制时才是可行的。选中后，继续递归去考虑其余物品的选择。（2）考虑物品i不被选择，这种可能性仅当不包含物品i也有可能会找到价值更大的方案的情况。按以上思想写出递归算法如下
16、：try(物品i，当前选择已达到的重量和，本方案可能达到的总价值tv) /*考虑物品i包含在当前方案中的可能性*/ if(包含物品i是可以接受的) 将物品i包含在当前方案中； if (in-1) try(i+1,tw+物品i的重量,tv); else /*又一个完整方案，因为它比前面的方案好，以它作为最佳方案*/以当前方案作为临时最佳方案保存; 恢复物品i不包含状态； /*考虑物品i不包含在当前方案中的可能性*/ if (不包含物品i仅是可考虑的) if (in-1) try(i+1,tw,tv-物品i的价值)； else /*又一个完整方案，因它比前面的方案好，以它作为最佳方案*/以当前方案
17、作为临时最佳方案保存; 为了理解上述算法，特举以下实例。设有4件物品，它们的重量和价值见表：物品0123重量5321价值4431 并设限制重量为7。则按以上算法，下图表示找解过程。由图知，一旦找到一个解，算法就进一步找更好的解。如能判定某个查找分支不会找到更好的解，算法不会在该分支继续查找，而是立即终止该分支，并去考察下一个分支。Try(物品号，总重，价值)按上述算法编写函数和程序如下：【程序】# include # define N 100double limitW,totV,maxV;int optionN,copN;struct double weight; double value;a
18、N;int n;void find(int i,double tw,double tv) int k; /*考虑物品i包含在当前方案中的可能性*/ if (tw+ai.weight=limitW) copi=1; if (in-1) find(i+1,tw+ai.weight,tv); else for (k=0;kmaxV) if (in-1) find(i+1,tw,tv-ai.value); else for (k=0;kn;k+) optionk=copk; maxv=tv-ai.value; void main() int k; double w,v; printf(“输入物品种数n
19、”); scanf(“%d”,&n); printf(“输入各物品的重量和价值n”); for (totv=0.0,k=0;kn;k+) scanf(“%1f%1f”,&w,&v); ak.weight=w; ak.value=v; totV+=V; printf(“输入限制重量n”); scanf(“%1f”,&limitV); maxv=0.0; for (k=0;kn;k+) copk=0; find(0,0.0,totV); for (k=0;kn;k+) if (optionk) printf(“%4d”,k+1); printf(“n总价值为%.2fn”,maxv);作为对比，下面
20、以同样的解题思想，考虑非递归的程序解。为了提高找解速度，程序不是简单地逐一生成所有候选解，而是从每个物品对候选解的影响来形成值得进一步考虑的候选解，一个候选解是通过依次考察每个物品形成的。对物品i的考察有这样几种情况：1 当该物品被包含在候选解中依旧满足解的总重量的限制，该物品被包含在候选解中是应该继续考虑的；2 反之，该物品不应该包括在当前正在形成的候选解中。3 仅当物品不被包括在候选解中，还是有可能找到比目前临时最佳解更好的候选解时，才去考虑该物品不被包括在候选解中；4 该物品不包括在当前候选解中的方案也不应继续考虑。5 对于任意一个值得考虑的饿方案，程序就去进一步考虑下一个物品；【程序】# include # define N 100double limitW;int copN;struct ele double weight; double value; aN;int k,n;struct int flg; double tw; double tv; twvN;void next(int i,double tw,double tv) twvi.flg=1; twvi.tw=tw; twvi.tv=tv;double find(struct ele *a,int n)
