《数学建模算法C语言示例》由会员分享，可在线阅读，更多相关《数学建模算法C语言示例（50页珍藏版）》请在金锄头文库上搜索。
1、【分享】常用算法设计方法常用算法设计方法在网上找到这篇常用算法设计方法 ，虽然代码是C 的，但是算法的原理都一样吧。常用算法设计方法要使计算机能完成人们预定的工作， 首先必须为如何完成预定的工作设计一个算法， 然后再根据算法编写程序。 计算机程序要对问题的每个对象和处理规则给出正确详尽的描述， 其中程序的数据结构和变量用来描述问题的对象，程序结构、函数和语句用来描述问题的算法。算法数据结构是程序的两个重要方面。算法是问题求解过程的精确描述， 一个算法由有限条可完全机械地执行的、 有确定结果的指令组成。 指令正确地描述了要完成的任务和它们被执行的顺序。 计算机按算法指令所描述的顺序执行算法的指令
2、能在有限的步骤内终止， 或终止于给出问题的解， 或终止于指出问题对此输入数据无解。通常求解一个问题可能会有多种算法可供选择，选择的主要标准是算法的正确性和可靠性，简单性和易理解性。其次是算法所需要的存储空间少和执行更快等。算法设计是一件非常困难的工作， 经常采用的算法设计技术主要有迭代法、 穷举搜索法、 递推法、贪婪法、回溯法、分治法、动态规划法等等。另外，为了更简洁的形式设计和藐视算法，在算法设计时又常常采用递归技术，用递归描述算法。一、迭代法迭代法是用于求方程或方程组近似根的一种常用的算法设计方法。设方程为 f(x)=0 ，用某种数学方法导出等价的形式x=g(x) ，然后按以下步骤执行：(
3、 1 ) 选一个方程的近似根，赋给变量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) ；迭代算法也常用于求方
4、程组的根，令X= X x0, x1,，xn-1 )设方程组为：xi=gi(X) (I=0, 1,，n-1)则求方程组根的迭代算法可描述如下：【算法】迭代法求方程组的根 for (i=0;ix=初始近似根；do for (i=0;iy=x;for (i=0;ix=gi(X);for (delta=0.0,i=0;iif (fabs(y-x)delta) delta=fabs(y-x)； while (deltaEpsilon) ；for (i=0;iprintf( “变量 x%d 的近似根是%f ” ， I ， x) ；printf( “ n ” ) ；具体使用迭代法求根时应注意以下两种可能发生
5、的情况：( 1 ) 如果方程无解，算法求出的近似根序列就不会收敛，迭代过程会变成死循环，因此在使用迭代算法前应先考察方程是否有解，并在程序中对迭代的次数给予限制；( 2 ) 方程虽然有解，但迭代公式选择不当， 或迭代的初始近似根选择不合理，也会导致迭代失败。二、穷举搜索法穷举搜索法是对可能是解的众多候选解按某种顺序进行逐一枚举和检验， 并从众找出那些符 合要求的候选解作为问题的解。1 ，【问题】 将 A、 B、 C、 D、 E、 F 这六个变量排成如图所示的三角形，这六个变量分别取6 上的整数， 且均不相同。 求使三角形三条边上的变量之和相等的全部解。 如图就是一个解。程序引入变量a、 b、
6、c、 d、 e、 f ，并让它们分别顺序取1 至 6 的证书，在它们互不相同的条件下， 测试由它们排成的如图所示的三角形三条边上的变量之和是否相等， 如相等即为一种满足要求的排列， 把它们输出。 当这些变量取尽所有的组合后， 程序就可得到全部可能的解。细节见下面的程序。【程序 1 】# includevoid 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=
7、b)|(d=c) continue;for (e=1;e0;j-)if (*ptj*ptj-1) break;if (j=0) break;for (i=VARIABLES-1;i=j;i-)if (*pt*pti-1) break;t=*ptj-1;* ptj-1 =* pt; *pt=t;for (i=VARIABLES-1;ij;i-,j+) t=*ptj; *ptj =* pt; *pt=t; 从上述问题解决的方法中， 最重要的因素就是确定某种方法来确定所有的候选解。 下面再用一个示例来加以说明。【问题】 背包问题问题描述： 有不同价值、 不同重量的物品 n 件， 求从这 n 件物品中
8、选取一部分物品的选择方案，使选中物品的总重量不超过指定的限制重量，但选中物品的价值之和最大。设 n 个物品的重量和价值分别存储于数组w 和 v 中，限制重量为 tw 。考虑一个n 元组(x0, x1,，xn-1 ),其中xi=0表示第i个物品没有选取，而 xi=1则表示第i个物品被选取。 显然这个 n 元组等价于一个选择方案。 用枚举法解决背包问题， 需要枚举所有的选取方案，而根据上述方法，我们只要枚举所有的 n 元组，就可以得到问题的解。显然，每个分量取值为 0 或 1 的 n 元组的个数共为 2n 个。而每个n 元组其实对应了一个长度为n的二进制数，且这些二进制数的取值范围为02n-1。因
9、此，如果把02n-1分别转化为相应的二进制数，则可以得到我们所需要的 2n 个 n 元组。【算法】maxv=0;for (i=0;i2n;i+) B0.n-1=0;把 i 转化为二进制数，存储于数组 B 中 ;temp_w=0;temp_v=0;for (j=0;j if (Bj=1) temp_w=temp_w+wj;temp_v=temp_v+vj;if (temp_wmaxv) maxv=temp_v;保存该 B 数组；三、递推法递推法是利用问题本身所具有的一种递推关系求问题解的一种方法。设要求问题规模为 N的解， 当 N=1 时，解或为已知， 或能非常方便地得到解。 能采用递推法构造算
10、法的问题有重要的递推性质， 即当得到问题规模为 i-1 的解后， 由问题的递推性质， 能从已求得的规模为1, 2,，i-1的一系列解，构造出问题规模为I的解。这样，程序可从i=0或i=1出发，重复地，由已知至i-1 规模的解，通过递推，获得规模为 i 的解，直至得到规模为 N 的解。【问题】 阶乘计算问题描述：编写程序，对给定的n （n三100）,计算并输出k的阶乘k! （k=1, 2,，n）的全部有效数字。由于要求的整数可能大大超出一般整数的位数， 程序用一维数组存储长整数， 存储长整数数组的每个元素只存储长整数的一位数字。如有 m位成整数N用数组a口存储：N=amx 10m-1+am- 1 x 10m-2+ +a2 x 101+a1 x 100并用 a0 存储长整数N 的位数m， 即 a0=m 。 按上述约定， 数组的每个元素存储k 的阶乘 k ！的一位数字，并从低位到高位依次存于数组的第二个元素、第三个元素。例如，5!
