资源描述:
《递推.递归.迭代说明》由会员上传分享,免费在线阅读,更多相关内容在应用文档-天天文库。
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,a:byte; begin a:=10; fori:=1to4do a:=a+2; writeln('TheNumis',a
3、); 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个编号位置,元素编号与位置编号各不对应的方法数用M(n)表示,那么M(n-1)就表示n-1个编号元素放在n-1个编号位置,各不对应的方法数,其它类推. 第一步,把第n个元素放在一个位置,比如位置k,一共有n-1种方法; 第
4、二步,放编号为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、为精确迭代和近似迭代。“二分法”和“牛顿迭代法”属于近似迭代法。迭代算法是用计算机解决问题的一种基本方法。它利用计算机运算速度快、适合做重复性操作的特点,让计算机对一组指令(或一定步骤)进行重复执行,在每次执行这组指令(或这些步骤)时,都从变量的原值推出它的一个新值。目录算法1.确定迭代变量2.建立迭代关系式3.对迭代过程进行控制4.举例递归的基本概念和特点算法1.确定迭代变量2.建立迭代关系式3.对迭代过程进行控制4.举例递归的基本概念和特点展开编辑本段算法 利用迭代算法解决问题,需要做好以下三个方面的工作:确定迭代变量 在可以用迭代算法解决的问题中,至少存在一个直接或间接地不断
6、由旧值递推出新值的变量,这个变量就是迭代变量。建立迭代关系式 所谓迭代关系式,指如何从变量的前一个值推出其下一个值的公式(或关系)。迭代关系式的建立是解决迭代问题的关键,通常可以使用递推或倒推的方法来完成。对迭代过程进行控制 在什么时候结束迭代过程?这是编写迭代程序必须考虑的问题。不能让迭代过程无休止地重复执行下去。迭代过程的控制通常可分为两种情况:一种是所需的迭代次数是个确定的值,可以计算出来;另一种是所需的迭代次数无法确定。对于前一种情况,可以构建一个固定次数的循环来实现对迭代过程的控制;对于后一种情况,需要进一步分析出用来结束迭代过程的条件。举例 例1:一个饲养场引进一只刚
7、出生的新品种兔子,这种兔子从出生的下一个月开始,每月新生一只兔子,新生的兔子也如此繁殖。如果所有的兔子都不死去,问到第12个月时,该饲养场共有兔子多少只? 分析:这是一个典型的递推问题。我们不妨假设第1个月时兔子的只数为u1,第2个月时兔子的只数为u2,第3个月时兔子的只数为u3,……根据题意,“这种兔子从出生的下一个月开始,每月新生一只兔子”,则有 u1=1,u2=u1+u1×1=2,u3=u2+u2×1=4,…… 根据这个规律,可以归