循环结构经典算法.ppt

《循环结构经典算法.ppt》由会员分享，可在线阅读，更多相关《循环结构经典算法.ppt（17页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第八讲第八讲 循环结构的经典算法二循环结构的经典算法二程序设计举例程序设计举例 1.1.用用普通迭代法普通迭代法求方程的近似实根求方程的近似实根2.2.用用二分法二分法求一元非线性方程在某区间上的近似实根求一元非线性方程在某区间上的近似实根3.3.用用牛顿切线法（又叫牛顿切线法（又叫NewtonNewton迭代法）迭代法）求方程在某区间求方程在某区间 的近似实根的近似实根4.4.用用矩形法矩形法求一元函数在某区间上的积分近似值求一元函数在某区间上的积分近似值5.5.用用梯形法梯形法求一元函数在某区间上的积分近似值求一元函数在某区间上的积分近似值本节主要内容0.迭代法的一般含义迭代法迭代法也称辗

2、转法，是一种不断用变量的旧值递推新值的过程。也称辗转法，是一种不断用变量的旧值递推新值的过程。例如：上一讲的【例例如：上一讲的【例4 4】：FibonacciFibonacci（斐波纳契数列）（斐波纳契数列）a0=0a1=1a2=a0+a1a3=a1+a2a4+=a2+a3a5+=a3+a4a6+=a4+a5an=an-2+an-10112358an0.迭代法的一般含义迭代法迭代法也称辗转法，是一种不断用变量的旧值递推新值的过程。也称辗转法，是一种不断用变量的旧值递推新值的过程。再如：猴子吃桃再如：猴子吃桃 猴子第一天摘下若干桃子，当即吃了一半，还不过瘾，又多吃了一个。猴子第一天摘下若干桃子，

3、当即吃了一半，还不过瘾，又多吃了一个。第二天猴子又将剩下的桃子吃掉一半，又多吃一个。以后每天都吃掉前一第二天猴子又将剩下的桃子吃掉一半，又多吃一个。以后每天都吃掉前一天剩下的一半零一个。到第天剩下的一半零一个。到第10天再想吃时，发现只剩下一个桃子。问猴子天再想吃时，发现只剩下一个桃子。问猴子第一天共摘了多少桃子。第一天共摘了多少桃子。a1a2a3a4a5a6a7a8a9a101a9=2(a10+1)4a8=2(a9+1)10a7=2(a8+1)22a6=2(a7+1)46a5=2(a6+1)94a4=2(a5+1)190a3=2(a4+1)382a2=2(a3+1)766a1=2(a2+1)

4、15341.1.用用普通迭代法普通迭代法求方程的近似实根求方程的近似实根普通迭代法的基本思想：普通迭代法的基本思想：普通迭代法的基本思想：普通迭代法的基本思想：求一元非线性方程求一元非线性方程f(x)=0 f(x)=0 的实根。的实根。(1)(1)、将方程、将方程f(x)=0f(x)=0化为它的等价方程：化为它的等价方程：x=g(x),x=g(x),(2)(2)、设定一个、设定一个x x的初值的初值x0 x0；(3)(3)、用、用x=g(x)x=g(x)求出求出x x的下一个值的下一个值x1x1；(4)(4)、再将、再将x1x1代入上述公式，求出代入上述公式，求出x x的下一个值的下一个值x2

5、x2；(5)(5)、如此继续下去，直到前后两次求出的、如此继续下去，直到前后两次求出的x x值满足要求；值满足要求；其中，其中，x0 称为初始近似根，称为初始近似根，xn称为称为n n次近似根，次近似根，g(x)称称为迭代函数。误差可用为迭代函数。误差可用|xn-xn-1|估计。估计。1.1.用普通迭代法求方程的近似实根用普通迭代法求方程的近似实根例例例例1 1：编写程序，用普通迭代法求方程：编写程序，用普通迭代法求方程：编写程序，用普通迭代法求方程：编写程序，用普通迭代法求方程f(x)=x+sin(1.2x)-2.15=0f(x)=x+sin(1.2x)-2.15=0在区间在区间在区间在区间

6、00，55上的近似实根。迭代初值自选，精确到上的近似实根。迭代初值自选，精确到上的近似实根。迭代初值自选，精确到上的近似实根。迭代初值自选，精确到0.00010.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.2

