遞歸算法與遞歸程序教學(xué)設(shè)計

1、遞歸算法與遞歸程序岳西中學(xué)：崔世義一、教學(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)入 遞歸問題，從用普通程序解決斐波 那契的兔子問題入手，

2、引導(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ù)?遞歸程序。2、教學(xué)難點(1) 遞歸過程思路的

3、建立。(2) 判斷冋題是否適于 遞歸解法。(3) 正確寫出遞歸程序。三、教學(xué)環(huán)境1、教材處理教材選自浙江省普通高中信息技術(shù)選修：算法與程序設(shè)計第五章，原教材的編排是以本節(jié)以斐波那契的兔子問題引人，導(dǎo)出遞歸算法，從而自定義了一個以遞歸方式解決的函數(shù)過程。然后利用子過程解決漢諾塔的經(jīng)典 問題。教材經(jīng)處理后，讓同學(xué)們玩漢諾塔的游戲，導(dǎo)入 遞歸問題，從用普通程 序解決斐波那契的兔子問題入手，引導(dǎo)學(xué)生用自定義了一個以 遞歸方式解決 的函數(shù)過程解決問題，同時讓同學(xué)們做三個 遞歸練習(xí)，鞏固提高。然后讓學(xué) 生做練習(xí) 和練習(xí) 這兩道題目的形式相差很遠，但方法和答案卻都是完 全相同的練習(xí)，體會其中的奧妙，加深對

4、遞歸算法的了解。最后用子過程解 決漢諾塔的經(jīng)典問題。教學(xué)方法采用講解、探究、任務(wù)驅(qū)動和學(xué)生自主學(xué)習(xí)相結(jié)合2、預(yù)備知識學(xué)生已掌握了用計算機解決問題的過程，掌握了程序設(shè)計基礎(chǔ)，掌握了解析法、窮舉法、查找法、排序法設(shè)計 程序的技巧。四、教學(xué)過程導(dǎo)入：大家玩漢諾塔游戲：這個游戲盤子在A、B C三根柱子上不停運動，有沒有規(guī)律，和你在照過鏡子時遇到的情況相同嗎當(dāng)你往鏡子前面一站，鏡子里面就有一個你的像。但你試過兩面鏡子一起 照嗎如果甲、乙兩面鏡子相互面對面放著，你往中間一站，嘿，兩面鏡子里都有 你的千百個“化身” ！為什么會有這么奇妙的現(xiàn)象呢原來，甲鏡子里有乙鏡子的 像，乙鏡子里也有甲鏡子的像，而且這樣反

