循环结构的经典算法之.ppt
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_05.gif)
《循环结构的经典算法之.ppt》由会员分享,可在线阅读,更多相关《循环结构的经典算法之.ppt(21页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、第八讲第八讲 循环结构的经典算法之二循环结构的经典算法之二程序设计举例程序设计举例 教学重点:教学重点:1.1.用用普通迭代法普通迭代法求方程的近似实根求方程的近似实根2.2.用用二分法二分法求一元非线性方程在某区间上的近似实根求一元非线性方程在某区间上的近似实根3.3.用用牛顿切线法(又叫牛顿切线法(又叫NewtonNewton迭代法)迭代法)求方程在某区间求方程在某区间 的近似实根的近似实根4.4.用用矩形法矩形法求一元函数在某区间上的积分近似值求一元函数在某区间上的积分近似值5.5.用用梯形法梯形法求一元函数在某区间上的积分近似值求一元函数在某区间上的积分近似值6.6.加密、解密算法加密
2、、解密算法0.迭代法的一般含义迭代法迭代法也称辗转法,是一种不断用变量的旧值递推新值的过程。也称辗转法,是一种不断用变量的旧值递推新值的过程。例如:上一讲的【例例如:上一讲的【例5 5】:FibonacciFibonacci(斐波纳契数列)(斐波纳契数列)a0=0a1=1a2=a0+a1a3=a1+a2a4+=a2+a3a5+=a3+a4a6+=a4+a5an=an-2+an-1 从前有一对长寿兔子,从出从前有一对长寿兔子,从出生后第生后第3个月起每个月都生一对个月起每个月都生一对兔子。新生的小兔子长到第兔子。新生的小兔子长到第3个个月后每个月又都生一对兔子,月后每个月又都生一对兔子,这样一代
3、一代生下去,假设所这样一代一代生下去,假设所有兔子都不死,求兔子增长数有兔子都不死,求兔子增长数量的数列(即每个月的兔子总量的数列(即每个月的兔子总对数)。对数)。0112358an0.迭代法的一般含义迭代法迭代法也称辗转法,是一种不断用变量的旧值递推新值的过程。也称辗转法,是一种不断用变量的旧值递推新值的过程。再如:猴子吃桃再如:猴子吃桃 猴子第一天摘下若干桃子,当即吃了一半,还不过瘾,又多吃了一个。猴子第一天摘下若干桃子,当即吃了一半,还不过瘾,又多吃了一个。第二天猴子又将剩下的桃子吃掉一半,又多吃一个。以后每天都吃掉前一第二天猴子又将剩下的桃子吃掉一半,又多吃一个。以后每天都吃掉前一天剩
4、下的一半零一个。到第天剩下的一半零一个。到第10天再想吃时,发现只剩下一个桃子。问猴子天再想吃时,发现只剩下一个桃子。问猴子第一天共摘了多少桃子。第一天共摘了多少桃子。a1a2a3a4a5a6a7a8a9a101a9=2(a10+1)4a8=2(a9+1)10a7=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+aaa(na+aa+aaa+aaa(n个个个个a)a)的值。其中的值。其中的
5、值。其中的值。其中a a是一个从是一个从是一个从是一个从1 1到到到到9 9之之之之间的一个数字。要求间的一个数字。要求间的一个数字。要求间的一个数字。要求a a和和和和n n从键盘输入。从键盘输入。从键盘输入。从键盘输入。提示:累加项为提示:累加项为提示:累加项为提示:累加项为term=term*10+a,termterm=term*10+a,term初值为初值为初值为初值为0 0。考虑序列:考虑序列:考虑序列:考虑序列:a a0 0 =0 =0a a1 1 =a =a =a a0 0*10 +a*10 +a a a2 2 =aa=aa=a a1 1*10 +a*10 +a a a3 3 =
6、aaa=a*100+a*10+a=10*(a*10+a)+a =aaa=a*100+a*10+a=10*(a*10+a)+a =a a2 2*10+a*10+aa a4 4 =aaaa=aaaa=a a3 3*10+a*10+a a an n =a an-1n-1*10+a*10+a 本题等价于求迭代序列的前本题等价于求迭代序列的前本题等价于求迭代序列的前本题等价于求迭代序列的前n n项和项和项和项和 迭代法迭代法也称辗转法,是一种不断用变量的旧值递推新值的过程。也称辗转法,是一种不断用变量的旧值递推新值的过程。(其中其中其中其中a a0 0=0,a=0,ai i=a=ai-1i-1*10*1
7、0 +a)+a)0.迭代法的一般含义再如再如再如再如 求求求求1!+2!+3!+4!+10!1!+2!+3!+4!+10!考虑序列:考虑序列:考虑序列:考虑序列:a1=1!=1a1=1!=1a a2 2=2*a=2*a1 1a a3 3=3*a=3*a2 2a a4 4=4*a=4*a3 3.a an n=n*a=n*an-1n-1迭代法迭代法也称辗转法,是一种不断用变量的旧值递推新值的过程。也称辗转法,是一种不断用变量的旧值递推新值的过程。(其中其中其中其中 a a1 1=1,a=1,ai i=i*a=i*ai-1 i-1)1.1.用用普通迭代法普通迭代法求方程的近似实根求方程的近似实根普通
8、迭代法的基本思想:普通迭代法的基本思想:设设 f(x)是实函数是实函数,求方程求方程f(x)=0 的实根。的实根。u首先将首先将f(x)=0化为它的等价方程化为它的等价方程x=g(x);u再从某一实数再从某一实数 x x0 0 出发,求序列出发,求序列xn,其中:其中:xn-1=g(xn)n=0 n=0,1 1,2 2,u如果序列如果序列xn有极限,不访设有极限,不访设xna,当当n。对上式两端取极限,。对上式两端取极限,就有就有 a=g(a),即即 f(a)=0也就是说,也就是说,a是方程是方程f(x)=0的一个实根。的一个实根。其中,其中,x0 称为初始近似根,称为初始近似根,xn称为称为
9、n n次近似根,次近似根,g(x)称称为迭代函数。误差可用为迭代函数。误差可用|xn-xn-1|估计。估计。注意:g(x)必须满足一定的条件,才能保证序列xn在某一区间上的收敛性。这个问题已超出本课讨论的范围。1.1.用用普通迭代法普通迭代法求方程的近似实根求方程的近似实根例例例例1 1:编写程序,用普通迭代法求方程:编写程序,用普通迭代法求方程:编写程序,用普通迭代法求方程:编写程序,用普通迭代法求方程f(x)=x+sin(1.2x)-2.15=0f(x)=x+sin(1.2x)-2.15=0在区间在区间在区间在区间00,55上的近似实根。迭代初值自选,精确到上的近似实根。迭代初值自选,精确
10、到上的近似实根。迭代初值自选,精确到上的近似实根。迭代初值自选,精确到0.00010.0001。#include#include main()double x0,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(%.4fn,x0);以上方程的等价形式以上方程的等价形式:x=2.15-sin(1.2x)迭代函数迭代函数迭代函数迭代函数g(x)g(x)此程序可作为普通迭代法求
11、方程近此程序可作为普通迭代法求方程近此程序可作为普通迭代法求方程近此程序可作为普通迭代法求方程近似实根的通用模板,只需更改:似实根的通用模板,只需更改:似实根的通用模板,只需更改:似实根的通用模板,只需更改:(1 1)迭代初值;)迭代初值;)迭代初值;)迭代初值;(2 2)迭代函数;)迭代函数;)迭代函数;)迭代函数;(3 3)与具体方程相关的提示信息。)与具体方程相关的提示信息。)与具体方程相关的提示信息。)与具体方程相关的提示信息。2.2.用二分法求方程的近似实根用二分法求方程的近似实根二分法的基本思想:二分法的基本思想:设设 f(x)是连续、实函数是连续、实函数,求方程求方程f(x)=0
12、 的实根。的实根。先找到区间先找到区间(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)内有零点,
![循环结构的经典算法之.ppt_第1页](https://file3.taowenge.com/FileRoot3/2022-12/10/976ae0bd-8c18-4d00-b630-44e9e47056fe/976ae0bd-8c18-4d00-b630-44e9e47056fe1.gif)
![循环结构的经典算法之.ppt_第2页](https://file3.taowenge.com/FileRoot3/2022-12/10/976ae0bd-8c18-4d00-b630-44e9e47056fe/976ae0bd-8c18-4d00-b630-44e9e47056fe2.gif)
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 循环 结构 经典 算法
![提示](https://www.taowenge.com/images/bang_tan.gif)
限制150内