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

实验五-综合算法应用-教师版实验五-综合算法应用-教师版实验五-综合算法应用-教师版xxx公司实验五-综合算法应用-教师版文件编号：文件日期：修订次数：第1.0次更改批准审核制定方案设计，管理制度实验五程序设计常用算法5.1实验要求与目的1．熟悉和掌握算法以及算法的特性2．熟练掌握结构化程序设计的三种基本结构3.掌握常用的数值算法（求最大公约数，迭代法、牛顿迭代法和二分法等）4.培养解决实际问题的能力5.2实验指导算法（Algorithm）是计算机解题的基本思想方法和步骤，算法被称为程序设计的灵魂，也是学习编程的必备知识。学习和掌握算法，必须要十分清楚，输入什么数据，输出什么结果，采用什么结构以及如何合理安排语句等。通常使用自然语言、结构化流程图、伪代码等来描述算法。利用计算机解决问题，首先要设计出适合计算机执行的算法，此算法包含的步骤必须是有限的，每一步都必须是明确的，最终能被计算机执行，而得到结果。算法可分为两类：数值运算算法。对问题求数值解，通过运算得出一个具体值，如求方程的根等，此类算法一般有现成的模型，算法较成熟。非数值运算算法。如用于事务管理领域，图书检索等。根据实际问题设计算法时，还要尽量考虑用重复的步骤去实现，使算法简明扼要，通用性强，不仅能减少编写程序的时间，减少上机输入和调试程序的时间，还能减少程序本身所占用的内存空间。算法应具有以下的特性：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：求两数的余数r。r=m%n；S2：判断余数r是否为0，若为0，执行S5,否则执行S3；S3：m←n，n←r；S4：求两数的余数r。r=m%n；返回S2；S5：输出最大公约数n。最小公倍数利用公式求得。即，最小公倍数=两个整数之积/最大公约数。#include<stdio.h>voidmain(){intnm,r,n,m,t;printf("pleaseinputtwonumbers:\n");scanf("%d,%d",&m,&n);nm=n*m;if(m<n){t=n;n=m;m=t;}r=m%n;while(r!=0){m=n;n=r; r=m%n;}printf("最大公约数:%d\n",n);printf("最小公倍数:%d\n",nm/n);}输入测试数据：24,8程序运行结果：最大公约数:8最小公倍数:24小结：1.求最大公约数和最小公倍数通常要求在自然数中求解。如何控制输入负数时，要求重新输入数。算法思想，先输入任意整数，然后判断其数是否符合要求，若符合正常求解，若不符合，重新输入整数。因此先输入再判断，可采用do-while循环语句实现。实现语句如下。do{printf("inputm&n");scanf("%d%d",&m,&n);}while(m<=0||n<=0);该循环条件是若m和n至少有一个为负或为0时，重新输入两整数。2.当if语句的判断省略时，程序调试也是正确的。【5.2】编程实现，用迭代法求QUOTE。求平方根的迭代公式为：QUOTE要求前后两次求出的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近似相等了，没有必要再算下去了，退出循环体，执行S6。S4：x0←x。S5：将x0代入迭代公式，求出下一个x的值。返回S3。S6：输出x的值。因为迭代变量x与x0的误差很小，所以也可以输出x0。#include<stdio.h>#include<math.h>voidmain(){doublex0,x;floata;printf("Pleaseinputapositivenumber:\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("Thesquarerootof%6.2fis%lf\n",a,x);}输入测试数据：3程序运行结果：Thesquarerootof3.00is1.732051小结：以上程序，只能输入正数，如果不小心输入了负数，程序本身没有容错设置，就会出错了。由此可以在该程序中增加一个循环程序段，用来判断输入的数是否正确。修改上述程序，实现程序的容错设置。#include<stdio.h>#include<math.h>intmain(){doublex0,x;floata;printf("Pleaseinputapositivenumber:\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("Thesquarerootof%6.2fis%lf\n",a,x);}由于精度问题，实数在计算机中实际表示时存在误差。因此，在程序设计中，判断两实数是否相等，不能采用x==x0或x-x0==0的形式。而是采用fabs(x-x0)<=10-5的形式，其含义是当两个实数的差逼近一个较小的精度值时，视这两个实数近似相等。3.迭代初值的给定可以是任意的，但初值的选取会直接影响到迭代的次数，有时也会影响迭代的收敛性。通常选取迭代初值时，估计一个与解接近的值。【5.3】编程实现，用牛顿迭代法求方程QUOTE，在2附近的根。程序文件名ex5_3.c。牛顿迭代法（Newton'smethod），又称为牛顿切线法，是牛顿在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*为止。由此得到牛顿迭代公式，牛顿迭代法求非线性方程的根的基本算法：确定迭代变量，旧值：x1；新值x；以及相对应的函数值变量f1，即代表f(x1)；导数值变量f2，即代表f’(x1)。牛顿迭代公式：x=x1-f1/f2确定迭代终止条件，当fabs(x-x0)<1e-5时，迭代终止。牛顿迭代法求非线性方程的根的算法描述：S1：先任意确定一个与真实的根接近的初始值x；S2：将x1作为旧值，x1=x；S3：求x1的函数值f1与在这点的导数值f2；S4：由牛顿迭代公式求新x；S5：判断前后两值是否小于给定的一个值精度，若是转到S6，否则返回S2；S6：输出x为方程的近似根。#include<stdio.h>#include<math.h>voidmain(){doublex,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("Therootis%6.2lf\n",x);}程序运行结果：Therootis3.00【5.4】编程实现，用二分法求方程2x3-4x2+3x-6=0在（-10,10）之间的根。程序文件名ex5_4.c。二分法，也称为对分法。是求非线性方程f(x)=0在区间[a,b]的实根的一种简单高效的求解方法。二分法求方程的根是将给定的区间一分为二为两个区间，确定存在根的区间，再对该区间一分为二为两个区间，再次确定存在根的区间。依次类推，直到分的区间足够小为止。也可以说逐次把有根区间对分，直到找到根或有根区间的长度小于给定精度为止。因此二分法求方程的根的关键问题，是如何确定存在根的区间？若函数f(x)在闭区间[a,b]上为单调函数，且f(a)与f(b)异号(即f(a)*f(b)<0)，则在该区间内f(x)有一个实根。设定f(x)=2x3-4x2+3x-6，区间为[x1,x2]，区间端点的函数值变量为f1和f2。中点变量为x,对应的函数值变量为f。如图5.2所示。图5.2二分法求根二分法求非线性方程的根的算法描述：S1．输入x1和x2的区间值；S2。求区间端点的函数值f1和f2；S3．确定在该区间内函数有根。若f1*f2>0，在该区间内无根，返回S1。否则继续S4；S4．计算x1，x2的中点，x=（x1+x2）/2；S5．计算中点的函数值f；S6．判断根存在的区间。若f*f1>0，则根存在于区间[x,x2]，更改存在根的区间，即，x1=x，f1=f。否则根存在于区间[x1,x]，更改存在根的区间，即，x2=x，f2=f。S7．判断|x1-x2|<10-5或|f(x0)|<10-5。若成立执行S8，否则返回S4；S8．输出方程的近似根x的值。#include<stdio.h>#include<math.h>voidmain(){doublex1,x2,x,f1,f2,f;do{printf("Enterx1,x2:\n");scanf("%lf,%lf",&x1,&x2);f1=2*x1*x1*x1-4*x1*x1+3*x1-6;f2=2*x2*x2*x2-4*x2*x2+3*x2-6;}while(f1*f2>0);do{x=(x1+x2)/2;f=2*x*x*x-4*x*x+3*x-6;if(f*f1<0) { x2=x;f2=f; } else{ x1=x;f1=f; }}while(fabs(x1-x2)>=1e-5);printf("root=%6.3f\n",x);}5.3实验内容【5.5】编写实现，程序功能是，利用简单迭代公式，求方程：cos(x)-x=0的一个实根。程序文件名：ex5_5.c。程序运行结果：Root=0.739086【参考源程序】#include<math.h>#include<stdio.h>voidmain(){doublex0,x1=0.0;do{x0=x1;x1=cos(x0);}while(fabs(x0-x1)>0.000001);printf("Root=%lf\n",x1);}小结：迭代步骤如下：（1）取x1初值为0.0；（2）x0=x1，把x1的值赋给x0；（3）x1=cos(x0)，求出一个新的x1；（4）若x0-x1的绝对值小于0.000001，执行步骤（5），否则执行步骤（2）；（5）所求x1就是方程cos(x)-x=0的一个实根，作为函数值返回。【5.6】编程实现，有一只猴子第一天摘下了若干个桃子，当即吃掉一半，还觉得不过瘾，又多吃了一个。第二天接着吃了剩下的桃子中的一半，仍不过瘾，又多吃了一个。以后每天都是吃前一天剩下的桃子的一半零一个。到第n天（n>1）早上猴子再去吃桃子时，只剩下一个桃子了。问猴子第一天共摘下了多少个桃子。程序文件名：ex5_6.c。输入测试数据：10程序运行结果：1534【参考源程序】#include"stdio.h"voidmain(){intday,sum;scanf("%d",&day);sum=1;do{sum=2*sum+2;day--;}while(day>1);printf("%d",sum);}小结：1.假设第1天有sum个桃子，根据题意可知第2天应有桃子sum/2-1。将问题倒过来考虑，若第n天有sum个桃子，则第n-1天就应该有2*sum+2个桃子。所以可以看成简单的迭代，将天数看成迭代次数。2.注意最后一天是不算的。【5.7】编程实现，验证谷角猜想。日本数学家谷角静夫在研究自然数时发现了一个奇怪现象：对于任意一个自然数n，若n为偶数，则将其除以2；若n为奇数，则将其乘以3，然后再加1。如此经过有限次运算后，总可以得到自然数1。人们把谷角静夫的这一发现叫做“谷角猜想”。程序文件名：ex5_7.c。输入测试数据：26程序运行结果：134020105168421#include<stdio.h>voidmain(){intn;scanf("%d",&n);while(n!=1){if(n%2==0)n=n/2;elsen=n*3+1;printf("%5d",n);}}小结：1.定义迭代变量为n，从键盘输入任意验证整数为初值。2.按照谷角的猜想，得到迭代关系式：当n为偶数时，n=n/2；当n为奇数时，n=n*3+1。3.当n=1时，迭代终止。由问题可知，对任意给定的一个自然数n，只要经过有限次运算后，能够得到自然数1，就已经完成了验证工作。5.4应用与提高【5.8】编程实现，求的值。程序文件名：ex5_8.c。提示：利用定积分的几何意义求定积分。定积分的几何意义：曲线，直线y=0、x=4和x=5所围成的曲边梯形的面积。算法思想：将积分区间n等分后，若将阴影部分看成矩形，则n个矩形的面积之和就为定积分的值，此算法称为矩形法求定积分。若将阴影部分看成梯形，则n个梯形的面积之和就为定积分的值，此算法称为梯形法求定积分。如图5.3所示。图5.3定积分的几何意义用矩形法求定积分的表达式可描述为：第一次运行程序输入测试数据：1000045程序运行结果：128.412767第二次运行程序输入测试数据：10000045程序运行结果：128.416277第三次运行程序输入测试数据：10000045程序运行结果：128.416628【参考源程序】#include<stdio.h>voidmain(){intn,i;doublea,b,x,h,f,sum=0;printf("inputn:");scanf("%d",&n);/*区间个数*/printf("inputa&b");scanf("%lf%lf",&a,&b);/*积分上下限*/h=(b-a)/n;/*矩形宽度*/for(i=0;i<n;i++){x=a+i*h;f=x*x*x+2*x*x-x;/*矩形高度*/sum=sum+f*h;}printf("%lf\n",sum);}小结：从运行结果可以看出，积分区间n等分值越大，越能够接近正确结果。利用梯形法求定积分。#include<stdio.h>voidmain(){longn,i;doublea,b,x,h,f,fh,sum=0;printf("inputn:");scanf("%ld",&n);/*区间个数*/printf("inputa&b");scanf("%lf%lf",&a,&b);/*积分上下限*/h=(b-a)/n;/*梯形高度*/f=a*a*a+2*a*a-a;for(i=1;i<=n;i++){x=a+i*h; fh=x*x*x+2*x*x-x;sum=sum+(f+fh)*h/2;f=fh;}printf("%lf\n",sum);}输入测试数据：10000045程序运行结果：128.416667从程序运行结果可以看出，梯形法比矩形法求定积分更逼近结果。【5.9】程序填空题。求两个正整数的最大公约数和最小公倍数。请填空，填空时不得增行或删行，也不得更改程序的结构，一条横线上只能填写一条语句！程序文件名ex5_9.c。#include<stdio.h>voidmain(){intnm,r,a,b,t;printf("pleaseinputtwonumbers:\n");scanf("%d,%d",&a,&b);nm=a*b;if(a<b){t=a;a=b;b=t;}while(______【1】______){a=b;____【2】_____;}nm=nm/b;printf("最大公约数:%d\n",b);printf("最小公倍数:%d\n",____【3】_____);}输入测试数据：24,8程序运行结果：最大公约数:8最小公倍数:24参考答案：【1】(r=a%b)!=0或r=a%b由辗转相除求最大公约数算法可知，余数不为零是循环继续的条件。【2】b=r在循环体内，需将a=b;b=r;从而施行辗转相除的算法。【3】nm因两正整数的最小公倍数等于两数的乘积除以最大公约数，程序中有语句nm=m*n;为两数乘积，还有语句nm=nm/b(此时b已经是最大公约数)，所以，此时nm就是最小公倍数。【5.10】程序填空题。用二分法求方程x2＝2在区间[1．4，1．5]的正实根的近似解(精确度0.00001)。请填空，填空时不得增行或删行，也不得更改程序的结构，一条横线上只能填写一条语句！程序文件名ex5_10.c。#include<stdio.h>#include<math.h>voidmain(){doublex1,x2,x,f1,f2,f;do{printf("Enterx1,x2:\n");scanf("%lf,%lf",&x1,&x2);f1=x1*x1-2;f2=x2*x2-2;}while(f1*f2>0);while(_____【1】_______){x=(x1+x2)/2;______【2】______;if(f*f2<0) { ___【3】____;f1=f; } else{ ____【4】____;f2=f; }}printf("root=%lf\n",x);}输入测试数据：1.4,1.5程序运行结果：root=1.414215参考答案：fabs(x1-x2)>=1e-5由于精度问题，判断两实数是否相等，不能采用x1==x2或x1-x2==0的形式。而是采用fabs(x1-x2)<=10-5的形式，其含义是当两个实数的差逼近一个较小的精度值时，视这两个实数近似相等。在本题中，采用二分法直到分的区间足够小为止，否则继续，所以填写fabs(x1-x2)>=1e-5。f=x*x-2由前条语句可知，x为x1,x2的中点，此时计算出中点x所对应的函数值f。x1=x在f*f2<0时，也就是f和f2异号时，说明在x和x2之间有方程的根，所以将x1=x，实现[x1,x2]区间的缩小。x2=x在f*f2>=0时，也就是f和f2同号时，说明在x和x2之间没有方程的根，那么方程的根就是在[x1,x]之间，所以将x2=x，实现[x1,x2]区间的缩小。5.5实验思考【思考1】对于题目【5.1】，我们是利用了辗转相除法求两个任意正整数的最大公约数，除此之外，还是其它方法。如辗转相减法，也称为尼考曼彻斯法，求任意两个正整数的最大公约数。其方法是不断用较大的数减较小数，直到差为零，此时被减数