4-5 遞歸算法與遞歸程序.doc

一、 教學(xué)目標(biāo)1、 知識與技能(1)認(rèn)識遞歸現(xiàn)象。(2)使用遞歸算法解決問題往往能使算法的描述乘法而易于表達(3)理解遞歸三要素：每次遞歸調(diào)用都要縮小規(guī)模；前次遞歸調(diào)用為后次作準(zhǔn)備：遞歸調(diào)用必須有條件進行。(4)認(rèn)識遞歸算法往往不是高效的算法。(5)了解遞歸現(xiàn)象的規(guī)律。(6)能夠設(shè)計遞歸程序解決適用于遞歸解決的問題。(7)能夠根據(jù)算法寫出遞歸程序。(8)了解生活中的遞歸現(xiàn)象，領(lǐng)悟遞歸現(xiàn)象的既有重復(fù)，又有變化的特點，并且從中學(xué)習(xí)解決問題的一種方法。2、 方法與過程本節(jié)讓同學(xué)們玩漢諾塔的游戲，導(dǎo)入遞歸問題，從用普通程序解決斐波那契的兔子問題入手，引導(dǎo)學(xué)生用自定義了一個以遞歸方式解決的函數(shù)過程解決問題，同時讓同學(xué)們做三個遞歸練習(xí)，鞏固提高。然后讓學(xué)生做練習(xí)(2)和練習(xí)(3)這兩道題目的形式相差很遠，但方法和答案卻是完全相同的練習(xí)，體會其中的奧妙，加深對遞歸算法的了解。最后用子過程解決漢諾塔的經(jīng)典問題。3、 情感態(tài)度和價值觀結(jié)合高中生想象具有較強的隨意性、更富于現(xiàn)實性的身心發(fā)展特點，綜合反映出遞歸算法的特點，以及遞歸算法解答某些實踐問題通常得很簡潔，從而激發(fā)學(xué)生對程序設(shè)計的追求和向往。二、 重點難點1、 教學(xué)重點（1） 了解遞歸現(xiàn)象和遞歸算法的特點。（2） 能夠根據(jù)問題設(shè)計出恰當(dāng)?shù)倪f歸程序。2、 教學(xué)難點(1)遞歸過程思路的建立。(2)判斷問題是否適于遞歸解法。(3)正確寫出遞歸程序。三、 教學(xué)環(huán)境1、 教材處理教材選自廣東省普通高中信息技術(shù)選修一：算法與程序設(shè)計第四章第五節(jié)，原教材的編排是以本節(jié)以斐波那契的兔子問題引人，導(dǎo)出遞歸算法，從而自定義了一個以遞歸方式解決的函數(shù)過程。然后利用子過程解決漢諾塔的經(jīng)典問題。教材經(jīng)處理后，讓同學(xué)們玩漢諾塔的游戲，導(dǎo)入遞歸問題，從用普通程序解決斐波那契的兔子問題入手，引導(dǎo)學(xué)生用自定義了一個以遞歸方式解決的函數(shù)過程解決問題，同時讓同學(xué)們做三個遞歸練習(xí)，鞏固提高。然后讓學(xué)生做練習(xí)(2)和練習(xí)(3)這兩道題目的形式相差很遠，但方法和答案卻都是完全相同的練習(xí)，體會其中的奧妙，加深對遞歸算法的了解。最后用子過程解決漢諾塔的經(jīng)典問題。教學(xué)方法采用講解、探究、任務(wù)驅(qū)動和學(xué)生自主學(xué)習(xí)相結(jié)合2、 預(yù)備知識學(xué)生已掌握了用計算機解決問題的過程，掌握了程序設(shè)計基礎(chǔ)，掌握了解析法、窮舉法、查找法、排序法設(shè)計程序的技巧。3、 硬件要求建議本節(jié)課在多媒體電腦教室中完成，最好有廣播教學(xué)系統(tǒng)或投影儀，為拓展學(xué)習(xí)，學(xué)生機應(yīng)允許上互聯(lián)網(wǎng)。4、 所需軟件學(xué)生機要安裝VB6.0或以上版本。5、 所需課時2課時（90分鐘）四、 教學(xué)過程導(dǎo)入：大家玩漢諾塔游戲： 圖4-5(1)漢諾塔游戲的部分界面這個游戲盤子在A、B、C三根柱子上不停運動，有沒有規(guī)律，和你在照過鏡子時遇到的情況相同嗎？當(dāng)你往鏡子前面一站，鏡子里面就有一個你的像。但你試過兩面鏡子一起照嗎?如果甲、乙兩面鏡子相互面對面放著，你往中間一站，嘿，兩面鏡子里都有你的千百個“化身”!為什么會有這么奇妙的現(xiàn)象呢?原來，甲鏡子里有乙鏡子的像，乙鏡子里也有甲鏡子的像，而且這樣反反復(fù)復(fù)，就會產(chǎn)生一連串的“像中像”。這是一種遞歸現(xiàn)象。由同學(xué)們總結(jié)出遞歸算法的概念遞歸算法：是一種直接或者間接地調(diào)用自身的算法。在計算機編寫程序中，遞歸算法對解決一大類問題是十分有效的，它往往使算法的描述簡潔而且易于理解。問題4-16：著名的意大利數(shù)學(xué)家斐波那契(Fibonacci)在他的著作算盤書中提出了一個“兔子問題”：假定小兔子一個月就可以長成大兔子，而大兔子每個月都會生出一對小兔子。如果年初養(yǎng)了一對小兔子，問到年底時將有多少對兔子? (當(dāng)然得假設(shè)兔子沒有死亡而且嚴(yán)格按照上述規(guī)律長大與繁殖)我們不難用以前學(xué)過的知識設(shè)計出如下算法： 輸入計算兔子的月份數(shù)：n If n 3 Then c = 1 Else a = 1: b = 1 i = 3 c = a + b：a = b：b = c i=i+1,如果in則返回 結(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圖4-5(2)斐波那契兔子程序運行結(jié)果圖開動腦筋：我們有沒有更簡單的方法解決該問題呢？4.5.1 從斐波那契的兔子問題看遞歸算法1斐波那契的兔子問題子 (1)分析問題。我們可以根據(jù)題意列出表4-3來解決這個問題：表43兔子問題分析表1月2月3月4月5月6月7月8月9月10月11月12月小兔111235813213455大兔1123581321345589合計1123581321345589144這個表格雖然解決了斐波那契的兔子問題(年底時兔子的總數(shù)是144只)，但仔細觀察一下這個表格，你會發(fā)現(xiàn)兔子的數(shù)目增長得越來越快，如果時間再長，只用列表的方法就會有困難。(例如，你愿意用列表的方法求出5年后兔子的數(shù)目嗎？)我們需要研究表中的規(guī)律，找出一般的方法，去解決這個問題。交流仔細研究表4-8，你有些什么發(fā)現(xiàn)？每一個月份的大兔數(shù)、小兔數(shù)與上一個月的數(shù)字有什么聯(lián)系，能肯定這個規(guī)律嗎？恭喜你，你快成功了？(2)設(shè)計算法?！巴米訂栴}”很容易列出一條遞推式而得到解決。假設(shè)第N個月的兔子數(shù)目是F(N)，我們有：這是因為每月的大兔子數(shù)目一定等于上月的兔子總數(shù)，而每個月的小兔子數(shù)目一定等于上月的大兔子數(shù)目(即前一個月的兔子的數(shù)目)。由上述的遞推式我們可以設(shè)計出遞歸程序。遞歸程序的特點是獨立寫出一個函數(shù)(或子過程)，而這個函數(shù)只對極簡單的幾種情況直接給出解答，而在其余情況下通過反復(fù)的調(diào)用自身而把問題歸結(jié)到最簡單的情況而得到解答?？罩屑佑驼荆鹤远x函數(shù)的定義格式:Function procedurename(arguments) As typeStatementsEnd Function其中的procedurename是函數(shù)名，arguments是函數(shù)中的參數(shù)表，type是函數(shù)返回值的數(shù)據(jù)類型，表示可有可無的部分，statements是過程中的代碼調(diào)用函數(shù)的格式：procedurename(arguments)(3)編寫程序。窗體中開設(shè)一個文本框Textl用于填人月數(shù)N，設(shè)置命令框Commandl，點擊它即執(zhí)行程序求出第N月的兔子數(shù)。然后用文本框Text2輸出答案。 文本框2 根據(jù)遞推式可以寫出遞歸程序如下： 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 Command1_Click() N = Val(Text1.Text) Text2.Text = 第 & N & 月的兔子數(shù)目是： & Fib(N)End Sub(4)調(diào)試程序因為這個算法的效率不高，建議在調(diào)試程序時月份數(shù)不要大于40。圖4-5(4)斐波那契兔子程序運行結(jié)果圖(5)檢測結(jié)果挑戰(zhàn)自我：（以下部分由學(xué)生自己完成）(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_Click() Dim n As Integer n = Val(InputBox(請輸入正整數(shù)N：, 求N的階乘) Print 輸入的正整數(shù)是; n; Print ，階乘是; F(n)End Sub圖4-5(5)求階乘程序的運行結(jié)果圖(2)對一正整數(shù)N，用數(shù)字l和2組成一條加法算式，使其和為N，共可以列出多少條不同的式子？(“l(fā)+2”和“2+1”看作是不同的式子)。算法設(shè)計：假設(shè)和為N時可列式子的方法數(shù)是F(N)，那么第一個加數(shù)可選擇1或2。當(dāng)?shù)谝粋€加數(shù)為1時剩下加數(shù)的和為N一1，故方法數(shù)為F(N一1)；當(dāng)?shù)谝粋€加數(shù)為2時，剩下加數(shù)的和為N-2，故方法數(shù)為F(N-2)。于是可以得到如下式子：這是一個典型的遞歸算法，參考程序如下：參考程序如下：Function F(ByVal n As Integer) As Long If n = 2 Then F = n Else F = F(n - 1) + F(n - 2)End FunctionPrivate Sub Form_Click() Dim n As Integer n = Val(InputBox(請輸入正整數(shù)N：, 輸入式子的總和) Print 當(dāng)總和是; n; 時 Print 可以列出不同的由1和2組成的加法式子; F(n); 條End Sub圖4-5(6)書上P137練習(xí)2程序運行結(jié)果圖(3)羅光明在上樓梯時，有時一步一級樓梯，有時一步兩級。如果樓梯有N級，他上完這N級樓梯有多少種不同的方法？設(shè)計算法假設(shè)樓梯級數(shù)為N時的方法數(shù)是F(N)，那么第一步可選擇1或2級樓梯。當(dāng)?shù)谝徊綖?級時剩下樓梯的級數(shù)為N-1，故方法數(shù)為F(N-1)；當(dāng)?shù)谝徊綖?級時，剩下樓梯的級數(shù)為N-2，故方法數(shù)為F(N-2)。于是可以得到如下式子：這是一個典型的遞歸算法，參考程序如下：程序如下：Function F(ByVal n As Integer)As Long If n=2 Then F=n Else F=F(n-1)+F(n-2)End Functi 0nPrivate Sub Form_Click() Dim n As Integer n=Val(InputBox(請輸入樓梯級數(shù)N：，輸人樓梯級數(shù)) Print 當(dāng)樓梯級數(shù)；n；時， Print 可以有；F(n)；種不同的上樓梯方法。End Sub同學(xué)們比較一下你們所做的練習(xí)(2)和(3)的程序代碼，不知同學(xué)們有沒有發(fā)現(xiàn)一個有趣的現(xiàn)象？為什么會這樣？本節(jié)小結(jié)：遞歸算法的特點遞歸過程一般通過函數(shù)或子過程來實現(xiàn)。遞歸算法：在函數(shù)或子過程的內(nèi)部，直接或者間接地調(diào)用自己的算法。遞歸算法的實質(zhì)：是把問題轉(zhuǎn)化為規(guī)?？s小了的同類問題的子問題。然后遞歸調(diào)用函數(shù)(或過程)來表示問題的解。遞歸算法解決問題的特點：(1) 遞歸就是在過程或函數(shù)里調(diào)用自身。(2) 在使用遞增歸策略時，必須有一個明確的遞歸結(jié)束條件，稱為遞歸出口。(3) 遞歸算法解題通常顯得很簡潔，但遞歸算法解題的運行效率較低。所以一般不提倡用遞歸算法設(shè)計程序。(4) 在遞歸調(diào)用的過程當(dāng)中系統(tǒng)為每一層的返回點、局部量等開辟了棧來存儲。遞歸次數(shù)過多容易造成棧溢出等。所以一般不提倡用遞歸算法設(shè)計程序。遞歸算法所體現(xiàn)的“重復(fù)”一般有三個要求：一是每次調(diào)用在規(guī)模上都有所縮小(通常是減半)；二是相鄰兩次重復(fù)之間有緊密的聯(lián)系，前一次要為后一次做準(zhǔn)備(通常前一次的輸出就作為后一次的輸入)；三是在問題的規(guī)模極小時必須用直接給出解答而不再進行遞歸調(diào)用，因而每次遞歸調(diào)用都是有條件的(以規(guī)模未達到直接解答的大小為條件)，無條件遞歸調(diào)用將會成為死循環(huán)而不能正常結(jié)束。第二課時：導(dǎo)入：大家玩漢諾塔游戲：圖4-5(7)漢諾塔程序運行界面圖4.5.2 一個應(yīng)用遞歸算法解決的問題經(jīng)典例子問題4-17：傳說在古代印度的貝拿勒斯神廟，有一塊黃銅板上插了3根寶石柱，在其中一根寶石柱自上而下由小到大地疊放著64個大小不等的金盤。一名僧人把這些金盤從一根寶石柱移到另外一根上。僧人在移動金盤時遵守下面3條規(guī)則：第一，一次只能移動一個金盤。第二，每個金盤只能由一根寶石柱移到另外一根寶石柱。第三，任何時候都不能把大的金盤放在小的金盤上。神話說，如果僧人把64個金盤完全地從一根寶石移到了另外一根上，世界的末日就要到了。當(dāng)然，神話只能當(dāng)故事來聽，世界不可以因為個別人的活動而導(dǎo)致末日。不過，從僧人搬完64個金盤所需時間的角度來說，即使僧人每秒都能移動一個金盤，那也得要幾千億年！試設(shè)計程序，模擬移動金盤的過程。(1)分析問題。我們把3根寶石柱分別命名為A、B、C。最初有N個金盤放在A，需要把它們?nèi)堪匆?guī)則移動到B。當(dāng)N=1時，直接把金盤從A搬到B就可以了，1次成功。當(dāng)N2，那么需要利用C柱來過渡。我們假設(shè)已經(jīng)找到一種把N1個金盤從一根柱搬到另外一根柱的方法，那么，我們只要把N1個金盤從A搬到C，然后把最大的金盤從A搬到B，最后把C上的N一1個金盤搬到B就可以了?？窟f歸的思想，我們輕而易舉地完成了整個搬動。(2)設(shè)計算法。我們定義一個過程Hanoi(N，A，B，C)，表示有N個金盤需要從A柱搬到B柱(以C柱為過渡)。那么完成它只需3步： Hanoi(N一1，A，C，B)它的意思是把A柱上的N一1個金盤搬到C柱； AB 它的意思是把一個(最大的)金盤從A柱搬到B柱； Hanoi(N1，C，B，A)它的意思是把c柱上的N一1個金盤搬到B柱?？罩屑佑驼荆哼^程定義的格式：Private Sub procedurename(arguments)statementsEnd Sub其中的procedurename是函數(shù)名，arguments是函數(shù)中的參數(shù)表，statements是過程中的代碼調(diào)用過程的格式：Call procedurename(arguments)Function函數(shù)與Sub過程的幾點區(qū)別： Function函數(shù)可以返回一個值到調(diào)用程序。 一般來說，讓較大的語句或表達式的右邊包含函數(shù)過程名和參數(shù)（returnvalue=function），這就調(diào)用了函數(shù)。 與變量完全一樣，函數(shù)過程有數(shù)據(jù)類型，這就決定了返回值的類型。（如果沒有AS子句，缺省的數(shù)據(jù)類型為Variant。）。 給procedurename自身賦一個值，就可返回這個值。Function函數(shù)返回一個值可成為較大表達式的一部分。(3)編寫程序（引導(dǎo)學(xué)生編寫程序）。根據(jù)所設(shè)計的算法，我們安排窗體如圖4-23： Private Sub Hanoi(n As Integer, ByVal A As String, ByVal B As String, ByVal C As String, t As Long)If n = 1 Then Text3.Text = Text3.Text + A + + B + vbCrLft = t + 1 增加變量t用來統(tǒng)計移動次數(shù)。Else Call Hanoi(n - 1, A, C, B, t) Text3.Text = Text3.Text + A + + B + vbCrLf t = t + 1 Call Hanoi(n - 1, C, B, A, t)End IfEnd SubPrivate Sub Command1_Click() Dim t As Long, n As Integer t = 0 n = Val(Text1.Text) A = A B = B C = C Call Hanoi(n, A, B, C, t) Text2.Text = tEnd Sub(4)測試程序在“金葉數(shù)目”的文本框中輸入4。圖4-5(9)Hanoi結(jié)果示意圖(5)檢測結(jié)果挑戰(zhàn)自我：（以下部分由學(xué)生自己完成）如來不用遞歸，可不可以用其它的解決