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

1、游戲：猜猜是什么禮物游戲規(guī)則：邀請幾個學生拆禮物，如果你拆開看到的是禮物盒子，請你將里邊的禮物盒子轉交給下一個同學，下一個同學拆禮物盒子，如果拆開看到的依然禮物盒子，依舊將禮物轉交給盒子給下一個學生，以此類推，直到幸運的學生打開盒子后看到的是禮物。請幸運的學生將禮物交給你前一個學生，依次傳遞回到第一個人，直到第一個學生拿到禮物，并將是什么禮物告知所有的學生。第四章 第五節(jié)從斐波那契的兔子問題看遞歸算法遞歸法的概念這種將問題從未知“遞”到已知，再從已知逐步回“歸”，將原問題求解的過程就是遞歸法求解問題的過程。任務一：兔子問題。開 始問題描述難度系數(shù) *分 析問 題問題：有一對兔子，從出生后第3個

2、月起每個月都生”一對”兔子，小兔子長到第三個月后每個月又生一對兔子，假如兔子都不死，問每個月的兔子總數(shù)為多少？1月2月3月4月5月6月7月8月9月10月11月12月小兔111235813213455大兔1123581321345589合計1123581321345589144當月兔子數(shù)=當月小兔（上上月的兔子數(shù)）+當月大兔（上月的兔子數(shù)）任務一：兔子問題。設 計算 法難度系數(shù) *任務一：兔子問題。難度系數(shù) *調(diào) 試運 行編 寫代 碼問題解決嘗試體驗：求和問題問題描述：s=1+2+3+4+5+6+7+.+n (n1遞推與遞歸遞推實現(xiàn)（循環(huán)實現(xiàn)）遞歸實現(xiàn)（自定義函數(shù)）Private Sub Com

3、mand1_Click()Dim n As Long, i As Long, s As Longn = Val(Text1.Text)For i = To s = Next iText2.Text = sEnd SubFunction sum(ByVal n As Long) As LongIf ( ) Then sum = 1 Else sum =End FunctionPrivate Sub Command1_Click()n = Val(Text1.Text)Text2.Text = sum(n)End Sub1ns + in=1sum(n-1)+n遞推與遞歸對比遞推實現(xiàn)遞歸實現(xiàn)循環(huán)實現(xiàn)

4、自定義函數(shù)實現(xiàn)從已知求到未知從大問題“遞”到已知的小問題，從已知的小問題逐步回“歸”求解大問題優(yōu)點是效率高。運行時間只因循環(huán)次數(shù)增加而增加，沒什么額外開銷?？臻g上沒有什么增加。優(yōu)點就是易理解，容易編程。缺點就是不容易理解，編寫復雜問題時困難。缺點是遞歸是用棧機制實現(xiàn)的，每深入一層，都要占去一塊棧數(shù)據(jù)區(qū)域，對嵌套層數(shù)深的算法，遞歸會力不從心，空間上會以內(nèi)存崩潰而告終，而且遞歸也帶來了大量的函數(shù)調(diào)用，這也有許多額外的時間開銷。所以在深度大時，它的時空性就不好了。遞歸算法基本模式：Function fib(ByVal n As Long) As LongIf (n 3) /遞歸結束條件、出口Then

5、 fib = 1 /直接求解Else fib = fib(n - 1) + fib(n - 2) /遞歸求解End Function小結：(1)遞歸法通過自定義函數(shù)來實現(xiàn)；(2）函數(shù)體內(nèi)通過分支來判斷是否滿足遞歸結束條件，不滿足則進一步縮小規(guī)模，遞歸處理。遞歸算法總結：遞歸算法1遞歸法規(guī)律2遞歸法的優(yōu)缺點優(yōu)點缺點概 念遞歸算法結構 遞歸算法基本模式 自己調(diào)用自己自定義函數(shù)（函數(shù)調(diào)用本身）遞歸法的基本模式Function sum( ) As LongIf ( ) Then /遞歸出口Else /遞歸調(diào)用函數(shù)自己End Function歡迎交流完！課后作業(yè)課后習題：難度系數(shù) *按照遞歸算法解決問題的一般步驟：分析問題，設計算法，編寫程序，調(diào)試運行，完成以下習題。1.某同學在上樓梯時，有時一步一級樓梯，有時一步兩級。如果樓梯有n級，他上完這n級樓梯有多少種不同