4.5.1從裴波那契的兔子問題看遞歸算法

1、4.5.1 從裴波那契的兔子問題看遞歸算法授課教師：王小艷學(xué)科：高中信息技術(shù)單位：合肥市第六中學(xué)教材：廣東教育出版社 信息技術(shù)（選修1）算法與程序設(shè)計一、兔子問題小兔子兔子大兔子一個月一個月生出一、兔子問題如果年初養(yǎng)了一對小兔子，問到年底時將有多少對兔子？（假設(shè)兔子沒有死亡而且嚴格按照上述規(guī)律長大與繁殖）（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）設(shè)計算法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）設(shè)計算法F(N)=11F(N-1)+F(N-2)N=1N=2N2遞歸算法：函數(shù)不斷引用自身，直到引用的對象已知，否則會成為死循環(huán)而不能正常結(jié)束。思路清晰，代碼少。例：當(dāng)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 & 月的兔子對數(shù)是： & Fib(N)End Sub遞歸算法（4）調(diào)試程序完成學(xué)習(xí)資源包中的任務(wù)1其他算法 If （條件）Then 表達式1 Else: 表達式2For循環(huán)語句基本格式For 循環(huán)變量=初值 To 終值 step 步長 語句組Next 循環(huán)變量其他算法Private Sub Command1_Click()n = Val(Text1.Text)If n 3 Then c = 1 每月的兔子對數(shù)Else a = 1: b = 1 For i = 3 To n c = a + b: a = b: b = c a每月小兔子 b每月大兔子 Next iEnd IfPrint cEnd Sub學(xué)習(xí)資源包學(xué)案任務(wù)2比較不同算法的效率