常用算法设计方法(C).docx

常用算法设计方法(C)要使计算机能完成人们预定的工作，首先必须为如何完成预定的工作设计一个算 法，然后再根据算法编写程序计算机程序要对问题的每个对象和处理规则给出 正确详尽的描述，其中程序的数据结构和变量用来描述问题的对象，程序结构、 函数和语句用來描述问题的算法算法数据结构是程序的两个重要方面算法是问题求解过程的精确描述，一个算法由有限条可完全机械地执行的、有 确定结果的指令组成指令正确地描述了要完成的任务和它们被执行的顺序计 算机按算法指令所描述的顺序执行算法的指令能在有限的步骤内终止，或终止于 给出问题的解，或终止于指出问题对此输入数据无解通常求解一个问题可能会冇多种算法可供选择，选择的主要标准是算法的正 确性和可靠性，简单性和易理解性其次是算法所需要的存储空间少和执行更快 等算法设计是一件非常困难的工作，经常采用的算法设计技术主要有迭代法、 穷举搜索法、递推法、贪焚法、冋溯法、分治法、动态规划法等等另外，为了 更简洁的形式设计和藐视算法，在算法设计吋又常常采用递归技术，用递归描述 算法一、迭代法迭代法是用于求方程或方程组近似根的一种常用的算法设计方法设方程为 f(x)=O,用某种数学方法导出等价的形式x=g(x),然后按以下步骤执行：(1) 选一个方程的近似根，赋给变量xO；(2) 将xO的值保存于变量x1,然后计算g(x1),并将结果存于变量xO；(3) 当xO与x1的差的绝对值还小于指定的精度要求时，重复步骤(2)的 计算。