5、反復(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 Th

6、e n c = 1 Else a = 1: b = 1 i = 3 c = a + b : a = b : b = c i=i+1,如果i n則返回 結(jié)束參考程序如下：Private Sub Comma nd1_Click()n = VaiIf n 3 The n c = 1 Else a = 1: b = 1For i = 3 To nc = a + ba = bb = cNext i=第&n& 月的兔子數(shù)目是：& cEnd Sub開動腦筋：我們有沒有更簡單的方法解決該問題呢從斐波那契的兔子問題看遞歸算法1 斐波那契的兔子問題子分析冋題。我們可以根據(jù)題意列出表4-3來解決這個問題: 表43兔

7、子冋題分析表1月2月3月4月5月6月7月8月9月10月11月12月小 兔111235813213455大 兔1123581321345589合計1123581321345589144這個表格雖然解決了斐波那契的兔子問題(年底時兔子的總數(shù)是144只), 但仔細(xì)觀察一下這個表格，你會發(fā)現(xiàn)兔子的數(shù)目增長得越來越快，如果時間再長， 只用列表的方法就會有困難。(例如，你愿意用列表的方法求出5年后兔子的數(shù) 目嗎)我們需要研究表中的規(guī)律，找出一般的方法，去解決這個問題。 交流仔細(xì)研究表4-8，你有些什么發(fā)現(xiàn)每一個月份的大兔數(shù)、小兔數(shù)與上一個月 的數(shù)字有什么聯(lián)系，能肯定這個規(guī)律嗎恭喜你，你快成功了設(shè)計算法?！?/p>

8、兔子問題”很容易列出一條 遞推式而得到解決。假設(shè)第N個月的兔子數(shù)目是 F(N)，我們有：這是因為每月的大兔子數(shù)目一定等于上月的兔子總數(shù)，而每個月的小兔子數(shù)目一定等于上月的大兔子數(shù)目(即前一個月的兔子的數(shù)目)。由上述的遞推式我們可以設(shè)計出遞歸程序。遞歸程序的特點是獨立寫出一個 函數(shù)(或子過程)，而這個函數(shù)只對極簡單的幾種情況直接給出解答， 而在其余情 況下通過反復(fù)的調(diào)用自身而把問題歸結(jié)到最簡單的情況而得到解答。刖面學(xué)過： 自定義函數(shù)的定義格式：Function 函數(shù)名(參數(shù)表 )As type過程中的代碼End Fun cti on調(diào)用函數(shù)的格式：函數(shù)名(參數(shù)表)(3) 編寫程序。窗體中開設(shè)一個

9、文本框Textl用于填人月數(shù)N,設(shè)置命令框Commandl點擊 它即執(zhí)行程序求出第N月的兔子數(shù)。然后用文本框Text2輸出答案。根據(jù)遞推式可以寫出遞歸程序如下：Function Fib(ByVal N As Integer) As LongIf N 3 Then Fib = 1 Else Fib = Fib(N - 1) + Fib(N - 2) End Fun cti onPrivate Sub Comma nd1_Click()N = Val=第& N & 月的兔子數(shù)目是：& Fib(N)End Sub調(diào)試程序 因為這個算法的效率不高，建議在調(diào)試 程序時月份數(shù)不要大于40。一個應(yīng)用遞歸算法

10、解決的問題經(jīng)典例子問題4-17 :傳說在古代印度的貝拿勒斯神廟，有一塊黃銅板上插了3根寶石柱，在其中一根寶石柱自上而下由小到大地疊放著64個大小不等的金盤。一名僧人把這些金盤從一根寶石柱移到另外一根上。僧人在移動金盤時遵守下面3條規(guī)則：第一，一次只能移動一個金盤。第二，每個金盤只能由一根寶石柱移到另外一根寶石柱。第三，任何時候都不能把大的金盤放在小的金盤上。神話說，如果僧人把64個金盤完全地從一根寶石移到了另外一根上，世界 的末日就要到了。當(dāng)然，神話只能當(dāng)故事來聽，世界不可以因為個別人的活動而 導(dǎo)致末日。不過，從僧人搬完64個金盤所需時間的角度來說，即使僧人每秒都 能移動一個金盤，那也得要幾千

11、億年！(1) 分析問題。我們把3根寶石柱分別命名為A、B、C。最初有N個金盤放在A,需要把它 們?nèi)堪匆?guī)則移動到Bo當(dāng)N=1時，直接把金盤從A搬到B就可以了，1次成功。 當(dāng)NA2,那么需要利用C柱來過渡。我們假設(shè)已經(jīng)找到一種把 N1個金盤從一 根柱搬到另外一根柱的方法，那么，我們只要把N-1個金盤從A搬到C,然后把最大的金盤從A搬到B,最后把C上的N一一 1個金盤搬到B就可以了?？窟f歸 的思想，我們輕而易舉地完成了整個搬動。設(shè)計算法。我們定義一個過程Hanoi(N，A，B，C)，表示有N個金盤需要從A柱搬到B 柱(以C柱為過渡)。那么完成它只需3步： Hanoi(N 1, A，C, B)它的意

12、思是把A柱上的N 1個金盤搬到C柱; A-B它的意思是把一個(最大的)金盤從A柱搬到B柱； Hanoi(N 1, C, B, A)它的意思是把c柱上的N 1個金盤搬到B柱。前面已經(jīng)學(xué)過：過程定義的格式：Private Sub 過程名(參數(shù)表)代碼End Sub調(diào)用過程的格式：Call過程名(參數(shù)表)(3)編寫程序(引導(dǎo)學(xué)生編寫程序)。Private Sub Hanoi(n As Integer, ByVai A As String, ByVai B As String, ByVai C As Stri ng, t As Long)If n = 1 The n = + A + + B + vbC

13、rLft = t + 1增加變量t用來統(tǒng)計移動次數(shù)。ElseCall Hanoi(n - 1, A, C, B, t)=+ A + + B + vbCrLft = t + 1Call Hanoi(n - 1, C, B, A, t) End IfEnd SubPrivate Sub Comma nd1_Click() Dim t As Long, n As In teger t = 0n = VaiA = A B = B C = C Call Hanoi(n, A, B, C, t)=tEnd Sub測試程序 在文本框中輸入4算法然后遞歸調(diào)小結(jié)： 遞歸算法的特點 遞歸過程一般通過函數(shù)或子過程來實現(xiàn)。 遞歸算法：在函數(shù)或子過程的內(nèi)部，直接或者間接地調(diào)用自己的 遞歸算法的實質(zhì)：是把問題轉(zhuǎn)化為規(guī)?？s小了的同類問題的子問題 用函數(shù)(或過程)來表示問題的解。 遞歸算法解決問題的特點：(1) 遞歸就是在過程或函數(shù)里調(diào)用自身(2) 在使用遞增歸策略時，必須有一個明確的 遞歸結(jié)束條件，稱為遞歸出口(3) 遞歸算法解題通常顯得很簡潔，但遞歸算法解題的運行效率較低。所以一般 不提倡用遞歸算法設(shè)計(4) 在遞歸調(diào)用的過程當(dāng)中系統(tǒng)為每一層的返回點、局部量等開辟了棧來存儲。遞歸次數(shù)過多容易造成棧