4.5.1從裴波那契的兔子問(wèn)題看遞歸算法

1、4.5.1 從裴波那契的兔子問(wèn)題看遞歸算法授課教師：王小艷學(xué)科：高中信息技術(shù)單位：合肥市第六中學(xué)教材：廣東教育出版社 信息技術(shù)（選修1）算法與程序設(shè)計(jì)一、兔子問(wèn)題小兔子兔子大兔子一個(gè)月一個(gè)月生出一、兔子問(wèn)題如果年初養(yǎng)了一對(duì)小兔子，問(wèn)到年底時(shí)將有多少對(duì)兔子？（假設(shè)兔子沒(méi)有死亡而且嚴(yán)格按照上述規(guī)律長(zhǎng)大與繁殖）（1）分析問(wèn)題第1個(gè)月（對(duì)）：第2個(gè)月（對(duì)）：第3個(gè)月（對(duì)）：第4個(gè)月（對(duì)）：第5個(gè)月（對(duì)）：第6個(gè)月（對(duì)）：第7個(gè)月（對(duì)）：11235813（1）分析問(wèn)題1月2月3月4月5月6月7月8月9月10月11月12月小兔111235813213455大兔1123581321345589合計(jì)11235

2、81321345589144（2）設(shè)計(jì)算法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è)計(jì)算法F(N)=11F(N-1)+F(N-2)N=1N=2N2遞歸算法：函數(shù)不斷引用自身，直到引用的對(duì)象已知，否則會(huì)成為死循環(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）編寫(xiě)程序遞歸算法 If （條件）Then 表達(dá)式1 Else: 表達(dá)式2（3）編寫(xiě)程序遞歸算法Function Fib(ByVal N As Integer) As Long If Then Else: End FunctionN 3Fib = 1Fib = Fib(N - 1) + Fib(N - 2)（3）編寫(xiě)程序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 & 月的兔子對(duì)數(shù)是： & Fib(N)End Sub遞歸算法（4）調(diào)試程序完成學(xué)習(xí)資源包中的任務(wù)1其他算法 If （條件）Then 表達(dá)式1 Else: 表達(dá)式2For循環(huán)語(yǔ)句基本格式For 循環(huán)變量=初值 To 終值 step 步長(zhǎng) 語(yǔ)句組Next 循環(huán)變量其他算法Private Sub Command1_Click()n = Val(Text1.Text)If n 3 Then c = 1 每月的兔子對(duì)數(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比較不同算法的效率