实验五-综合算法应用-教师版-.doc

实验五 程序设计常用算法5.1实验要求与目的1．熟悉和掌握算法以及算法的特性2．熟练掌握结构化程序设计的三种基本结构3. 掌握常用的数值算法（求最大公约数，迭代法、牛顿迭代法和二分法等）4. 培养解决实际问题的能力5.2实验指导算法（Algorithm）是计算机解题的基本思想方法和步骤，算法被称为程序设计的灵魂，也是学习编程的必备知识 学习和掌握算法，必须要十分清楚，输入什么数据，输出什么结果，采用什么结构以及如何合理安排语句等通常使用自然语言、结构化流程图、伪代码等来描述算法利用计算机解决问题，首先要设计出适合计算机执行的算法，此算法包含的步骤必须是有限的，每一步都必须是明确的，最终能被计算机执行，而得到结果算法可分为两类：1. 数值运算算法对问题求数值解，通过运算得出一个具体值，如求方程的根等，此类算法一般有现成的模型，算法较成熟2. 非数值运算算法如用于事务管理领域，图书检索等根据实际问题设计算法时，还要尽量考虑用重复的步骤去实现，使算法简明扼要，通用性强，不仅能减少编写程序的时间，减少上机输入和调试程序的时间，还能减少程序本身所占用的内存空间算法应具有以下的特性：1.有穷性：一个算法应包含有限的操作步骤而不能是无限的。

2.确定性：算法中每一个步骤应当是确定的，而不能具有二义性3.有零个或多个输入：通常，处理的数据对象需要从外界通过输入来获得数据4.有一个或多个输出：算法的目的就是得到结果，将其结果输出没有输出的算法是无意义的5.有效性：算法中每一个步骤应当能有效地执行，并得到确定的结果5.1】编程实现，求两个正整数的最大公约数和最小公倍数程序文件名ex5_1.c 分析：利用欧几里德辗转相除法求最大公约数算法思想，假定两个整数m,n（m>n），用较小的数n（除数）除较大的数m（被除数），得到余数r1；若余数r1不为零，则除数作为被除数，余数r1作为除数，相除得到余数r2；若余数r2还不为零，仍是将除数作为被除数，余数r2作为除数，相除得到余数r3，这样辗转相除，直到余数是零为止当余数为零时的除数，称为原正整数m,n的最大公约数 求最大公约数的算法描述 假定两正整数为m，n，使得m>n，余数为r S1：求两数的余数rr=m%n； S2：判断余数r是否为0，若为0，执行S5,否则执行S3；S3：m←n，n←r；S4：求两数的余数rr=m%n；返回S2；S5：输出最大公约数n最小公倍数利用公式求得。

