第八讲+循环结构的经典算法之二教材课程.ppt

第八讲+循环结构的经典算法之二教材课程.ppt第八讲循环结构的经典算法之二程序设计举例教学重点:(又叫Newton迭代法)、,是一种不断用变量的旧值递推新值的过程。例如:上一讲的【例5】:i(斐波纳契数列)a0=0a1=1a2=a0+a1a3=a1+a2a4+=a2+a3a5+=a3+a4a6+=a4+a5……an=an-2+an-1……从前有一对长寿兔子,从出生后第3个月起每个月都生一对兔子。新生的小兔子长到第3个月后每个月又都生一对兔子,这样一代一代生下去,假设所有兔子都不死,求兔子增长数量的数列(即每个月的兔子总对数)。0112358……an……:编程求a+aa+aaa+…+aa…a(n个a)的值。其中a是一个从1到9之间的一个数字。要求a和n从键盘输入。提示:累加项为term=term*10+a,term初值为0。 考虑序列: a0=0 a1=a=a0*10+aa2=aa=a1*10+a a3=aaa=a*100+a*10+a=10*(a*10+a)+a=a2*10+a a4=aaaa=a3*10+a ……an=an-1*10+a本题等价于求迭代序列的前n项和迭代法也称辗转法,是一种不断用变量的旧值递推新值的过程。(其中a0=0,ai=ai-1*10+a)!+2!+3!+4!+…+10!考虑序列:a1=1!=1a2=2*a1a3=3*a2a4=4*a3…….an=n*an-1迭代法也称辗转法,是一种不断用变量的旧值递推新值的过程。(其中a1=1,ai=i*ai-1):设f(x)是实函数,求方程f(x)=0的实根。首先将f(x)=0化为它的等价方程x=g(x);再从某一实数x0出发,求序列{xn},其中:           xn-1=g(xn)n=0,1,2,…如果序列{xn}有极限,不访设xn→a,当n→∝。对上式两端取极限,就有a=g(a),即f(a)=0也就是说,a是方程f(x)=0的一个实根。其中,x0称为初始近似根,xn称为n次近似根,g(x)称为迭代函数。误差可用|xn-xn-1|估计。注意:g(x)必须满足一定的条件,才能保证序列{xn}在某一区间上的收敛性。这个问题已超出本课讨论的范围。:编写程序,用普通迭代法求方程f(x)=x+sin()-=0在区间[0,5]上的近似实根。迭代初值自选,。#include<>#include<>main(){ doublex0,x1; x1=;/*初始近似根*/ do { x0=x1; x1=-sin(*x0);/*迭代公式*/ } while(fabs(x1-x0)>=1e-4); printf(“方程x+sin()-=0的近似根:”); printf("%.4f\n",x0);}以上方程的等价形式:x=-sin()迭代函数g(x)此程序可作为普通迭代法求方程近似实根的通用模板,只需更改:(1)迭代初值;(2)迭代函数;(3)与具体方程相关的提示信息。:设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)继续计算。利用这种方法,每次可以把f(x)的零点所在小区间收缩一半,如此下去,区间的两个端点将逐步逼近函数的零点。此法称为“二分法”。实际操作时,当f((a+b)/2)小于要求的误差时,则停止计算,此时(a+b)/2称方程的一个近似实根。xyaby=f(x)a+bf(b)f(a)f((a+b)/2)例2:编写程序,用二分法求一元非线性方程f(x)=2x+sinx-=0在区间(0,5)上的近似实根r,。#include<>#include<>main(){floata=