7、x)迭代函数迭代函数迭代函数迭代函数g(x)g(x)此程序可作为普通迭代法求方程近此程序可作为普通迭代法求方程近此程序可作为普通迭代法求方程近此程序可作为普通迭代法求方程近似实根的通用模板，只需更改：似实根的通用模板，只需更改：似实根的通用模板，只需更改：似实根的通用模板，只需更改：（1 1）迭代初值；）迭代初值；）迭代初值；）迭代初值；（2 2）迭代函数；）迭代函数；）迭代函数；）迭代函数；（3 3）与具体方程相关的提示信息。）与具体方程相关的提示信息。）与具体方程相关的提示信息。）与具体方程相关的提示信息。2.2.用二分法求方程的近似实根用二分法求方程的近似实根先找到区间先找到区间(a,b

8、)，使得，使得f(a)，f(b)异号，异号，说明在区间说明在区间(a,b)内一定有实根：内一定有实根：1.(1)求求f(a+b)/2)。如果。如果f(a+b)/2)=0，2.则则(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，转

9、步骤，转步骤(1)继续计算。继续计算。xyaby=f(x)(a+b)/2f(b)f(a)f(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(“方程可能无实方程可能无实数根！数根！”);els

10、e /*求近似实根求近似实根*/do ab=(a+b)/2 fab=2*ab+sin(ab)-2.15 ;if (fa*fab=1e-4);printf(“方程的近似实根为方程的近似实根为:%.4fn,ab);2.2.用二分法求方程的近似实根用二分法求方程的近似实根xyy=f(x)r3.3.用用牛顿切线法牛顿切线法求求方程的近似实根方程的近似实根xn+1=xnf(xn)/f(xn)，是，是r r的的n+1n+1次近似值，称为牛顿迭代公式次近似值，称为牛顿迭代公式(x0,f(x0)x0 x1(x1,f(x1)x2又称又称NewtonNewton迭代法。迭代法。其基本思路：其基本思路：u设设r是是

11、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的一次近似值。的一次近似值。u过点（过点（x1,f(x1)）做曲线）做曲线y=f(x)的切线，并求该切线与的切线，并求该切线与x轴轴交点的横坐标交点的横坐标 x2=x1-f(x1)/f(x1)，称，称x2为为r的二次近似值。的二次近似值。重复以上过程，得重复以上过程，得r的近似值序列。的近似值序列。3

12、.3.用用牛顿切线法牛顿切线法求求方程的近似实根方程的近似实根例例3：编写程序，用：编写程序，用Newton迭代法求方程迭代法求方程f(x)=2x+cosx-2.6=0在区间在区间0，4上的近似实根上的近似实根r，迭代初值自选，精确到，迭代初值自选，精确到0.0001。#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)、直

13、线、直线x=a、直线、直线x=b与与x轴围成的区域的面积轴围成的区域的面积(图中阴形部分图中阴形部分)。y=f(x)xyx=ax=bba4.4.用用矩形法矩形法求定积分近似值求定积分近似值矩形法的基本思想：矩形法的基本思想：求定积分求定积分l把区间把区间a,b平均分成平均分成n个小区间，以每个小区间左端点的函数值为宽、个小区间，以每个小区间左端点的函数值为宽、小区间长度为高作矩形，然后把这小区间长度为高作矩形，然后把这n个小矩形的面积相加，即为所求的个小矩形的面积相加，即为所求的定积分的近似值。定积分的近似值。l显然，小区间数显然，小区间数n越大，求得的定积分的近似求值的精度也越高。越大，求得

14、的定积分的近似求值的精度也越高。的近似值yxaby=f(x)y=f(x)hh=(b-a)/nai=a+(i-1)*h(ai,f(ai)例例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)

15、/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.4.用用矩形法矩形法求定积分近似值求定积分近似值5.5.用用梯形法梯形法求定积分近似值求定积分近似值梯形法的基本思想：梯形法的基本思想：求定积分求定积分l把区间把区间a,b平均分成平均分成n个小区间，以每个小区间左端点的函数值为上个小区间，以每个小区间左端点的函数值为上底、右端点的函数值为下底、小区间长度为高作梯形，然后把这底、右端点的函数值为下底、小区间长度为高作梯形，然后把这n个小个小梯形的面积相加，即为

16、所求的定积分的近似值。梯形的面积相加，即为所求的定积分的近似值。l显然，小区间数显然，小区间数n越大，求得的定积分的近似求值的精度也越高。并且越大，求得的定积分的近似求值的精度也越高。并且可以看出，对于同样的小区间数，梯形法的精度比矩形法高。可以看出，对于同样的小区间数，梯形法的精度比矩形法高。的近似值h=(b-a)/nai=a+(i-1)*hyxaby=f(x)y=f(x)h(ai,f(ai)例例5：用梯形法求一元函数：用梯形法求一元函数f(x)=e(-x2)在区间在区间0,1上的上的积分近似值积分近似值S，保留，保留4位小数。位小数。(区间数区间数n=10，此参数，此参数不能改动否则影响答

17、案，其中不能改动否则影响答案，其中e为自然对数的底，为自然对数的底，表表示幂运算示幂运算)5.5.用用梯形法梯形法求定积分近似值求定积分近似值即，求定积分即，求定积分的近似值。的近似值。C语言库函数中求语言库函数中求ex的函数是的函数是double exp(double x)有关有关C语言更多的库函数，请参考语言更多的库函数，请参考P351附录附录#include#includemain()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.5.用用梯形法梯形法求定积分近似值求定积分近似值求 的近似值课堂小结课堂小结熟练掌握本节所讲的所有算法，熟练掌握本节所讲的所有算法，能够举一反三。能够举一反三。