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

第八讲 循环结构的经典算法之二程序设计举例
1
编辑ppt
教学重点：


（又叫Newton迭代法）求方程在某区间
的近似实根


、解密算法
2
编辑ppt

迭代法也称辗转法，是一种不断用变量的旧值递推新值的过程。
例如：上一讲的【例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
……
3
编辑ppt

迭代法也称辗转法，是一种不断用变量的旧值递推新值的过程。
再如：猴子吃桃
猴子第一天摘下若干桃子，当即吃了一半，还不过瘾，又多吃了一个。第二天猴子又将剩下的桃子吃掉一半，又多吃一个。以后每天都吃掉前一天剩下的一半零一个。到第10天再想吃时，发现只剩下一个桃子。问猴子第一天共摘了多少桃子。
a1
a2
a3
a4
a5
a6
a7
a8
a9
a10
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
4
编辑ppt

再如：编程求a+aa+aaa+ …+ aa…a(n个a)的值。其中a是一个从1到9之间的一个数字。要求a和n从键盘输入。
提示：累加项为term =term*10+a, term初值为0。
考虑序列：
a0 = 0
a1 = a = a0*10 + a
a2 = 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)
5
编辑ppt

再如 求1!+2!+3!+4!+…+10!
考虑序列：
a1=1! = 1
a2 = 2 * a1
a3 = 3 * a2
a4 = 4 * a3
…….
an = n * an-1
迭代法也称辗转法，是一种不断用变量的旧值递推新值的过程。
( 其中 a1=1, ai=i * ai-1 )
6
编辑ppt

普通迭代法的基本思想：
设 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}在某一区间上的收敛性。这个问题已超出本课讨论的范围。
7
编辑ppt

例1：编写程序，用普通迭代法求方程f(x)=x+sin()-=0在区间[0，5]上的近似实根。迭代初值自选，。
#include <>
#include <>
main()
{
double x0 , x1;
x1=; /* 初始近似根 */
do
{
x0=x1;