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

第八讲第八讲循环结构的经典算法二循环结构的经典算法二程序设计举例程序设计举例 (又叫 Newton 迭代法) 求方程在某区间的近似实根 ,是一种不断用变量的旧值递推新值的过程。例如:上一讲的【例4】:i (斐波纳契数列) a 0 = 0 a 1 = 1 a 2 =a 0 +a 1a 3 =a 1 +a 2a 4 +=a 2 +a 3a 5 +=a 3 +a 4a 6 +=a 4 +a 5…… an=a n-2 +a n-1 …… 0112358…… a n…… ,是一种不断用变量的旧值递推新值的过程。再如:猴子吃桃猴子第一天摘下若干桃子,当即吃了一半,还不过瘾,又多吃了一个。第二天猴子又将剩下的桃子吃掉一半,又多吃一个。以后每天都吃掉前一天剩下的一半零一个。到第 10 天再想吃时,发现只剩下一个桃子。问猴子第一天共摘了多少桃子。 1 a 10a 9a 8a 7a 6a 5a 4a 3a 2a 1a 9 =2(a 10 +1) 4 a 8 =2(a 9 +1) 10 a 7 =2(a 8 +1) 22 a 6 =2(a 7 +1) 46 a 5 =2(a 6 +1) 94 a 4 =2(a 5 +1) 190 a 3 =2(a 4 +1) 382 a 2 =2(a 3 +1) 766 a 1 =2(a 2 +1) 1534 : 普通迭代法的基本思想: 求一元非线性方程 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值满足要求; 其中, x 0称为初始近似根, x n称为 n次近似根, g (x) 称为迭代函数。误差可用|x n -x n-1 |估计。 1. 1:编写程序,用普通迭代法求方程:编写程序,用普通迭代法求方程 f(x f(x )=x+sin()-=0 )=x+sin()-=0 在区间在区间[0 [0, , 5] 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 g(x ) )此程序可作为普通迭代法求方程近此程序可作为普通迭代法求方程近似实根的通用模板,只需更改: 似实根的通用模板,只需更改: ( (1 1)迭代初值; )迭代初值; ( (2 2)迭代函数; )迭代函数; ( (3 3)与具体方程相关的提示信息。)与具体方程相关的提示信息。 2. ( 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 yab y= f(x ) (a+b)/2 f(b ) f(a ) f((a+b)/2) 二分法的基本思想: 例2:编写程序,用二分法求一元非线性方程 f(x )=2x+sinx-=0 在区间(0,