(
课件网) 4.5.1 从裴波那契的兔子问题看递归算法 授课教师： 学科：高中信息技术 单位：合肥市第六中学 教材：广东教育-出卷网- 信息技术（选修1）《算法与程序设计》 一、兔子问题 小兔子 兔子 大兔子 一个月 一个月 生出 一、兔子问题 如果年初养了一对小兔子，问到年底时将有多少对兔子？（假设兔子没有死亡而且严格按照上述规律长大与繁殖） （1）分析问题 第1个月（对）： 第2个月（对）： 第3个月（对）： 第4个月（对）： 第5个月（对）： 第6个月（对）： 第7个月（对）： 1 1 2 3 5 8 13 （1）分析问题 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 （2）设计算法 F(N)= ｛ 1 1 F(N-1)+F(N-2) N=1 N=2 N>2 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233，377，610，987，1597，2584，4181，6765，10946，17711，28657，46368 （2）设计算法 F(N)= ｛ 1 1 F(N-1)+F(N-2) N=1 N=2 N>2 递归算法：函数不断引用自身，直到引用的对象已知，否则 会成为死循环而不能正常结束。思路清晰，代码少。 例：当N=5，求F(N) F(5)=F(4)+F(3) F(4)=F(3)+F(2) F(3)=F(2)+F(1) F(2)=1 F(1)=1 F(1)=1 F(2)=1 F(3)=F(2)+F(1)=2 F(4)=F(3)+F(2)=3 F(5)=F(4)+F(3)=5 不足： 递归算法的效率不高。 （3）编写程序 递归算法 If （条件）Then 表达式1 Else: 表达式2 （3）编写程序 递归算法 Function Fib(ByVal N As Integer) As Long If Then Else: End Function N < 3 Fib = 1 Fib = Fib(N - 1) + Fib(N - 2) （3）编写程序 Function Fib(ByVal N As Integer) As Long If N < 3 Then Fib = 1 Else: Fib = Fib(N - 1) + Fib(N - 2) End Function Private Sub Command1_Click() N = Val(Text1.Text) Text2.Text = "第" & N & "月的兔子对数是：" & Fib(N) End Sub 递归算法 （4）调试程序 完成学习资源包中的任务1 其他算法 If （条件）Then 表达式1 Else: 表达式2 For循环语句 基本格式 For 循环变量=初值 To 终值 step 步长 语句组 Next 循环变量 其他算法 Private Sub Command1_Click() n = Val(Text1.Text) If n < 3 Then c = 1 ‘每月的兔子对数 Else a = 1: b = 1 For i = 3 To n c = a + b: a = b: b = c ‘a每月小兔子 b每月大兔子 Next i End If Print c End Sub 学习资源包学案任务2 比较不同算法的效率（任务3） 递归算法 其他算法 当N=10 当N=40 总结 斐波那契数列 递归算法 任务4：在VB语言环境下用递归算法求n!（n!=1*2*3*···*n），如图
