实验五-综合算法应用-教师版_第1页
实验五-综合算法应用-教师版_第2页
实验五-综合算法应用-教师版_第3页
实验五-综合算法应用-教师版_第4页
实验五-综合算法应用-教师版_第5页
已阅读5页,还剩56页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

实验五-综合算法应用-教师版实验五-综合算法应用-教师版实验五-综合算法应用-教师版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】,我们是利用了辗转相除法求两个任意正整数的最大公约数,除此之外,还是其它方法。如辗转相减法,也称为尼考曼彻斯法,求任意两个正整数的最大公约数。其方法是不断用较大的数减较小数,直到差为零,此时被减数

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论