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

1、4.5.1 从裴波那契的兔子问题看递归算法授课教师：王小艳学科：高中信息技术单位：合肥市第六中学教材：广东教育出版社 信息技术（选修1）算法与程序设计一、兔子问题小兔子兔子大兔子一个月一个月生出一、兔子问题如果年初养了一对小兔子，问到年底时将有多少对兔子？（假设兔子没有死亡而且严格按照上述规律长大与繁殖）（1）分析问题第1个月（对）：第2个月（对）：第3个月（对）：第4个月（对）：第5个月（对）：第6个月（对）：第7个月（对）：11235813（1）分析问题1月2月3月4月5月6月7月8月9月10月11月12月小兔111235813213455大兔1123581321345589合计11235

2、81321345589144（2）设计算法F(N)=11F(N-1)+F(N-2)N=1N=2N20, 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)=11F(N-1)+F(N-2)N=1N=2N2递归算法：函数不断引用自身，直到引用的对象已知，否则会成为死循环而不能正常结束。思路清晰，代码少。例：当N=5，求F(N)?F(5)=F(4)+F(3)F(4)=F(3)+F(2)F(3)=F(2)+F(1)F(2)=1F

3、(1)=1F(1)=1F(2)=1F(3)=F(2)+F(1)=2F(4)=F(3)+F(2)=3F(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 FunctionN 3Fib = 1Fib = Fib(N - 1) + Fib(N - 2)（3）编写程序Function Fib(ByVal N As Integer) As Long If N 3 Then Fib =

4、1 Else: Fib = Fib(N - 1) + Fib(N - 2)End FunctionPrivate Sub Command1_Click()N = Val(Text1.Text)Text2.Text = 第 & N & 月的兔子对数是： & Fib(N)End Sub递归算法（4）调试程序完成学习资源包中的任务1其他算法 If （条件）Then 表达式1 Else: 表达式2For循环语句基本格式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 iEnd IfPrint cEnd Sub学习资源包学案任务2比较不同算法的效率