2021年递归算法与递归程序.ppt

导入 : 大家玩汉诺塔游戏： 这个游戏盘子在A、B、C三根柱子上不停运动，有没有规律，和你在照过镜子时遇到的情况相同吗？
递归算法与递归程序
2021/1/15
1
当你往镜子前面一站，镜子里面就有一个你的像。但你试过两面镜子一起照吗?如果甲、乙两面镜子相互面对面放着，你往中间一站，嘿，两面镜子里都有你的千百个“化身”!为什么会有这么奇妙的现象呢?原来，甲镜子里有乙镜子的像，乙镜子里也有甲镜子的像，而且这样反反复复，就会产生一连串的“像中像”。这是一种递归现象。
递归算法与递归程序
2021/1/15
2
递归算法：是一种直接或者间接地调用自身的算法。在计算机编写程序中，递归算法对解决一大类问题是十分有效的，它往往使算法的描述简洁而且易于理解
递归算法与递归程序
2021/1/15
3
问题4-16：著名的意大利数学家斐波那契(Fibonacci)在他的著作《算盘书》中提出了一个“兔子问题”：假定小兔子一个月就可以长成大兔子，而大兔子每个月都会生出一对小兔子。如果年初养了一对小兔子，问到年底时将有多少对兔子?  (当然得假设兔子没有死亡而且严格按照上述规律长大与繁殖)
递归算法与递归程序
2021/1/15
4
我们不难用以前学过的知识设计出如下算法：
①输入计算兔子的月份数：n
②If n < 3 Then c = 1 Else a = 1: b = 1
③i = 3
④c = a + b：a = b：b = c
⑤i=i+1,如果i≤n则返回④
⑥结束
递归算法与递归程序
2021/1/15
5
参考程序如下：
Private Sub Command1_Click()
  n = Val()
  If n < 3 Then c = 1 Else a = 1: b = 1
  For i = 3 To n
    c = a + b
    a = b
    b = c
  Next i
  = "第" & n & "月的兔子数目是：" & c
End Sub
递归算法与递归程序
2021/1/15
6
开动脑筋：我们有没有更简单的方法解决该问题呢？
递归算法与递归程序
2021/1/15
7
(1)分析问题。
这个表格虽然解决了斐波那契的兔子问题(年底时兔子的总数是144只)，但仔细观察一下这个表格，你会发现兔子的数目增长得越来越快，如果时间再长，只用列表的方法就会有困难。(例如，你愿意用列表的方法求出5年后兔子的数目吗？)我们需要研究表中的规律，找出一般的方法，去解决这个问题。
1月
2月
3月
4月
5月
6月
7月
8月
9月
10月
11月
12
小兔
1
1
1
2
3
5
8
13
21
34
55
大兔
1
1
2
3
5
8
13
21
34
55
89
合计
1
1
2
3
5
8
13
21
34
55
89
144
递归算法与递归程序
2021/1/15
8
仔细研究表4-8，你有些什么发现？每一个月份的大兔数、小兔数与上一个月的数字有什么联系，能肯定这个规律吗？恭喜你，你快成功了？
递归算法与递归程序
2021/1/15
9
(2)设计算法。
“兔子问题”很容易列出一条递推式而得到解决。假设第N个月的兔子数目是F(N)，我们有：
这是因为每月的大兔子数目一定等于上月的兔子总数，而每个月的小兔子数目一定等于上月的大兔子数目(即前一个月的兔子的数目)。
递归算法与递归程序
2021/1/15
10