即，最小公倍数=两个整数之积/最大公约数include void main(){ int nm,r,n,m,t; printf("please input two numbers:\n"); scanf("%d,%d",&m,&n); nm=n*m; if(m

2. 当if语句的判断省略时，程序调试也是正确的5.2】编程实现，用迭代法求求平方根的迭代公式为：要求前后两次求出的x的差的绝对值小于10-5程序文件名ex5_2.c迭代算法是用计算机解决问题的一种基本方法迭代法是一种不断用变量的旧值递推新值的过程利用迭代算法解决问题，需考虑以下三个方面的问题1．确定迭代变量在可以用迭代算法解决的问题中，至少存在一个直接或间接地不断由旧值递推出新值的变量，这个变量称为迭代变量通常情况下，设定两个迭代变量一个是迭代旧值，另一个是迭代新值，并且要给定开始迭代的初值2．建立迭代公式有的问题的迭代公式是给出的，如求非线性方程的根常用的牛顿迭代公式有的问题需要递推或倒推的方法来建立迭代公式3．确定迭代终止条件即在什么时候结束迭代过程？迭代过程的控制通常可分为两种情况：一种是规定了迭代次数另一种是迭代次数无法确定，分析得出结束迭代过程的条件分析：根据题意，迭代公式已给定设定两个迭代变量x，x0，给定初值，利用迭代公式不断计算下一个x, 直到x与x0的差的绝对值小于10-5为止采用循环语句实现迭代，而此时不能确定循环次数，只给出迭代终止的条件，所以首选while循环语句或do-while循环语句来实现。

用迭代法求平方根的算法描述：S1：设定迭代变量x0（旧值）的初值（一般是可设置为a/2，当然也可以设置另外的值）；S2：用迭代公式求出下一个x（新值）的值；S3：判断x-x0的绝对值是否小于等于10-5，如条件不成立，就说明x1和x0相差较大，迭代还必须进行下去所以，程序转到S4继续执行；如条件成立，我们就认为x1和x0近似相等了，没有必要再算下去了，退出循环体，执行S6S4：x0←xS5：将x0代入迭代公式，求出下一个x的值返回S3S6：输出x的值因为迭代变量x与x0的误差很小，所以也可以输出x0include #include void main(){ double x0,x; float a; printf("Please input a positive number:\n"); scanf("%f",&a); x0=a/2; x=(x0+a/x0)/2; while(fabs(x0-x)>=1e-5) { x0=x; x=(x0+a/x0)/2; } printf("The square root of %6.2f is %lf \n",a,x);}输入测试数据：3程序运行结果：The square root of 3.00 is 1.732051小结：1. 以上程序，只能输入正数，如果不小心输入了负数，程序本身没有容错设置，就会出错了。

由此可以在该程序中增加一个循环程序段，用来判断输入的数是否正确修改上述程序，实现程序的容错设置include #include int main(){ double x0,x; float a; printf("Please input a positive number:\n"); scanf("%f",&a); while(a<0) /*判断输入是否有错误*/ { printf("a>0,a>0,a>0:\n"); /*该提示信息提示要求输入的数必须是大于0的数*/ scanf("%f",&a); } x0=a/2; x=(x0+a/x0)/2; while(fabs(x0-x)>=1e-5) { x0=x; x=(x0+a/x0)/2; } printf("The square root of %6.2f is %lf \n",a,x);} 2. 由于精度问题，实数在计算机中实际表示时存在误差因此，在程序设计中，判断两实数是否相等，不能采用x==x0或x-x0==0的形式。

而是采用fabs(x-x0)<=10-5的形式，其含义是当两个实数的差逼近一个较小的精度值时，视这两个实数近似相等3. 迭代初值的给定可以是任意的，但初值的选取会直接影响到迭代的次数，有时也会影响迭代的收敛性通常选取迭代初值时，估计一个与解接近的值5.3】编程实现，用牛顿迭代法求方程，在2附近的根程序文件名ex5_3.c牛顿迭代法（Newton's method），又称为牛顿切线法，是牛顿在17世纪提出的一种在实数域和复数域上近似求解方程的方法，是求非线性方程根的重要方法之一图5.1 牛顿迭代法求根设f(x)=0是非线性方程，f(x)在某一区间内为单调函数，则方程f(x)=0在某一区间只有一个实根牛顿迭代法的几何意义，如图5.1所示，f(x)=0的解就是y=f(x)与x轴的交点的横坐标，也就是给定一个初值x1，不断通过切线方程的迭代求解而逼近解x*的过程先设定一个与真实根接近的x1作为第一个近似根，过点（x1,f(x1)）作f(x)的切线，与x轴相交于x2，这时，我们把x2作为第二个近似根；即，过点（x2,f(x2)）作f(x)的切线，与x轴相交于x3，这时，我们把x2作为第三个近似根；即，过点（x3,f(x3)）作f(x)的切线，与x轴相交于x4，依次类推，直到接近真正的根x*为止。

由此得到牛顿迭代公式，牛顿迭代法求非线性方程的根的基本算法：1. 确定迭代变量，旧值：x1 ； 新值 x ；以及相对应的函数值变量f1，即代表f(x1)；导数值变量f2，即代表f’(x1) 2. 牛顿迭代公式：x=x1-f1/f23. 确定迭代终止条件，当fabs(x-x0)<1e-5时，迭代终止牛顿迭代法求非线性方程的根的算法描述：S1：先任意确定一个与真实的根接近的初始值x；S2：将x1作为旧值，x1=x；S3：求x1的函数值f1与在这点的导数值f2；S4：由牛顿迭代公式求新x；S5：判断前后两值是否小于给定的一个值精度，若是转到S6，否则返回S2；S6：输出x为方程的近似根include #include void main(){ double x,x1,f,f1; x=2; do{ x1=x; f=3*x1*x1*x1-9*x1*x1+4*x1-12; f1=9*x1*x1-18*x1+4; x=x1-f/f1; }while(fabs(x1-x)>=1e-5); printf("The root is%6.2lf\n",x);}程序运行结果：The root is 3.00【5.4】编程实现，用二分法求方程2x3-4x2+3x-6=0在（-10,10）之间的根。

程序文件名ex5_4.c二分法，也称为对分法是求非线性方程f(x)=0在区间[a,b]的实根的一种简单高效的求解方法二分法求方程的根是将给定的区间一分为二为两个区间，确定存在根的区间，再对该区间一分为二为两个区间，再次确定存在根的区间依次类推，直到分的区间足够小为止也可以说逐次把有根区间对分，直到找到根或有根区间的长度小于给定精度为止 因此二分法求方程的根的关键问题，是如何确定存在根的区间？ 若函数f(x)在闭区间[a,b]上为单调函数，且f(a)。