循环结构的经典算法之二.ppt

第八讲 循环结构的经典算法之二程序设计举例,教学重点：1.用普通迭代法求方程的近似实根2.用二分法求一元非线性方程在某区间上的近似实根3.用牛顿切线法（又叫Newton迭代法）求方程在某区间 的近似实根4.用矩形法求一元函数在某区间上的积分近似值5.用梯形法求一元函数在某区间上的积分近似值6.加密、解密算法,0.迭代法的一般含义,迭代法也称辗转法，是一种不断用变量的旧值递推新值的过程。,例如：上一讲的【例5】：Fibonacci（斐波纳契数列）,a0=0a1=1a2=a0+a1a3=a1+a2a4+=a2+a3a5+=a3+a4a6+=a4+a5an=an-2+an-1,从前有一对长寿兔子，从出生后第3个月起每个月都生一对兔子。新生的小兔子长到第3个月后每个月又都生一对兔子，这样一代一代生下去，假设所有兔子都不死，求兔子增长数量的数列（即每个月的兔子总对数）。,0112358an,0.迭代法的一般含义,迭代法也称辗转法，是一种不断用变量的旧值递推新值的过程。,再如：猴子吃桃 猴子第一天摘下若干桃子，当即吃了一半，还不过瘾，又多吃了一个。第二天猴子又将剩下的桃子吃掉一半，又多吃一个。以后每天都吃掉前一天剩下的一半零一个。到第10天再想吃时，发现只剩下一个桃子。问猴子第一天共摘了多少桃子。,0.迭代法的一般含义,再如：编程求a+aa+aaa+aaa(n个a)的值。其中a是一个从1到9之间的一个数字。要求a和n从键盘输入。提示：累加项为term=term*10+a,term初值为0。考虑序列：a0=0a1=a=a0*10+a a2=aa=a1*10+a a3=aaa=a*100+a*10+a=10*(a*10+a)+a=a2*10+aa4=aaaa=a3*10+a an=an-1*10+a 本题等价于求迭代序列的前n项和,迭代法也称辗转法，是一种不断用变量的旧值递推新值的过程。,(其中a0=0,ai=ai-1*10+a),0.迭代法的一般含义,再如 求1!+2!+3!+4!+10!考虑序列：a1=1!=1a2=2*a1a3=3*a2a4=4*a3.an=n*an-1,迭代法也称辗转法，是一种不断用变量的旧值递推新值的过程。,(其中 a1=1,ai=i*ai-1),1.用普通迭代法求方程的近似实根,普通迭代法的基本思想：设 f(x)是实函数,求方程f(x)=0 的实根。首先将f(x)=0化为它的等价方程x=g(x);再从某一实数 x0 出发，求序列xn,其中：xn-1=g(xn)n=0，1，2，如果序列xn有极限，不访设xna,当n。对上式两端取极限，就有 a=g(a),即 f(a)=0也就是说，a是方程f(x)=0的一个实根。,其中，x0 称为初始近似根，xn称为n次近似根，g(x)称为迭代函数。误差可用|xn-xn-1|估计。,注意：g(x)必须满足一定的条件，才能保证序列xn在某一区间上的收敛性。这个问题已超出本课讨论的范围。,1.用普通迭代法求方程的近似实根,例1：编写程序，用普通迭代法求方程f(x)=x+sin(1.2x)-2.15=0在区间0，5上的近似实根。迭代初值自选，精确到0.0001。,#include#include main()double x0,x1;x1=2.5;/*初始近似根*/do x0=x1;x1=2.15-sin(1.2*x0);/*迭代公式*/while(fabs(x1-x0)=1e-4);printf(“方程x+sin(1.2x)-2.15=0的近似根:”);printf(%.4fn,x0);,以上方程的等价形式：x=2.15-sin(1.2x),迭代函数g(x),此程序可作为普通迭代法求方程近似实根的通用模板，只需更改：（1）迭代初值；（2）迭代函数；（3）与具体方程相关的提示信息。,2.用二分法求方程的近似实根,二分法的基本思想：设 f(x)是连续、实函数,求方程f(x)=0 的实根。先找到区间(a,b)，使得f(a)，f(b)异号，说明在区间(a,b)内一定有实根：(1)求f(a+b)/2)。如果f(a+b)/2)=0，则(a+b)/2 就是方程的一个实根，任务完成。(2)如果f(a+b)/2)与f(b)异号,则说明方程在区间(a+b)/2，b)内实根，令a=(a+b)/2，转步骤(1)继续计算。(3)如果f(a+b)/2)与f(a)异号，则说明方程在区间(a,(a+b)/2)内有零点，令b=(a+b)/2，转步骤(1)继续计算。,利用这种方法，每次可以把f(x)的零点所在小区间收缩一半，如此下去，区间的两个端点将逐步逼近函数的零点。此法称为“二分法”。实际操作时，当f(a+b)/2)小于要求的误差时，则停止计算，此时(a+b)/2称方程的一个近似实根。,例2：编写程序，用二分法求一元非线性方程f(x)=2x+sinx-2.15=0 在区间(0，5)上的近似实根r，精确到0.0001。,#include#include main()float a=0,b=5,ab,fa,fb,fab;fa=2*a+sin(a)-2.15;fb=2*a+sin(b)-2.15;if(fa*fb 0)printf(“方程可能无实数根！”);else/*求近似实根*/,2.用二分法求方程的近似实根,3.用牛顿切线法求方程的近似实根,又称Newton迭代法。其基本思路：假设f(x)是连续、光滑、实函数，求f(x)=0的实根。设r是f(x)=0的根，选取x0作为r初始近似值，过点（x0,f(x0)）做曲线y=f(x)的切线L，L的方程为y=f(x0)+f(x0)(x-x0)，求出L与x轴交点的横坐标 x1=x0-f(x0)/f(x0)，称x1为r的一次近似值。过点（x1,f(x1)）做曲线y=f(x)的切线，并求该切线与x轴交点的横坐标 x2=x1-f(x1)/f(x1)，称x2为r的二次近似值。重复以上过程，得r的近似值序列。,其中xn+1=xnf(xn)/f(xn)，是r的n+1次近似值，又称为牛顿迭代公式。,3.用牛顿切线法求方程的近似实根,例3：编写程序，用Newton迭代法求方程f(x)=2x+cosx-2.6=0在区间0，4上的近似实根r，迭代初值自选，精确到0.0001。提示:牛顿切线法的迭代公式为 x=x f(x)/f(x),#include#include main()float x,x0;x=2;dox0=x;x=x0-(2*x0+cos(x0)-2.6)/(2-sin(x0);while(fabs(x-x0)=1e-4);printf(%.4fn,x);,定积分概念回顾,求定积分,值，等价于求曲线y=f(x)、直线,x=a、直线x=b与x轴围成的区域的面积(图中阴形部分)。,y=f(x),x,y,x=a,x=b,b,a,4.用矩形法求定积分近似值,矩形法的基本思想：求定积分把区间a,b平均分成n个小区间，以每个小区间左端点的函数值为宽、小区间长度为高作矩形，然后把这n个小矩形的面积相加，即为所求的定积分的近似值。显然，小区间数n越大，求得的定积分的近似求值的精度也越高。,的近似值,h=(b-a)/nai=a+(i-1)*h,例4：编写程序，用矩形法求一元函数f(x)=(4-(sinx)2)(1/2)在区间0，3.1416/6上的积分近似值S，保留4位小数（小区间数n=15，此参数不能改动，否则影响答案，其中表示幂运算）。,#include#include main()double x,h,a=0,b=3.1416/6,s=0;int i,n=15;h=(b-a)/n;for(i=1;i=n;i+)x=a+(i-1)*h;s=s+sqrt(4-sin(x)*sin(x);s=s*h;printf(“定积的近似值为%.4fn,s);,4.用矩形法求定积分近似值,5.用梯形法求定积分近似值,梯形法的基本思想：求定积分把区间a,b平均分成n个小区间，以每个小区间左端点的函数值为上底、右端点的函数值为下底、小区间长度为高作梯形，然后把这n个小梯形的面积相加，即为所求的定积分的近似值。显然，小区间数n越大，求得的定积分的近似求值的精度也越高。并且可以看出，对于同样的小区间数，梯形法的精度比矩形法高。,的近似值,h=(b-a)/nai=a+(i-1)*h,例5：用矩形法和梯形法求一元函数f(x)=e(-x2)在区间0,1上的积分近似值S，保留4位小数。(区间数n=10，此参数不能改动否则影响答案，其中e为自然对数的底，表示幂运算),5.用梯形法求定积分近似值,C语言库函数中求ex的函数是double exp(double x)有关C语言更多的库函数，请参考书后附录,#include#includemain()int i,n=10;double a=0,b=1,h,f1,f2,s1,s2,x;h=(b-a)/n;for(s1=0,s2=0,i=1;i=n;i+)x=a+(i-1)*h;f1=exp(-x*x);f2=exp(-(x+h)*(x+h);s1=s1+f1*h;/*矩形面积累加*/s2=s2+(f1+f2)*h/2;/*梯形面积累加*/printf(矩形法算得积分值：%.4lfn,s1);printf(梯形法算得积分值：%.4lfn,s2);,5.用梯形法求定积分近似值,求 的近似值,6.加密、解密算法(P103),例5_33:译密文。规律是将字母变成其后的第4个字母，非字母字符不变，如“China!”转换为“Gmlre！”。编写程序，从键盘输入一行字符，然后输出其相应的密文。,为使电文保密，往往按一定规律将其转换成密文，收报人再按约定的规律将其译回原文。,6.加密、解密算法(P103),例5_33:译密码。规律是将字母变成其后的第4个字母，非字母字符不变，如“China!”转换为“Gmlre！”。编写程序，从键盘输入一行字符，然后输出其相应的密文。,#includemain()char c;while(c=getchar()!=n)if(c=a/*如果不是字母*/,课堂小结,熟练掌握本节所讲的所有算法，能够举一反三。,