高中信息技術(shù)課件：遞歸算法-(共19張ppt)word版本

1、高中信息技術(shù)課件：遞歸算法-(共19張PPT) 某人有一對(duì)兔子飼養(yǎng)在圍墻中，如果它們每個(gè)月生一對(duì)兔子，且新生的兔子在第二個(gè)月后也是每個(gè)月生一對(duì)兔子，問一年后圍墻中共有多少對(duì)兔子。 第一個(gè)月是最初的一對(duì)兔子生下一對(duì)兔子，圍墻內(nèi)共有兩對(duì)兔子。第二個(gè)月仍是最初的一對(duì)兔子生下一對(duì)兔子，共有3對(duì)兔子。到第三個(gè)月除最初的兔子新生一對(duì)兔子外，第一個(gè)月生的兔子也開始生兔子，因此共有5對(duì)兔子。繼續(xù)推下去，第12個(gè)月時(shí)最終共有對(duì)377對(duì)兔子。每個(gè)月的兔子總數(shù)可由前兩個(gè)月的兔子數(shù)相加而得。 輸入計(jì)算兔子的月份數(shù)：nIfn3Thenc=1Elsea=1:b=1i=3c=a+b：a=b：b=ci=i+1,如果in則返回

2、結(jié)束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 Next i Text2.Text = 第 & n & 月的兔子數(shù)目是： & cEnd Sub 我們有沒有更簡(jiǎn)單的方法解決該問題呢？(1)分析問題我們可以根據(jù)題意列出表來解決這個(gè)問題：兔子問題分析表 仔細(xì)研究兔子問題分析表，你有些什么發(fā)現(xiàn)？每一個(gè)月份的大兔數(shù)、小兔數(shù)與上一個(gè)月的數(shù)字有什么聯(lián)系，能肯定這個(gè)規(guī)律嗎？(2)設(shè)計(jì)算法。

3、 “兔子問題”很容易列出一條遞推式而得到解決。假設(shè)第N個(gè)月的兔子數(shù)目是F(N)，我們有： 這是因?yàn)槊吭碌拇笸米訑?shù)目一定等于上月的兔子總數(shù)，而每個(gè)月的小兔子數(shù)目一定等于上月的大兔子數(shù)目(即前一個(gè)月的兔子的數(shù)目)。 由上述的遞推式我們可以設(shè)計(jì)出遞歸程序。遞歸程序的特點(diǎn)是獨(dú)立寫出一個(gè)函數(shù)(或子過程)，而這個(gè)函數(shù)只對(duì)極簡(jiǎn)單的幾種情況直接給出解答，而在其余情況下通過反復(fù)的調(diào)用自身而把問題歸結(jié)到最簡(jiǎn)單的情況而得到解答。自定義函數(shù)的定義格式: Function procedurename(arguments) As type Statements End Function其中的procedurename是函

4、數(shù)名，arguments是函數(shù)中的參數(shù)表，type是函數(shù)返回值的數(shù)據(jù)類型，表示可有可無的部分，statements是過程中的代碼調(diào)用函數(shù)的格式：procedurename(arguments)(3)編寫程序 窗體中開設(shè)一個(gè)文本框Text1用于填人月數(shù)N，設(shè)置命令框Commandl，點(diǎn)擊它即執(zhí)行程序求出第N月的兔子數(shù)。然后用文本框Text2輸出答案。Function Fib(ByVal N As Integer) As Long If N 3 Then Fib = 1 Else Fib = Fib(N - 1) + Fib(N - 2)End FunctionPrivate Sub Comman

5、d1_Click() N = Val(Text1.Text) Text2.Text = 第 & N & 月的兔子數(shù)目是： & Fib(N)End Sub(4)調(diào)試程序 因?yàn)檫@個(gè)算法的效率不高，建議在調(diào)試程序時(shí)月份數(shù)不要大于40。(1)利用遞歸方法編寫一求N的階乘。分析：根據(jù)N!=N*(N-1)*(N-2)*(N-3)*3*2*1可以推出下列式子： Function F(ByVal n As Integer) As Long If n = 1 Then F = 1 Else F = n * F(n - 1)End FunctionPrivate Sub Form_Clic

6、k() Dim n As Integer n = Val(InputBox(請(qǐng)輸入正整數(shù)N：, 求N的階乘) Print 輸入的正整數(shù)是; n; Print ，階乘是; F(n)End Sub遞歸算法的特點(diǎn)遞歸過程一般通過函數(shù)或子過程來實(shí)現(xiàn)。遞歸算法：在函數(shù)或子過程的內(nèi)部，直接或者間接地調(diào)用自己的算法。遞歸算法的實(shí)質(zhì)：是把問題轉(zhuǎn)化為規(guī)?？s小了的同類問題的子問題。然后遞歸調(diào)用函數(shù)(或過程)來表示問題的解。遞歸算法解決問題的特點(diǎn)：(1) 遞歸就是在過程或函數(shù)里調(diào)用自身。(2) 在使用遞增歸策略時(shí)，必須有一個(gè)明確的遞歸結(jié)束條件，稱為遞歸出口。(3) 遞歸算法解題通常顯得很簡(jiǎn)潔，但遞歸算法解題的運(yùn)行效率較低。所以一般不提倡用遞歸算法設(shè)計(jì)程序。(4) 在遞歸調(diào)用的過程當(dāng)中系統(tǒng)為每一層的返回點(diǎn)、局部量等開辟了棧來存儲(chǔ)。遞歸次數(shù)過多容易造成棧溢出等。所以一般不提倡用遞歸算法設(shè)計(jì)程序。遞歸算法所體現(xiàn)的“重復(fù)”一般有三個(gè)要求：一是每次調(diào)用在規(guī)模上都有所縮小(通常是減半)；二是相鄰兩次重復(fù)之間有緊密的聯(lián)系，前一次要為后一次做準(zhǔn)備(通常前一次的輸出就作為后一次的輸入)；三是在問題的規(guī)模極小時(shí)必須用直接給出解答而不再進(jìn)行遞歸調(diào)用，因而每次遞歸調(diào)用都是有條件的(以規(guī)模未達(dá)到