《循环结构经典算法》PPT课件.ppt

第八讲 循环结构的经典算法二 程序设计举例,1.用普通迭代法求方程的近似实根 2.用二分法求一元非线性方程在某区间上的近似实根 3.用牛顿切线法（又叫Newton迭代法）求方程在某区间 的近似实根 4.用矩形法求一元函数在某区间上的积分近似值 5.用梯形法求一元函数在某区间上的积分近似值,本节主要内容,0.迭代法的一般含义,迭代法也称辗转法，是一种不断用变量的旧值递推新值的过程。,例如：上一讲的【例4】：Fibonacci（斐波纳契数列）,a0= 0 a1= 1 a2=a0+a1 a3=a1+a2 a4+=a2+a3 a5+=a3+a4 a6+=a4+a5 an=an-2+an-1 ,0 1 1 2 3 5 8 an ,0.迭代法的一般含义,迭代法也称辗转法，是一种不断用变量的旧值递推新值的过程。,再如：猴子吃桃 猴子第一天摘下若干桃子，当即吃了一半，还不过瘾，又多吃了一个。第二天猴子又将剩下的桃子吃掉一半，又多吃一个。以后每天都吃掉前一天剩下的一半零一个。到第10天再想吃时，发现只剩下一个桃子。问猴子第一天共摘了多少桃子。,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值满足要求；,其中，x0 称为初始近似根，xn称为n次近似根，g (x) 称为迭代函数。误差可用|xn-xn-1|估计。,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）与具体方程相关的提示信息。,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)继续计算。,二分法的基本思想：,例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. 用牛顿切线法求方程的近似实根,xn+1=xnf(xn)/f(xn)，是r的n+1次近似值，称为牛顿迭代公式,又称Newton迭代法。 其基本思路：,设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的近似值序列。,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); ,定积分概念回顾,求定积分,值，等价于求曲线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)/n ai=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)/n ai=a+(i-1)*h,例5：用梯形法求一元函数f(x)=e(-x2) 在区间0,1上的积分近似值S，保留4位小数。(区间数n=10，此参数不能改动否则影响答案，其中e为自然对数的底，表示幂运算),5.用梯形法求定积分近似值,C语言库函数中求ex的函数是double exp(double x) 有关C语言更多的库函数，请参考P351附录,#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(