常用算法设计方法(C语言)

《常用算法设计方法(C语言)》由会员分享，可在线阅读，更多相关《常用算法设计方法(C语言)（44页珍藏版）》请在金锄头文库上搜索。

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

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

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

4、+)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) 如果方程无解，算法求出的近似根序列就不会收敛，迭代过程会变成死循环， 因此在使用迭代算法前应先考察方程是否有解，并在程序中对迭代的次数给予 限制；(2) 方程虽然有解，但迭代公式

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

6、部可能 的解。细节见下面的程序。【程序 1】# include void 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;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)

7、printf(“%6d,a) printf(“%4d%4d”,b,f) printf(“%2d%4d%4d”,c,d,e) scanf(“%*c”)按穷举法编写的程序通常不能适应变化的情况。如问题改成有9 个变量排成三角形，每 条边有4 个变量的情况，程序的循环重数就要相应改变。对一组数穷尽所有排列，还有更直接的方法。将一个排列看作一个长整数，则所有排列 对应着一组整数。将这组整数按从小到大的顺序排列排成一个整数，从对应最小的整数开始。 按数列的递增顺序逐一列举每个排列对应的每个整数，这能更有效地完成排列的穷举。从一 个排列找出对应数列的下一个排列可在当前排列的基础上作部分调整来实现。倘若当前

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

9、前考察过程中第一个比 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,&E,&F;int *sideSIDE_NLE

10、NGTH=&A,&B,&C,&C,&D,&E,&E,&F,&A;int side_totalSIDE_N;main int i,j,t,equal;for (j=0;jVARIABLES;j+)*ptj=j+1;while(1) for (i=0;iSIDE_N;i+) for (t=j=0;jLENGTH;j+)t+=*sideij;side_totali=t;for (equal=1,i=0;equal&iSIDE_N-1;i+)if (side_totali!=side_totali+1 equal=0;if (equal) for (i=1;i0;j-)if (*ptj*ptj-1)

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

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

13、-1=0;把i转化为二进制数，存储于数组B中；temp_w=0;temp_v=0；for (j=0；jn；j+) if (Bj=1) 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=1出 发，重复地，由已知至i-1规模的解，通过递推，获得规模为i的解，直至得到规模为N的 解。【问题】 阶乘计算问题描述：编写程序，对给定的n (n- 100)，计算并输出k的阶乘k! (k=l, 2,， n)的全部有效数字。由于要求的整数可能大大超出一般整数的位数，程序用一维数组存储长整数，存储长整 数数组的每个元素只存储长整数的一位数字。如有m位成整数N用数组a存储： N=amxl0m-i+am-lxl0m-2+ +a2xl0i+alxl0。并用a0存储长整数N的位数m,即a0=m。按上述约定，数组的每个元素存储k的阶乘 k!的一位数字，并从低位到高位依次存于数组的第二个元素、第三个元素。例如，5! =120，在数组中的存储形式为：3021首元素3 表示长整数是一个3位数，接着是低位到高位依次是0、2、1，表示成整数120。计算阶乘k!可采用对已求得的阶乘(k-1)!连续累加k-1次后求得。例如，已知4! =24, 计算5 ！ ，可对原来的24累加4次24后得到120。细节见以下程