第8讲循环结构经典算法二

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第八讲 循环结构的经典算法二程序设计举例,1,1.用,普通迭代法,求方程的近似实根,2.用,二分法,求一元非线性方程在某区间上的近似实根,3.用,牛顿切线法（又叫Newton迭代法）,求方程在某区间,的近似实根,4.用,矩形法,求一元函数在某区间上的积分近似值,5.用,梯形法,求一元函数在某区间上的积分近似值,本节主要内容,2,0.迭代法的一般含义,迭代法,也称辗转法，是一种不断用变量的旧值递推新值的过程。,例如：上一讲的【例4】,：,Fibonacci（斐波纳契数列）,a,0,= 0,a,1,= 1,a,2,=a,0,+a,1,a,3,=a,1,+a,2,a,4,+=a,2,+a,3,a,5,+=a,3,+a,4,a,6,+=a,4,+a,5,an=a,n-2,+a,n-1,0,1,1,2,3,5,8,a,n,3,0.迭代法的一般含义,迭代法,也称辗转法，是一种不断用变量的旧值递推新值的过程。,再如：猴子吃桃,猴子第一天摘下若干桃子，当即吃了一半，还不过瘾，又多吃了一个。第二天猴子又将剩下的桃子吃掉一半，又多吃一个。以后每天都吃掉前一天剩下的一半零一个。到第10天再想吃时，发现只剩下一个桃子。问猴子第一天共摘了多少桃子。,a,9,=2(a,10,+1),4,a,8,=2(a,9,+1),10,a,7,=2(a,8,+1),22,a,6,=2(a,7,+1),46,a,5,=2(a,6,+1),94,a,4,=2(a,5,+1),190,a,3,=2(a,4,+1),382,a,2,=2(a,3,+1),766,a,1,=2(a,2,+1),1534,4,1.用,普通迭代法,求方程的近似实根,普通迭代法的基本思想：,求一元非线性方程f(x)=0 的实根。,(1)、将方程f(x)=0化为它的等价方程：x=g(x) ,(2)、设定一个x的初值x0；,(3)、用x=g(x)求出x的下一个值x1；,(4)、再将x1代入上述公式，求出x的下一个值x2；,(5)、如此继续下去，直到前后两次求出的x值满足要求；,其中，,x,0,称为初始近似根，,x,n,称为n次近似根，,g (x),称为迭代函数。误差可用|,x,n,-x,n-1,|估计。,5,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,x1);,以上方程的等价形式,：,x=2.15-sin(1.2x),迭代函数,g(x),此程序可作为普通迭代法求方程近似实根的通用模板，只需更改：,（1）迭代初值；,（2）迭代函数；,（3）与具体方程相关的提示信息。,6,2.用二分法求方程的近似实根,先找到区间(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)继续计算。,x,y,a,b,y=f(x),(a+b)/2,f(b),f(a),f(a+b)/2),二分法的基本思想：,7,例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,/* 求近似实根 */,do, ab=(a+b)/2,fab=2*ab+sin(ab)-2.15 ;,if (fa * fab =1e-4) ;,printf(“方程的近似实根为:%.4fn,ab);,2.用二分法求方程的近似实根,8,x,y,y=f(x),r,3. 用,牛顿切线法,求,方程的近似实根,x,n+1,=x,n,f(x,n,)/f(x,n,),，是r的n+1次近似值，称为牛顿迭代公式,(x,0,f(x,0,),x,0,x,1,(x,1,f(x,1,),x,2,又称Newton迭代法。,其基本思路：,设,r,是,f(x,) = 0,的根，选取,x,0,作为,r,初始近似值，过点（,x,0,f(x,0,),）做曲线,y =,f(x,),的切线,L,，,L,的方程为,y = f(x,0,)+f(x,0,)(x-x,0,),，求出,L,与,x,轴交点的横坐标,x,1,= x,0,-f(x,0,)/f(x,0,),，称,x,1,为,r,的一次近似值。,过点（,x,1,f(x,1,),）做曲线,y =,f(x,),的切线，并求该切线与,x,轴交点的横坐标,x,2,= x,1,-f(x,1,)/f(x,1,),，称,x,2,为,r,的二次近似值。重复以上过程，得,r,的近似值序列。,9,3. 用,牛顿切线法,求,方程的近似实根,例3：编写程序，用Newton迭代法求方程f(x)=2x+cosx-2.6=0在区间0，4上的近似实根r，迭代初值自选，精确到0.0001。,#include ,#include ,main(),float x,x0;,x=2;,do,x0 = x;,x=x0 - (2 * x0 + cos(x0) - 2.6 ) / ( 2 - sin(x0) );,while(fabs(x-x0)=1e-4);,printf(%.4fn,x);,10,定积分概念回顾,求定积分,值，等价于求曲线y=f(x)、直线,x=a、直线x=b与x轴围成的区域的面积(图中阴形部分)。,y=f(x),x,y,x=a,x=b,b,a,11,4.用,矩形法,求定积分近似值,矩形法的基本思想：,求定积分,把区间,a,b,平均分成,n,个小区间，以每个小区间左端点的函数值为宽、小区间长度为高作矩形，然后把这,n,个小矩形的面积相加，即为所求的定积分的近似值。,显然，小区间数,n,越大，求得的定积分的近似求值的精度也越高。,的近似值,y,x,a,b,y=f(x),h,h=(b-a)/n,a,i,=a+(i-1)*h,( a,i, f(a,i,) ),12,例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.用,矩形法,求定积分近似值,13,5.用,梯形法,求定积分近似值,梯形法的基本思想：,求定积分,把区间,a,b,平均分成,n,个小区间，以每个小区间左端点的函数值为上底、右端点的函数值为下底、小区间长度为高作梯形，然后把这,n,个小梯形的面积相加，即为所求的定积分的近似值。,显然，小区间数,n,越大，求得的定积分的近似求值的精度也越高。并且可以看出，对于同样的小区间数，梯形法的精度比矩形法高。,的近似值,h=(b-a)/n,a,i,=a+(i-1)*h,y,x,a,b,y=f(x),h,( a,i, f(a,i,) ),14,例5：用梯形法求一元函数f(x)=e(-x2) 在区间0,1上的积分近似值S，保留4位小数。(区间数n=10，此参数不能改动否则影响答案，其中e为自然对数的底，表示幂运算),5.用,梯形法,求定积分近似值,即，求定积分,的近似值。,C语言库函数中求e,x,的函数是,double,exp(,double,x),有关C语言更多的库函数，请参考P351附录,15,#include,#include,main(),int i,n=10;,double a=0, b=1, h, f1, f2, s1, x;,h = ( b-a ) / n;,for(s1=0, i=1; i=n; i+), x = a + ( i-1 ) * h;,f1 = exp( - x * x );,f2 = exp( - (x + h) * (x + h) );,s1 = s1 + ( f1 + f2 ) * h / 2;,/*梯形面积累加*/,printf(梯形法算得积分值：%.4lfn, s1);,5.用,梯形法,求定积分近似值,求 的近似值,16,课堂小结,熟练掌握本节所讲的所有算法，,能够举一反三。,17,