搜索
常用算法设计方法................................................................................................................1一、迭代法................................................................................................................................1二、穷举搜索法.....................................................................................................................2三、递推法................................................................................................................................6四、递归.....................................................................................................................................7五、回溯法..............................................................................................................................15六、贪婪法..............................................................................................................................28七、分治法..............................................................................................................................33八、动态规划法...................................................................................................................391常用算法设计方法要使计算机能完成人们预定的工作，首先必须为如何完成预定的工作设计一个算法，然后再根据算法编写程序。计算机程序要对问题的每个对象和处理规则给出正确详尽的描述，其中程序的数据结构和变量用来描述问题的对象，程序结构、函数和语句用来描述问题的算法。算法数据结构是程序的两个重要方面。算法是问题求解过程的精确描述，一个算法由有限条可完全机械地执行的、有确定结果的指令组成。指令正确地描述了要完成的任务和它们被执行的顺序。计算机按算法指令所描述的顺序执行算法的指令能在有限的步骤内终止，或终止于给出问题的解，或终止于指出问题对此输入数据无解。通常求解一个问题可能会有多种算法可供选择，选择的主要标准是算法的正确性和可靠性，简单性和易理解性。其次是算法所需要的存储空间少和执行更快等。算法设计是一件非常困难的工作，经常采用的算法设计技术主要有迭代法、穷举搜索法、递推法、贪婪法、回溯法、分治法、动态规划法等等。另外，为了更简洁的形式设计和藐视算法，在算法设计时又常常采用递归技术，用递归描述算法。一、迭代法迭代法是用于求方程或方程组近似根的一种常用的算法设计方法。设方程为f(x)=0，用某种数学方法导出等价的形式x=g(x)，然后按以下步骤执行：选一个方程的近似根，赋给变量x0；将x0的值保存于变量x1，然后计算g(x1)，并将结果存于变量x0；当x0与x1的差的绝对值还小于指定的精度要求时，重复步骤（2）的计算。若方程有根，并且用上述方法计算出来的近似根序列收敛，则按上述方法求得的x0就认为是方程的根。上述算法用C程序的形式表示为：【算法】迭代法求方程的根{x0=初始近似根；do{x1=x0；x0=g(x1)；/*按特定的方程计算新的近似根*/}while(fabs(x0-x1)Epsilon)；printf(“方程的近似根是%f\n”，x0)；}迭代算法也常用于求方程组的根，令2X=（x0，x1，…，xn-1）设方程组为：xi=gi(X)(I=0，1，…，n-1)则求方程组根的迭代算法可描述如下：【算法】迭代法求方程组的根{for(i=0;in;i++)x[i]=初始近似根;do{for(i=0;in;i++)y[i]=x[i];for(i=0;in;i++)x[i]=gi(X);for(delta=0.0,i=0;in;i++)if(fabs(y[i]-x[i])delta)delta=fabs(y[i]-x[i])；}while(deltaEpsilon)；for(i=0;in;i++)printf(“变量x[%d]的近似根是%f”，I，x[i])；printf(“\n”)；}具体使用迭代法求根时应注意以下两种可能发生的情况：如果方程无解，算法求出的近似根序列就不会收敛，迭代过程会变成死循环，因此在使用迭代算法前应先考察方程是否有解，并在程序中对迭代的次数给予限制；方程虽然有解，但迭代公式选择不当，或迭代的初始近似根选择不合理，也会导致迭代失败。二、穷举搜索法穷举搜索法是对可能是解的众多候选解按某种顺序进行逐一枚举和检验，并从中找出那些符合要求的候选解作为问题的解。【问题】将A、B、C、D、E、F这六个变量排成如图所示的三角形，这六个变量分别取[1，6]上的整数，且均不相同。求使三角形三条边上的变量之和相等的全部解。如图就是一个解。程序引入变量a、b、c、d、e、f，并让它们分别顺序取1至6的证书，在它们互不相同的条件下，测试由它们排成的如图所示的三角形三条边上的变量之和是否相等，如相等即为一种满足要求的排列，把它们输出。当这些变量取尽所有的组合后，程序就可得到全部可能的解。细节见下面的程序。3【程序1】#includestdio.hvoidmain(){inta,b,c,d,e,f;for(a=1;a=6;a++)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%4d”,c,d,e);scanf(“%*c”);}}}}}}按穷举法编写的程序通常不能适应变化的情况。如问题改成有9个变量排成三角形，每条边有4个变量的情况，程序的循环重数就要相应改变。对一组数穷尽所有排列，还有更直接的方法。将一个排列看作一个长整数，则所有排列对应着一组整数。将这组整数按从小到大的顺序排列排成一个整数，从对应最小的整数开始。按数列的递增顺序逐一列举每个排列对应的每个整数，这能更有效地完成排列的穷举。从一个排列找出对应数列的下一个排列可在当前排列的基础上作部分调整来实现。倘若当前排列为1，2，4，6，5，3，并令其对应的长整数为124653。要寻找比长整数124653更大的排列，可从该排列的最后一个数字顺序向前逐位考察，当发现排列中的某个数字比它前一个数字大时，如本例中的6比它的前一位数字4大，这说明还有对应更大整数的排列。但为了顺序从小到大列举出所有的排列，不能立即调整得太大，如本例中将数字6与数字4交换得4到的排列126453就不是排列124653的下一个排列。为了得到排列124653的下一个排列，应从已经考察过的那部分数字中选出比数字大，但又是它们中最小的那一个数字，比如数字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】#includestdio.h#defineSIDE_N3#defineLENGTH3#defineVARIABLES6intA,B,C,D,E,F;int*pt[]={&A,&B,&C,&D,&E,&F};int*side[SIDE_N][LENGTH]={&A,&B,&C,&C,&D,&E,&E,&F,&A};intside_total[SIDE_N];main{}{inti,j,t,equal;for(j=0;jVARIABLES;j++)*pt[j]=j+1;while(1){for(i=0;iSIDE_N;i++){for(t=j=0;jLENGTH;j++)t+=*side[i][j];side_total[i]=t;}for(equal=1,i=0;equal&&iSIDE_N-1;i++)if(side_total[i]!=side_total[i+1]equal=0;if(equal){for(i=1;iVARIABLES;i++)printf(“%4d”,*pt[i]);printf(“\n”);scanf(“%*c”);}for(j=VARIABLES-1;j0;j--)if(*pt[j]*pt[j-1])break;if(j==0)break;5for(i=VARIABLES-1;i=j;i--)if(*pt[i]*pt[i-1])break;t=*pt[j-1];*pt[j-1]=*pt[i];*pt[i]=t;for(i=VARIABLES-1;ij;i--,j++){t=*pt[j];*pt[j]=*pt[i];*pt[i]=t;}}}从上述问题解决的方法中，最重要的因素就是确定某种方法来确定所有的候选解。下面再用一个示例来加以说明。【问题】背包问题问题描述：有不同价值、不同重量的物品n件，求从这n件物品中选取一部分物品的选择方案，使选中物品的总重量不超过指定的限制重量，但选中物品的价值之和最大。设n个物品的重量和价值分别存储于数组w[]和v[]中，限制重量为tw。考虑一个n元组（x0，x1，…，xn-1），其中xi=0表示第i个物品没有选取，而xi=1则表示第i个物品被选取。显然这个n元组等价于一个选择方案。用枚举法解决背包问题，需要枚举所有的选取方案，而根据上述方法，我们只要枚举所有的n元组，就可以得到问题的解。显然，每个分量取值为0或1的n元组的个数共为2n个。而每个n元组其实对应了一个长度为n的二进制数，且这些二进制数的取值范围为0～2n-1。因此，如果把0～2n-1分别转化为相应的二进制数，则可以得到我们所需要的2n个n元组。【算法】maxv=0;for(i=0;i2n;i++){B[0..n-1]=0;把i转化为二进制数，存储于数组B中;temp_w=0;temp_v=0;for(j=0;jn;j++){if(B[j]==1){temp_w=temp_w+w[j];temp_v=temp_v