递推.递归.迭代说明

递推.递归.迭代说明

ID:6652374

大小:174.50 KB

页数:20页

时间:2018-01-21

递推.递归.迭代说明_第1页
递推.递归.迭代说明_第2页
递推.递归.迭代说明_第3页
递推.递归.迭代说明_第4页
递推.递归.迭代说明_第5页
资源描述:

《递推.递归.迭代说明》由会员上传分享,免费在线阅读,更多相关内容在应用文档-天天文库

1、递推基本介绍  递推算法是一种用若干步可重复的简运算(规律)来描述复杂问题的方法.  递推是序列计算机中的一种常用算法。它是按照一定的规律来计算序列中的每个项,通常是通过计算机前面的一些项来得出序列中的指定象的值。其思想是把一个复杂的庞大的计算过程转化为简单过程的多次重复,该算法利用了计算机速度快和不知疲倦的机器特点。递推算法  递推算法是一种用若干步可重复的简运算(规律)来描述复杂问题的方法.  【例1】  植树节那天,有五位同学参加了植树活动,他们完成植树的棵树都不相同。问第一位同学植了多少棵时,他指着旁边的第二位

2、同学说比他多植了两棵;追问第二位同学,他又说比第三位同学多植了两棵;...如此,都说比另一位同学多植两棵。最后问到第五位同学时,他说自己植了10棵。到底第一位同学植了多少棵树?  分析:设第一位同学植树的棵树为a1,欲求a1,需从第五位同学植树的棵数a5入手,根据“多两棵”这个规律,按照一定顺序逐步进行推算:  (1)a5=10;  (2)a4=a5+2=12;  (3)a3=a4+2=14;  (4)a2=a3+2=16;  (5)a1=a2+2=18;  Pascal程序:  ProgramExaml;  Vari

3、,a:byte;  begin  a:=10;  fori:=1to4do  a:=a+2;  writeln('TheNumis',a);  readln;  end.  本程序的递推运算可用下图示表示:  初始值a:=10-----i=1,a=a+2(12)-----i=2,a=a+2(14)------i=3,a=a+2(16)-----i=4,a=a+2(18)----输出a值  例2:  十本不同的书放在书架上。现重新摆放,使每本书都不在原来放的位置。有几种摆法?  当n个编号元素放在n个编号位置,元素编号与

4、位置编号各不对应的方法数用M(n)表示,那么M(n-1)就表示n-1个编号元素放在n-1个编号位置,各不对应的方法数,其它类推.  第一步,把第n个元素放在一个位置,比如位置k,一共有n-1种方法;  第二步,放编号为k的元素,这时有两种情况.1,把它放到位置n,那么,对于剩下的n-2个元素,就有M(n-2)种方法;2,不把它放到位置n,这时,对于这n-1个元素,有M(n-1)种方法;  综上得到  M(n)=(n-1)[M(n-2)+M(n-1)]递推算法以初始(起点)值为基础,用相同的运算规律,逐次重复运算,直至运

5、算结束。这种从“起点”重复相同的方法直至到达一定“边界”,犹如单向运动,用循环可以实现。递推的本质是按规律逐次推出(计算)先一步的结果。迭代法迭代法也称辗转法,是一种不断用变量的旧值递推新值的过程,跟迭代法相对应的是直接法(或者称为一次解法),即一次性解决问题。迭代法又分为精确迭代和近似迭代。“二分法”和“牛顿迭代法”属于近似迭代法。迭代算法是用计算机解决问题的一种基本方法。它利用计算机运算速度快、适合做重复性操作的特点,让计算机对一组指令(或一定步骤)进行重复执行,在每次执行这组指令(或这些步骤)时,都从变量的原值推

6、出它的一个新值。目录算法1.确定迭代变量2.建立迭代关系式3.对迭代过程进行控制4.举例递归的基本概念和特点算法1.确定迭代变量2.建立迭代关系式3.对迭代过程进行控制4.举例递归的基本概念和特点展开编辑本段算法  利用迭代算法解决问题,需要做好以下三个方面的工作:确定迭代变量  在可以用迭代算法解决的问题中,至少存在一个直接或间接地不断由旧值递推出新值的变量,这个变量就是迭代变量。建立迭代关系式  所谓迭代关系式,指如何从变量的前一个值推出其下一个值的公式(或关系)。迭代关系式的建立是解决迭代问题的关键,通常可以使用

7、递推或倒推的方法来完成。对迭代过程进行控制  在什么时候结束迭代过程?这是编写迭代程序必须考虑的问题。不能让迭代过程无休止地重复执行下去。迭代过程的控制通常可分为两种情况:一种是所需的迭代次数是个确定的值,可以计算出来;另一种是所需的迭代次数无法确定。对于前一种情况,可以构建一个固定次数的循环来实现对迭代过程的控制;对于后一种情况,需要进一步分析出用来结束迭代过程的条件。举例  例1:一个饲养场引进一只刚出生的新品种兔子,这种兔子从出生的下一个月开始,每月新生一只兔子,新生的兔子也如此繁殖。如果所有的兔子都不死去,问到

8、第12个月时,该饲养场共有兔子多少只?  分析:这是一个典型的递推问题。我们不妨假设第1个月时兔子的只数为u1,第2个月时兔子的只数为u2,第3个月时兔子的只数为u3,……根据题意,“这种兔子从出生的下一个月开始,每月新生一只兔子”,则有  u1=1,u2=u1+u1×1=2,u3=u2+u2×1=4,……  根据这个规律,可以归

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。