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

第八讲 循环结构的经典算法之二 程序设计举例 教学重点： 1.用普通迭代法求方程的近似实根 2.用二分法求一元非线性方程在某区间上的近似实根 3.用牛顿切线法（又叫Newton迭代法）求方程在某区间 的近似实根 4.用矩形法求一元函数在某区间上的积分近似值 5.用梯形法求一元函数在某区间上的积分近似值 6.加密、解密算法 0.迭代法的一般含义 迭代法也称辗转法，是一种不断用变量的旧值递推新值的过程 。 例如：上一讲的【例5】：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 从前有一对长寿兔子，从出 生后第3个月起每个月都生一对 兔子。新生的小兔子长到第3个 月后每个月又都生一对兔子， 这样一代一代生下去，假设所 有兔子都不死，求兔子增长数 量的数列（即每个月的兔子总 对数）。 0 1 1 2 3 5 8 an 0.迭代法的一般含义 迭代法也称辗转法，是一种不断用变量的旧值递推新值的过程 。 再如：猴子吃桃 猴子第一天摘下若干桃子，当即吃了一半，还不过瘾，又多吃了一个 。第二天猴子又将剩下的桃子吃掉一半，又多吃一个。以后每天都吃掉前 一天剩下的一半零一个。到第10天再想吃时，发现只剩下一个桃子。问猴 子第一天共摘了多少桃子。 a1a2a3a4a5a6a7a8a9a10 1 a9=2(a10+1) 4 a8=2(a9+1) 10 a7=2(a8+1) 22 a6=2(a7+1) 46 a5=2(a6+1) 94 a4=2(a5+1) 190 a3=2(a4+1) 382 a2=2(a3+1) 766 a1=2(a2+1) 1534 0.迭代法的一般含义 再如：编程求再如：编程求a+aa+aaaa+aa+aaa+ + + + aaaaa(na(n个个a)a)的值。其中的值。其中a a是一个从是一个从1 1到到9 9 之间的一个数字。要求之间的一个数字。要求a a和和n n从键盘输入。从键盘输入。 提示：累加项为提示：累加项为term =term =termterm*10+a, term*10+a, term初值为初值为0 0。 考虑序列：考虑序列： a a0 0 = 0 = 0 a a1 1 = a = = a = a a 0 0 *10 + a*10 + a a a 2 2 = = aaaa = = a a 1 1 *10 + a*10 + a a a3 3 = = aaaaaa =a*100+ a*10 + a = 10*(a*10 + a) + a = =a*100+ a*10 + a = 10*(a*10 + a) + a = a a 2 2 *10 + a*10 + a a a4 4 = = aaaaaaaa = = a a 3 3 *10 + a*10 + a a a n n = = a an-1 n-1*10 + a *10 + a 本题等价于求迭代序列的前本题等价于求迭代序列的前n n项和项和 迭代法也称辗转法，是一种不断用变量的旧值递推新值的过程 。 ( (其中其中a a 0 0 =0, =0, a a i i =a=ai-1 i-1*10 *10 +a)+a) 0.迭代法的一般含义 再如再如 求求1!+2!+3!+4!+10!1!+2!+3!+4!+10! 考虑序列：考虑序列： a1=1! = 1a1=1! = 1 a a 2 2 = 2 * a = 2 * a 1 1 a a 3 3 = 3 * a = 3 * a 2 2 a a4 4 = 4 * a = 4 * a 3 3 . a a n n = n * a = n * an-1 n-1 迭代法也称辗转法，是一种不断用变量的旧值递推新值的过程 。 ( ( 其中其中 a a 1 1 =1, =1, a a i i =i * a=i * ai-1 i-1 ) ) 1.用普通迭代法求方程的近似实根 普通迭代法的基本思想： 设 f(x) 是实函数, 求方程f(x)=0 的实根。 u 首先将f(x)=0化为它的等价方程x=g(x); u 再从某一实数 x0 出发，求序列xn,其中： xn-1=g(xn) n=0，1，2， u 如果序列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 1：编写程序，用普通迭代法求方程：编写程序，用普通迭代法求方程f(xf(x)=x+sin(1.2x)-2.15=0)=x+sin(1.2x)-2.15=0在区间在区间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“,x0); 以上方程的等价形式：x=2.15-sin(1.2x) 迭代函数迭代函数g(xg(x) ) 此程序可作为普通迭代法求方程近此程序可作为普通迭代法求方程近 似实根的通用模板，只需更改：似实根的通用模板，只需更改： （1 1）迭代初值；）迭代初值； （2 2）迭代函数；）迭代函数； （3 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)继续计算。 u利用这种方法，每次可以把f(x)的零点所在小区间收缩一半，如此下去，区间的 两个端点将逐步逼近函数的零点。此法称为“二分法”。 u实际操作时，当f(a+b)/2)小于要求的误差时，则停止计算，此时(a+b)/2称方 程的一个近似实根。 x y ab y=f(x) a+b f(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(“方程可能无实数根！”); else /* 求近似实根 */ /* 求近似实根 */ do ab=(a+b)/2 fab=2*ab+sin(ab)-2.15 ; if (fa * fab =1e-4) ; printf(“方程的近似实根为:%.4fn“,ab); 2.用二分法求方程的近似实根 x y y=f(x) r 3. 用牛顿切线法求方程的近似实根 又称Newton迭代法。 其基本思路： 假设f(x)是连续、光滑、实函数，求f(x)=0的实根。 u 设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的一次近似值。 u 过点（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次近似值，又称为牛顿迭代公式。 (x0,f(x0) x0x1 (x1,f(x1) x2 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; 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.用矩形法求定积分近似值 矩形法的基本思想： 求定积分 l 把区间a,b平均分成n个小区间，以每个小区间左端点的函数值为宽 、小区间长度为高作矩形，然后把这n个小矩形的面积相加，即为所 求的定积分的近似值。 l 显然，小区间数n越大，求得的定积分的近似求值的精度也越高。 的近似值 y xab y=y=f(xf(x) ) h h=(b-a)/n ai=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 )/n; for(i = 1; i #include