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

《八讲循环结构的经典算法之.ppt》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、第八讲循环结构的经典算法之二程序设计举例教学重点：1.用普通迭代法求方程的近似实根2.用二分法求一元非线性方程在某区间上的近似实根3.用牛顿切线法（又叫Newton迭代法）求方程在某区间的近似实根4.用矩形法求一元函数在某区间上的积分近似值5.用梯形法求一元函数在某区间上的积分近似值6.加密、解密算法0.迭代法的一般含义迭代法也称辗转法，是一种不断用变量的旧值递推新值的过程。例如：上一讲的【例5】：Fibonacci（斐波纳契数列）a0=0a1=1a2=a0+a1a3=a1+a2a4+=a2+a3a5+=a3+a4a6+=a4+a5……an=an-2+an-1……从前有一对长寿兔子，

2、从出生后第3个月起每个月都生一对兔子。新生的小兔子长到第3个月后每个月又都生一对兔子，这样一代一代生下去，假设所有兔子都不死，求兔子增长数量的数列（即每个月的兔子总对数）。0112358……an……0.迭代法的一般含义迭代法也称辗转法，是一种不断用变量的旧值递推新值的过程。再如：猴子吃桃猴子第一天摘下若干桃子，当即吃了一半，还不过瘾，又多吃了一个。第二天猴子又将剩下的桃子吃掉一半，又多吃一个。以后每天都吃掉前一天剩下的一半零一个。到第10天再想吃时，发现只剩下一个桃子。问猴子第一天共摘了多少桃子。a1a2a3a4a5a6a7a8a9a101a9=2(a10+1)4a8=2(a9+1)1

3、0a7=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)15340.迭代法的一般含义再如：编程求a+aa+aaa+…+aa…a(n个a)的值。其中a是一个从1到9之间的一个数字。要求a和n从键盘输入。提示：累加项为term=term*10+a,term初值为0。考虑序列：a0=0a1=a=a0*10+aa2=aa=a1*10+aa3=aaa=a*100+a*10+a=10*(a*10+a)+a=a2*10+aa4=aaaa=a3*10+a……an=an-1*10+a本题等

4、价于求迭代序列的前n项和迭代法也称辗转法，是一种不断用变量的旧值递推新值的过程。(其中a0=0,ai=ai-1*10+a)0.迭代法的一般含义再如求1!+2!+3!+4!+…+10!考虑序列：a1=1!=1a2=2*a1a3=3*a2a4=4*a3…….an=n*an-1迭代法也称辗转法，是一种不断用变量的旧值递推新值的过程。(其中a1=1,ai=i*ai-1)1.用普通迭代法求方程的近似实根普通迭代法的基本思想：设f(x)是实函数,求方程f(x)=0的实根。首先将f(x)=0化为它的等价方程x=g(x);再从某一实数x0出发，求序列｛xn｝,其中：xn-1=g(xn)n=0，1，2，

5、…如果序列｛xn｝有极限，不访设xn→a,当n→∝。对上式两端取极限，就有a=g(a),即f(a)=0也就是说，a是方程f(x)=0的一个实根。其中，x0称为初始近似根，xn称为n次近似根，g(x)称为迭代函数。误差可用

6、xn-xn-1

7、估计。注意：g(x)必须满足一定的条件，才能保证序列{xn}在某一区间上的收敛性。这个问题已超出本课讨论的范围。1.用普通迭代法求方程的近似实根例1：编写程序，用普通迭代法求方程f(x)=x+sin(1.2x)-2.15=0在区间[0，5]上的近似实根。迭代初值自选，精确到0.0001。#include#include

8、main(){doublex0,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("%.4f",x0);}以上方程的等价形式：x=2.15-sin(1.2x)迭代函数g(x)此程序可作为普通迭代法求方程近似实根的通用模板，只需更改：（1）迭代初值；（2）迭代函数；（3）与具体方程相关的提示信息。2.用二分法求方程的近似实根二分法的基本思想：设f(x)是连续、实函数,求方程f(x)=0的

9、实根。先找到区间(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，