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

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

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

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

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