实验五-综合算法应用-教师版知识讲解.doc

精品文档实验五 程序设计常用算法5.1实验要求与目的1熟悉和掌握算法以及算法的特性2熟练掌握结构化程序设计的三种基本结构3. 掌握常用的数值算法（求最大公约数，迭代法、牛顿迭代法和二分法等）4. 培养解决实际问题的能力5.2实验指导算法（Algorithm）是计算机解题的基本思想方法和步骤，算法被称为程序设计的灵魂，也是学习编程的必备知识 。学习和掌握算法，必须要十分清楚，输入什么数据，输出什么结果，采用什么结构以及如何合理安排语句等。通常使用自然语言、结构化流程图、伪代码等来描述算法。利用计算机解决问题，首先要设计出适合计算机执行的算法，此算法包含的步骤必须是有限的，每一步都必须是明确的，最终能被计算机执行，而得到结果。算法可分为两类：1. 数值运算算法。对问题求数值解，通过运算得出一个具体值，如求方程的根等，此类算法一般有现成的模型，算法较成熟。2. 非数值运算算法。如用于事务管理领域，图书检索等。根据实际问题设计算法时，还要尽量考虑用重复的步骤去实现，使算法简明扼要，通用性强，不仅能减少编写程序的时间，减少上机输入和调试程序的时间，还能减少程序本身所占用的内存空间。算法应具有以下的特性：1.有穷性：一个算法应包含有限的操作步骤而不能是无限的。 2.确定性：算法中每一个步骤应当是确定的，而不能具有二义性。3.有零个或多个输入：通常，处理的数据对象需要从外界通过输入来获得数据。4.有一个或多个输出：算法的目的就是得到结果，将其结果输出。没有输出的算法是无意义的。5.有效性：算法中每一个步骤应当能有效地执行，并得到确定的结果。【5.1】编程实现，求两个正整数的最大公约数和最小公倍数。程序文件名ex5_1.c。 分析：利用欧几里德辗转相除法求最大公约数。算法思想，假定两个整数m,n（mn），用较小的数n（除数）除较大的数m（被除数），得到余数r1；若余数r1不为零，则除数作为被除数，余数r1作为除数，相除得到余数r2；若余数r2还不为零，仍是将除数作为被除数，余数r2作为除数，相除得到余数r3，这样辗转相除，直到余数是零为止。当余数为零时的除数，称为原正整数m,n的最大公约数。 求最大公约数的算法描述。 假定两正整数为m，n，使得mn，余数为r。 S1：求两数的余数r。r=m%n； S2：判断余数r是否为0，若为0，执行S5,否则执行S3；S3：mn，nr；S4：求两数的余数r。r=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(mn) t=n; n=m; m=t; r=m%n; while (r!=0) m=n; n=r;r=m%n; printf(最大公约数:%dn,n); printf(最小公倍数:%dn,nm/n);输入测试数据：24,8程序运行结果：最大公约数:8 最小公倍数:24小结：1. 求最大公约数和最小公倍数通常要求在自然数中求解。如何控制输入负数时，要求重新输入数。算法思想，先输入任意整数，然后判断其数是否符合要求，若符合正常求解，若不符合，重新输入整数。因此先输入再判断，可采用do-while循环语句实现。实现语句如下。 do printf(input m & n); scanf(%d%d,&m,&n);while(m=0|n=0);该循环条件是若m和n至少有一个为负或为0时，重新输入两整数。 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近似相等了，没有必要再算下去了，退出循环体，执行S6。S4：x0x。S5：将x0代入迭代公式，求出下一个x的值。返回S3。S6：输出x的值。因为迭代变量x与x0的误差很小，所以也可以输出x0。#include #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(a0,a0,a0: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。牛顿迭代法（Newtons 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.2lfn,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)与 f(b)异号(即f(a)* f(b)0，在该区间内无根，返回S1。否则继续S4；S4计算x1，x2的中点，x=（x1+ x2）/2；S5计算中点的函数值f；S6判断根存在的区间。若f*f10，则根存在于区间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 #include void main( ) double x1,x2,x,f1,f2,f; do printf(Enter x1,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*f20); do x=(x1+x2)/2; f=2*x*x*x-4*x*x+3*x-6; if(f*f1=1e-5); printf(root = %6.3fn,x);5.3实验内容【5.5】编写实现，程序功能是，利用简单迭代公式，求方程：cos(x)-x=0的一个实根。程序文件名：ex5_5.c。程序运行结果：Root =0.739086【参考源程序】#include #include void main() double x0, x1=0.0; do x0=x1; x1=cos(x0); while(fabs(x0-x1)0.000001); printf(Root =%lfn, 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天（n1）早上猴子再去吃桃子时，只剩下一个桃子了。问猴子第一天共摘下了多少个桃子。程序文件名：ex5_6.c。输入测试数据：10程序运行结果：1534【参考源程序】#include stdio.hvoid main() int day,sum; scanf(%d,&day); sum=1; do sum=2*sum+2; day-; while(day1); 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程序运行结果：13 40 20 10 5 16 8 4 2 1#include void main() int n; scanf(%d,&n); while(n!=1) if(n%2=0) n=n/2; else n=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 定积分的几何意义用矩形法求定积分的表达式可描述为：第一次运行程序输入测试数据：10000 4 5程序运行结果：128.412767第二次运行程序输入测试数据：100000 4 5程序运行结果：128.416277第三次运行程序输入测试数据：100000 4 5程序运行结果：128.416628【参考源程序】#include void main() int n,i; double a,b,x,h,f,sum=0; printf(input n:); scanf(%d,&n); /* 区间个数 */ printf(input a & b); scanf(%lf%lf,&a,&b); /* 积分上下限 */ h=(b-a)/n; /* 矩形宽度 */ for(i=0;in;i+) x=a+i*h; f=x*x*x+2*x*x-x; /* 矩形高度 */ sum=sum+f*h; printf(%lfn,sum);小结：1. 从运行结果可以看出，积分区间n等分值越大，越能够接近正确结果。2. 利用梯形法求定积分。#include void main() long n,i; double a,b,x,h,f,fh,sum=0; printf(input n:); scanf(%ld,&n); /* 区间个数 */ printf(input a & 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(%lfn,sum);输入测试数据：100000 4 5程序运行结果：128.416667从程序运行结果可以看出，梯形法比矩形法求定积分更逼近结果。【5.9】程序填空题。求两个正整数的最大公约数和最小公倍数。请填空，填空时不得增行或删行，也不得更改程序的结构，一条横线上只能填写一条语句！程序文件名ex5_9.c。#include void main() int nm,r,a,b,t; printf(please input two numbers:n); scanf(%d,%d,&a,&b); nm=a*b; if(ab) t=a; a=b; b=t; while (_【1】_) a=b; _【2】_; nm=nm/b; printf(最大公约数:%dn,b); printf(最小公倍数:%dn,_【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】程序填空题。用二分法求方程x22在区间14，15的正实根的近似解(精确度0.00001)。请填空，填空时不得增行或删行，也不得更改程序的结构，一条横线上只能填写一条语句！程序文件名ex5_10.c。#include #include void main( ) double x1,x2,x,f1,f2,f; do printf(Enter x1,x2 : n); scanf(%lf,%lf,&x1,&x2); f1=x1*x1-2; f2=x2*x2-2; while(f1*f20); while(_【1】_) x=(x1+x2)/2; _【2】_; if(f*f2=1e-5 由于精度问题，判断两实数是否相等，不能采用x1=x2或x1-x2=0的形式。而是采用fabs(x1-x2)=1e-5。【2】 f=x*x-2 由前条语句可知，x为x1,x2的中点，此时计算出中点x所对应的函数值f。 【3】 x1=x 在f*f2=0时，也就是f和f2同号时，说明在x和x2之间没有方程的根，那么方程的根就是在x1,x之间，所以将x2=x，实现x1,x2区间的缩小。5.5实验思考【思考1】对于题目【5.1】，我们是利用了辗转相除法求两个任意正整数的最大公约数，除此之外，还是其它方法。如辗转相减法，也称为尼考曼彻斯法，求任意两个正整数的最大公约数。其方法是不断用较大的数减较小数，直到差为零，此时被减数或减数就为两正整数的最大公约数。用辗转相减法编程，求任意两正整数的最大公约数。输入测试数据：24,8程序运行结果：最大公约数:8 最小公倍数:24【参考源程序】#include void main() int nm,r,n,m,t; printf(please input two numbers:n); scanf(%d,%d,&m,&n); nm=n*m; if(mr)m=n;n=r; /*为了保证m总是最大的，需要判断*/ else m=r; r=m-n; printf(最大公约数:%dn,n); printf(最小公倍数:%dn,nm/n);【思考2】修改【5.7】程序，用5到15之间的所有数验证谷角猜想。并把所有数经过有限次运算后，最终变成自然数 1 的全过程打印出来。程序运行结果： 5: 16 8 4 2 16: 3 10 5 16 8 4 2 17: 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 18: 4 2 19: 28 14 7 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 110: 5 16 8 4 2 111: 34 17 52 26 13 40 20 10 5 16 8 4 2 112: 6 3 10 5 16 8 4 2 113: 40 20 10 5 16 8 4 2 114: 7 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 115: 46 23 70 35106 53160 80 40 20 10 5 16 8 4 2 1【参考源程序】#include void main() int n,i; for(i=5;i=15;i+) n=i; printf(%d:,i); while(n!=1) if(n%2=0) n=n/2; else n=n*3+1; printf(%3d,n); printf(n); 精品文档