第8讲循环结构经典算法二.ppt

第八讲 循环结构的经典算法二程序设计举例
1


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


本节主要内容
2

迭代法也称辗转法，是一种不断用变量的旧值递推新值的过程。
例如：上一讲的【例4】：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
……
0
1
1
2
3
5
8
……
an
……
3

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

普通迭代法的基本思想：
求一元非线性方程f(x)=0 的实根。
(1)、将方程f(x)=0化为它的等价方程：x=g(x) ,
(2)、设定一个x的初值x0；
(3)、用x=g(x)求出x的下一个值x1；
(4)、再将x1代入上述公式，求出x的下一个值x2；
(5)、如此继续下去，直到前后两次求出的x值满足要求；
其中，x0 称为初始近似根，xn称为n次近似根，g (x) 称为迭代函数。误差可用|xn-xn-1|估计。
5

例1：编写程序，用普通迭代法求方程f(x)=x+sin()-=0在区间[0，5]上的近似实根。迭代初值自选，。
#include <>
#include <>
main()
{
double x0 , x1;
x1=; /* 初始近似根 */
do
{
x0=x1;
x1=-sin(*x0); /* 迭代公式 */
}
while(fabs(x1-x0)>=1e-4);
printf(“方程x+sin()-=0的近似根:”);
printf("%.4f\n",x1);
}
以上方程的等价形式：x=-sin()
迭代函数g(x)
此程序可作为普通迭代法求方程近似实根的通用模板，只需更改：
（1）迭代初值；
（2）迭代函数；
（3）与具体方程相关的提示信息。
6

先找到区间(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)继续计算。
x
y
a
b
y=f(x)
(a+b)/2
f(b)
f(a)
f((a+b)/2)
二分法的基本思想：
7
例2：编写程序，用二分法求一元非线性方程f(x)=2x+sinx-=0
在区间 (0，5)上的近似实根r，。
#include <>
#include <>
main()
{ float a=0,b=5,ab, fa, fb, fab;
fa=2*a+sin(a)-;
fb=2*a+sin(b)-;
if( fa * fb > 0 )
printf(“方程可能无实数根！”);
else
{