递归算法与递归程序课件.ppt

《递归算法与递归程序课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、递归算法与递归程序导入:大家玩汉诺塔游戏： 这个游戏盘子在A、B、C三根柱子上不停运动，有没有规律，和你在照过镜子时遇到的情况相同吗？当你往镜子前面一站，镜子里面就有一个你的像。但你试过两面镜子一起照吗?如果甲、乙两面镜子相互面对面放着，你往中间一站，嘿，两面镜子里都有你的千百个“化身”!为什么会有这么奇妙的现象呢?原来，甲镜子里有乙镜子的像，乙镜子里也有甲镜子的像，而且这样反反复复，就会产生一连串的“像中像”。这是一种递归现象。递归算法：是一种直接或者间接地调用自身的算法。在计算机编写程序中，递归算法对解决一大类问题是十分有效的，它

2、往往使算法的描述简洁而且易于理解问题4-16：著名的意大利数学家斐波那契(Fibonacci)在他的著作《算盘书》中提出了一个“兔子问题”：假定小兔子一个月就可以长成大兔子，而大兔子每个月都会生出一对小兔子。如果年初养了一对小兔子，问到年底时将有多少对兔子? (当然得假设兔子没有死亡而且严格按照上述规律长大与繁殖)我们不难用以前学过的知识设计出如下算法：①输入计算兔子的月份数：n②Ifn<3Thenc=1Elsea=1:b=1③i=3④c=a+b：a=b：b=c⑤i=i+1,如果i≤n则返回④⑥结束参考程序如下：PrivateSubC

3、ommand1_Click()n=Val(Text1.Text)Ifn<3Thenc=1Elsea=1:b=1Fori=3Tonc=a+ba=bb=cNextiText2.Text="第"&n&"月的兔子数目是："&cEndSub开动脑筋：我们有没有更简单的方法解决该问题呢？(1)分析问题。这个表格虽然解决了斐波那契的兔子问题(年底时兔子的总数是144只)，但仔细观察一下这个表格，你会发现兔子的数目增长得越来越快，如果时间再长，只用列表的方法就会有困难。(例如，你愿意用列表的方法求出5年后兔子的数目吗？)我们需要研究表中的规律，找出一

4、般的方法，去解决这个问题。1月2月3月4月5月6月7月8月9月10月11月12小兔111235813213455大兔1123581321345589合计1123581321345589144仔细研究表4-8，你有些什么发现？每一个月份的大兔数、小兔数与上一个月的数字有什么联系，能肯定这个规律吗？恭喜你，你快成功了？(2)设计算法。“兔子问题”很容易列出一条递推式而得到解决。假设第N个月的兔子数目是F(N)，我们有：这是因为每月的大兔子数目一定等于上月的兔子总数，而每个月的小兔子数目一定等于上月的大兔子数目(即前一个月的兔子的数目)。前

5、面学过：自定义函数的定义格式:Function函数名(参数表)[Astype]过程中的代码EndFunction调用函数的格式：函数名(参数表)(3)编写程序。FunctionFib(ByValNAsInteger)AsLongIfN<3ThenFib=1ElseFib=Fib(N-1)+Fib(N-2)EndFunctionPrivateSubCommand1_Click()N=Val(Text1.Text)Text2.Text="第"&N&"月的兔子数目是："&Fib(N)EndSub(4)调试程序因为这个算法的效率不高，建议在调

6、试程序时月份数不要大于40。4.5.2  一个应用递归算法解决的问题经典例子问题4-17：传说在古代印度的贝拿勒斯神庙，有一块黄铜板上插了3根宝石柱，在其中一根宝石柱自上而下由小到大地叠放着64个大小不等的金盘。一名僧人把这些金盘从一根宝石柱移到另外一根上。僧人在移动金盘时遵守下面3条规则：第一，一次只能移动一个金盘。第二，每个金盘只能由一根宝石柱移到另外一根宝石柱。第三，任何时候都不能把大的金盘放在小的金盘上。神话说，如果僧人把64个金盘完全地从一根宝石移到了另外一根上，世界的末日就要到了。当然，神话只能当故事来听，世界不可以因为个

7、别人的活动而导致末日。不过，从僧人搬完64个金盘所需时间的角度来说，即使僧人每秒都能移动一个金盘，那也得要几千亿年！(1)分析问题。我们把3根宝石柱分别命名为A、B、C。最初有N个金盘放在A，需要把它们全部按规则移动到B。当N=1时，直接把金盘从A搬到B就可以了，1次成功。当N≥2，那么需要利用C柱来过渡。我们假设已经找到一种把N－1个金盘从一根柱搬到另外一根柱的方法，那么，我们只要把N－1个金盘从A搬到C，然后把最大的金盘从A搬到B，最后把C上的N一1个金盘搬到B就可以了。靠递归的思想，我们轻而易举地完成了整个搬动。(2)设计算法。

8、我们定义一个过程Hanoi(N，A，B，C)，表示有N个金盘需要从A柱搬到B柱(以C柱为过渡)。那么完成它只需3步：①Hanoi(N一1，A，C，B)它的意思是把A柱上的N一1个金盘搬到C柱；② A→B 它的意思是把一个