4.5.1从裴波那契的兔子问题看递归算法VIP免费

递归算法与递归程序德罗斯特效应（Drosteeffect）是递归的一种视觉形式，是指一张图片的某个部分与整张图片相同，如此产生无限循环。递归算法：是一种直接或者间接地调用自身的算法。在定义一个过程或函数时出现调用本过程或本函数的成分，称之为递归。什么时候调用递归？什么时候调用递归？问题4-16：著名的意大利数学家斐波那契(Fibonacci)在他的著作《算盘书》中提出了一个“兔子问题”：假定小兔子一个月就可以长成大兔子，而大兔子每个月都会生出一对小兔子。如果年初养了一对小兔子，问到年底时将有多少对兔子?(当然得假设兔子没有死亡而且严格按照上述规律长大与繁殖)(1)分析问题。这个表格虽然解决了斐波那契的兔子问题(年底时兔子的总数是144只)，但仔细观察一下这个表格，你会发现兔子的数目增长得越来越快，如果时间再长，只用列表的方法就会有困难。(例如，你愿意用列表的方法求出5年后兔子的数目吗？)我们需要研究表中的规律，找出一般的方法，去解决这个问题。1月2月3月4月5月6月7月8月9月10月1112小兔111235813213455大兔1123581321345589合计1123581321345589144仔细研究表4-8，你有些什么发现？每一个月份的大兔数、小兔数与上一个月的数字有什么联系？每个月的小兔子数等于上个月的大兔子数；每个月的大兔子数等于上个月的兔子总数；从第三个月起：每个月的兔子总数等于前两个月的兔子数之和。(2)(2)设计算法。设计算法。“兔子问题”很容易列出一条递推式而得到解决。假设第N个月的兔子数目是F(N)，我们有：F(N)=1，当N=1、2时F(N-1)+F(N-2)，当N>=3时前面学过：前面学过：自定义函数的定义格式:Function函数名(参数表)[Astype]过程中的代码EndFunction调用函数的格式：函数名(参数表)(3)(3)编写程序。编写程序。FunctionFib(ByValNAsInteger)AsLongIfN<3ThenFib=1ElseFib=Fib(N-1)+Fib(N-2)EndFunctionPrivateSubCommand1_Click()N=Val(Text1.Text)Text2.Text="第"&N&"月的兔子数目是："&Fib(N)EndSub定义自定义函数fib，求第N个月的兔子数求第N个月的兔子数并在文本框2中输出(4)(4)调试程序调试程序因为这个算法的效率不高，建议在调试程序时月份数不要大于40。斐波那契数列斐波那契数列又称又称黄金分割数列黄金分割数列00、、11、、11、、22、、33、、55、、88、、1313、、2121、、3434、、5555、、8989、、144144、、233233、、377377、、610610、、987987、、15971597、、25842584、、41814181、、67656765、、1094610946、、1771117711、、2865728657、、46368…46368…这是一个线性递推数列。这是一个线性递推数列。生活中的斐波那契数列生活中的斐波那契数列斐波那契数列中的斐波那契数会经常出现在斐波那契数列中的斐波那契数会经常出现在我们的眼前我们的眼前————比如松果、凤梨、树叶的排比如松果、凤梨、树叶的排列、一些花朵的花瓣数（典型的有向日葵花列、一些花朵的花瓣数（典型的有向日葵花瓣），蜂巢，蜻蜓翅膀，黄金矩形、黄金分瓣），蜂巢，蜻蜓翅膀，黄金矩形、黄金分割、等角螺线，十二平均律等。割、等角螺线，十二平均律等。斐波那契数列在自然里还有许多应用。例如，树木的生长。由于新生的枝条，往往需要一段“休息”时间，供自身生长，而后才能萌发新枝。所以，一株树苗在一段间隔，例如一年，以后长出一条新枝；第二年新枝“休息”，老枝依旧萌发；此后，老枝与“休息”过一年的枝同时萌发，当年生的新枝则次年“休息”。这样，一株树木各个年份的枝桠数，便构成斐波那契数列。这个规律，就是生物学上著名的“鲁德维格定律”。为什么自然界中有如此之多的斐波那契数列巧合呢？这是植物在大自然中长期适应和进化的结果，就像盐的晶体必然是立方体的形状一样。当然，受气候或病虫害的影响，真实的植物往往没有完美的斐波那契螺旋。4.5.2一个应用递归算法解决的问题经典例子大家玩汉诺塔游戏：这个游戏盘子在A、B、C三根柱子上不停运动，有没有规律，和你在照过镜子时遇到的情况相同吗？在印度，有这么一个古老的传说：在世界中心贝拿勒斯（在印度北部）的圣庙里，一块黄铜板上插着三根宝石针。印度教的...