若方程有根，并且用上述方法计算出来的近似根序列收敛，则按上述方法求得的 xO就认为是方程的根上述算法用C程序的形式表示为：【算法】迭代法求方程的根{ x0=初始近似根；do {x1 = x0；xO=g(x1)； 厂按特定的方程计算新的近似根*/} while (fabs(xO-x1)>Epsilon)；printf( “方程的近似根是％f\n”，xO)；}迭代算法也常用于求方程组的根，令X= (xO, x1,…，xn-1)设方程组为：xi=gi(X) (l = 0, 1,…，n-1)则求方程组根的迭代算法口J描述如下：【算法】迭代法求方程组的根{ for (i=0;i x=初始近似根；do {for (i=0;i y=x;for (i=0;i x=gi(X);for (delta=0.0,i=0;i if (fabs(y-x)>delta) delta=fabs(y-x)；} while (delta>Epsilon)；for (i=0;i printf(“变量 x［%d］的近似根是 %f”，丨，x)；printf( “\n”)；}具体使用迭代法求根时应注意以下两种可能发生的情况：(1) 如果方程无解，算法求出的近似根序列就不会收敛，迭代过程会变成死 循环，因此在使用迭代算法前应先考察方程是否有解，并在程序中对迭代的次数 给予限制；(2) 方程虽然有解，但迭代公式选择不当，或迭代的初始近似根选择不合理, 也会导致迭代失败。

二、穷举搜索法穷举搜索法是对可能是解的众多候选解按某种顺序进行逐一枚举和检验， 并从众找出那些符合要求的候选解作为问题的解问题】将A、B、C、D、E、F这六个变量排成如图所示的三角形，这六 个变量分别取［1, 6］上的整数，且均不相同求使三角形三条边上的变量Z和相 等的全部解如图就是一个解程序引入变量a、b、c、d、e、f,并让它们分别顺序取1至6的证书，在 它们互不相同的条件下，测试由它们排成的如图所示的三角形三条边上的变量之 和是否相等，如相等即为一•种满足要求的排列，把它们输出当这些变量取尽所 有的组合后，程序就可得到全部可能的解细节见卜•面的程序程序1】# in eludevoid main(){ int a,b,c,d,e,f;for (a= 1 ;a< = 6;a+ + )for (b=1;b< = 6;b+ + ) {if (b= = a) continue;for (c= 1 ;cv = 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 (“ ％P);按穷举法编写的程序通常不能适应变化的情况。

如问题改成有9个变量排成 三角形，每条边有4个变量的情况，程序的循环重数就要相应改变对一组数穷尽所有排列，还有更直接的方法将一个排列看作一个长整数, 则所有排列对应着一组整数将这组整数按从小到大的顺序排列排成一个整数， 从对应最小的整数开始按数列的递增顺序逐一列举每个排列对应的每个整数， 这能更有效地完成排列的穷举从一个排列找出对应数列的下一个排列可在当前 排列的基础上作部分调整来实现倘若当前排列为1, 2, 4, 6, 5, 3,并令其 对应的长整数为124653o要寻找比长整数124653更大的排列，可从该排列的 最后一个数字顺序向前逐位考察，当发现排列中的某个数字比它両一个数字大 时，如本例中的6比它的前一位数字4大，这说明述冇对应更大整数的排列但 为了顺序从小到大列举出所有的排列，不能立即调整得太大，如本例中将数字6 与数字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】# in elude# define SI DE_N 3# define LENGTH 3# define VARIABLES 6int A,B,C,D,E, F;int *pt[] = {&A,&B,&C,&D,&E&F};int *side[SI DE_N][LENGTH] = {&A,&B,&C,&C,&D,&E,&E,&E&A};int side_total[SIDE_N];main{}{ int equal;for (j=O;j *pt[j]=j+1；while(1){ for (i=0;i { for (t=j=O;j t+ = *side[j];side_total=t;}for (equal= 1,i=0;equal&&i if (side_total!=side_total[i+1] equal=0;if (equal){ for (i=1;i printf( “％4cT ,*pt);printf(M\nn);scant( )；for (j = VARIABLES1 ;j>O;j・・) if (*pt[j]>*pt[j-1]) break;if (j= = 0) break;for (i=VARIABLES-1;i>=j;i-)if (*pt>*pt[i-1]) break; t=*pt[j-1];* pt[j-1] =* pt; *pt=t; for (僅VARIABLES^ ;i>j;i・・,j+ + ) { t=*pt[j]; *pt[j] =* pt; *pt=t; }从上述问题解决的方法中，最重要的因索就是确定某种方法來确定所冇的候 选解。

卜•面再用一个示例來加以说明问题】背包问题问题描述：有不同价值、不同重量的物品n件，求从这n件物品中选取一 部分物詁的选择方案，使选中物品的总重量不超过指定的限制重量，但选中物品 的价值之和最大设n个物品的重量和价值分别存储于数组皿]和v[]中，限制重量为tw 考虑一个n元组(xO, x1,・・・，xn-1), 中xi=0表示第i个物品没冇选取，而 xi=1则表示第i个物品被选取显然这个n元组等价于一个选择方案用枚举法 解决背包问题，需要枚举所有的选取方案，而根据上述方法，我们只要枚举所有 的n元组，就可以得到问题的解显然，每个分量取值为0或1的n元组的个数共为2n个而每个n元组其 实对应了一个长度为n的二进制数，且这些二进制数的取值范围为0〜因 此，如果把0〜2n・1分别转化为相应的二进制数，则可以得到我们所需要的2n 个n元组算法】maxv=0;for (i=0;iv2n;i+ + ){ B[0..n-1] = 0;把i转化为二进制数，存储于数组B中；temp_w=0;temp_v=0;for (j=O;j { if (B[j] = = 1){ temp_w= temp_w+ w[j];temp_v= temp_v+ v[j];}if ((temp_w< = tw)&&(temp_v>maxv)){ maxv=temp_v;保存该B数组；三、递推法递推法是利用问题木身所具有的一•种递推关系求问题解的一•种方法。

设要 求问题规模为N的解，当N=1时，解或为已知，或能非常方便地得到解能采 用递推法构造算法的问题冇重耍的递推性质，即当得到问题规模为i・1的解后， 由问题的递推性质，能从己求得的规模为1, 2,…，i・1的一系列解，构造出问 题规模为I的解这样，程序可从i=0或i=1 tB发，重复地，由已知至i・1规模 的解，通过递推，获得规模为i的解，直至得到规模为N的解问题】阶乘计算问题描述：编写程序，对给定的n (nW100),计算并输出k的阶乘k!(k=1, 2,・・・，n)的全部有效数字由于要求的整数可能大大超出一般整数的位数，程序用一维数组存储长整 数，存储长整数数组的每个元索只存储长整数的一位数字如冇m位成整数N 用数组a[]存储：N=a[m] X 10m-1 + a[m-1] X10m-2+ …+a[2]x 101 + a[1]x 100并用a[0]存储长整数N的位数即a[0] = mo按上述约定，数组的毎个元 素存储k的阶乘k!的一位数字，并从低位到高位依次存于数组的第二个尤素、 第三个元索……例如，5! =120,在数组中的存储形式为：3 0 2 1……首元素3表示长整数是一个3位数，接着是低位到高位依次是0、2、1,表 示成整数120。

计算阶乘k!可采用对已求得的阶乘(k-1)!连续累加次后求得例如, 已知4! =24,计算5!,可对原来的24累加4次24后得到120细节见以下程 序 in elude# in elude# define MAXN 1000void pnext(int a[ ],int k){ int *b,m=a[0],i,j,r,carry;b=(int * ) malloc(sizeof(int)* (m+1))。