循环结构的经典算法之二

第八讲 循环结构的经典算法之二程序设计举例,教学重点：1.用普通迭代法求一元非线性方程的近似实根r2.用二分法求一元非线性方程在某区间上的近似实根r3.用牛顿切线法（又叫Newton迭代法）求一元非线性方程 在某区间上的近似实根r4.用矩形法求一元函数在某区间上的积分近似值S5.用梯形法求一元函数在某区间上的积分近似值S6.加密、解密算法,所谓非线性方程，就是因变量与自变量之间的关系不是线性的关系，这类方程很多，例如平方关系、对数关系、指数关系、三角函数关系等等。,5.9 循环应用举例,1.用普通迭代法求方程的近似实根r,5.9 循环应用举例,1.用普通迭代法求方程的近似实根r,普通迭代法的基本思想：求一元非线性方程f(x)=0 的实根。(1)、将方程f(x)=0化为它的等价方程：x=g(x) , g (x) 称为迭代函数。(2)、设定一个x的初值x0；(3)、用x=g(x)求出x的下一个值x1； (4)、再将x1代入上述公式，求出x的下一个值x2；(5)、如此继续下去，直到前后两次求出的x值满足要求；,迭代法也称辗转法，是一种不断用变量的旧值递推新值的过程。,5.9 循环应用举例,1.用普通迭代法求方程的近似实根r例1：编写程序，用普通迭代法求方程f(x)=x+sin(1.2x)-2.15=0在区间0，5上的近似实根r，迭代初值自选，精确到0.0001。提示：必须把方程f(x)=0化成其等价方程x=g(x),#include #include main()double x,x0;x0=2.5; /*迭代初值自选*/dox=x0;x0=2.15-sin(1.2*x); /*转化后的等价方程x=g(x) */while(fabs(x-x0)=1e-4);printf(%.4fn,x0);,5.9 循环应用举例,2.用二分法求一元非线性方程在某区间上的近似实根r原理：对于方程 f(x)=0，解方程即要求f(x)的所有零点，(1) 先输入a、b的值，求f(a)和f(b)；(2) 如果f(a)和f(b)同号，说明在区间a,b内无实根，返回步骤(1),重新输入a和b的值；如果f(a)和f(b)异号，说明在区间a,b内一定有一个零点，即实根。 (3) 求f(a+b)/2，现在假设f(a)0,（a0，则在区间(a,(a+b)/2)内有零点，令b = (a+b)/2， 从(3)开始继续使用中点函数值判断。这样就可以不断接近零点,通过每次把f(x)的零点所在小区间收缩一半的方法，使区间的两个端点逐步迫近函数的零点，以求得零点的近似值，这种方法叫做二分法。,例2：编写程序，用二分法求一元非线性方程f(x)=2x+sinx-2.15=0 在区间 (0，5)上的近似实根r，精确到0.0001。,#include #include main() float a,b,x0,f1,f2,f0; do scanf(%f,%f,do x0=(a+b)/2; f0=2*x0+sin(x0)-2.15 ; if (f1*f0=1e-4) ; printf(%.4fn,x0); ,5.9 循环应用举例,3. 用牛顿切线法求方程在某区间的近似实根r Newton切线法又叫Newton迭代法。此方法使用函数f(x)的泰勒级数的前面几项来寻找方程f(x) = 0的根。,5.9 循环应用举例,3. 用牛顿切线法求方程在某区间的近似实根r先任意设定一个与真实的根r接近的值x0，作为第一次近似根，由x0求出f(x0)，过点（x0,f(x0)）做 f(x)的切线，切线交x轴于x1 ；把x1作为第二次近似根，再由x1求出f(x1) ，过点（x1,f(x1)）做 f(x)的切线，切线交x轴于x2；把x2作为第三次近似根，再由x2求出f(x2)，再做切线。如此继续下去，直到满足要求，得真实的根r的近似值。从图中可以看出：切线的斜率 f (x(n)= f(x(n)/ (x(n)-x(n+1)因此得：x(n+1)=x(n)f(x(n)/f(x(n)，称为牛顿迭代公式。,例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,f,f1;x=2; /*迭代初值自选*/dox0=x;f=2*x0+cos(x0)-2.6;f1=2-sin(x0);x=x0-f/f1;while(fabs(x-x0)=1e-4);printf(%.4fn,x);,5.9 循环应用举例,f1代表f(x),x0代表前一次的近似根，x代表后一次的近似根。求出一个x后，把它的值赋给x0，然后用x0求下一个x。,5.9 循环应用举例,求定积分的近似值常有矩形法与梯形法，其实质都是面积求和。矩形法是把所要求的面积垂直x轴分成n个小矩形，然后把这n个小矩形的面积相加，即为所求的定积分的值。梯形法是把所要求的面积垂直分成n个小梯形，然后作面积求和。这两种近似求值的精度随分割个数n的增加而增加，对于相同的 n个数，相对来说，梯形法的精度比矩形法的要高一些。,初始算法：初始化积分区间（a，b），如果把积分区间划分为 100个格，则每个区间的宽度h=fabs(a-b)/100；,4.用矩形法求一元函数在某区间上的积分近似值s,5.9 循环应用举例,【例5_34】 ：编写程序，用矩形法求一元函数f(x)=x*x在区间0，1上的积分近似值S。（课本P103）,5.9 循环应用举例,#includemain() int n,k;float a,b,h,f0,s=0,s1,x;scanf(%d,法一,例4：编写程序，用矩形法求一元函数f(x)=(4-(sinx)2)(1/2) 在区间0，3.1416/6上的积分近似值S，保留4位小数（小区间数n=15，此参数不能改动，否则影响答案， 其中表示幂运算 ）。,#include #include main()double x,y=0,h,a=0,b=3.1416/6,s;int i,n=15;h=fabs(a-b)/n;for(i=1;i=n;i+) x=a+(i-1)*h; y=y+sqrt(4-sin(x)*sin(x);s=y*h;printf(%.4fn ,s);,5.9 循环应用举例,法二,5.9 循环应用举例,5.用梯形法求一元函数在某区间上的积分近似值S原理： 求一个函数f(x)在a,b上的定积分，其几何意义是求f(x)曲线和直线x=a,y=0,x=b所围成的曲边梯形面积。为了近似求出此面积，可将a,b区间分成若各个小区间，每个区间的宽度为(b-a)/n,n为区间个数。近似求出每个小的曲边梯形面积，然后将n个小面积加起来，就近似的到总的面积。即定积分的近似值，当n愈大（即区间分的愈小），近似程度愈高。,#