1、遞歸算法的實現【基本信息】作者課時1課時單位 【課標要求】（三）算法與問題解決例舉1. 內容標準遞歸法與問題解決（1）了解使用遞歸法設計算法的基本過程。（2）能夠根據具體問題的要求，使用遞歸法設計算法、編寫遞歸函數、編寫程序、求解問題。【教材分析】“算法的程序實現”是算法與程序設計選修模塊第三單元的內容，本節課是“遞歸算法的程序實現”，前面學習了用解析法解決問題、窮舉法解決問題、在數組中查找數據、對數進行排序以及本節的前一小節知識點“什么是自定義函數”的學習，在學習自定義函數的基礎上，學習遞歸算法的程序實現是自定義函數的具體應用，培養學生“自頂向下”、“逐步求精”的意識起著重要的作用。遞歸算法

2、在算法的學習過程中是一個難點，在PASCAL和C語言等程序語言的學習過程中，往往是將其放在“函數與過程”這一章節中來講解的。遞歸算法的實現也是用函數或是過程的自我調用來實現的。從這一點上來講，作者對教材的分析與把握是準確的，思路是清晰的，目標是明確的。【學情分析】教學對象是高中二年級學生，前面學習了程序設計的各種結構，在學習程序設計各種結構的應用過程中培養了用計算機編程解決現實中問題的能力，特別是在學習循環語句的過程中，應用了大量的“遞推”算法。前一節課學習了如何自定義函數，在此基礎上學習深入學習和體會自定義函數的應用。以遞推算法的逆向思維進行求解問題，在學習過程中體會遞歸算法的思想過程。多維

3、度的思考問題和解決問題是提高學生的學習興趣關鍵。遞歸算法的本質是遞推，而遞推的實現正是通過循環語句來完成的。作者準確把握了學生前面的學習情況，對遞歸算法的本質與特征也分析的很透徹，可以說作者對教學任務的分析是很成功的，接來就要看，在成功分析的基礎上作者是如何通過設計教學來解決教學難點的了。【教學目標】知識與技能：理解什么是遞歸算法，學生會用遞歸算法的思想分析問題能夠應用自定義函數方法實現遞歸算法的編程過程與方法：學生參與討論，通過思考、動手操作，體驗遞歸算法的方法情感態度與價值：結合數學中的實例，激發學生的數學建模的意識，培養學生多維度的思考問題和解決問題。教學目標設計的合理、準確。這也是在意

4、料之中的，一般情況下，成功的教學任務分析一定會帶來成功的教學目標設計。【重點難點】重點：理解什么是遞歸算法，學生用遞歸算法的思想分析問題； 應用自定義函數方法實現遞歸算法的編程難點：應用自定義函數方法實現遞歸算法的編程大部分教師在確立教學重、難點時不會給出確立的依據，可能這些依據早就在教師的腦中明確了，也有可能是一筆糊涂賬，只不過是教參上是這樣寫的就照搬過來而已。如果在寫教學重、難點的同時能再給出確立重、難點的依據會令教案更具借鑒意義。本案例的作者雖然沒有寫依據，但由于前面成功的教學任務分析，也就自然確立了教學重、難點。這也是很好的。【教學過程】進程教師活動學生活動設計意圖創設情境課堂導入：

5、今天很高興，特此我給大家準備了一份禮品（精美包裝猴與兔藝術品），你們想知道里面有什么禮物嗎？學生：想 師：好！我們班有一位同學知道里面有什么禮物！(在上課之前事先告訴其中的一個同學)但是他不能就這樣告訴大家，有一個規則可以讓我們知道里面裝的是什么規則是：1.從第一排的第一個同學開始。2.每位同學只問他相鄰的同學，每位同學最多只能被問一次，而且一個同學不能再問第二人，當任何一個同學知道了答案,要求立即告訴曾經問過他的那個同學 (不能告訴其他同學)以此類推。3.一直到得出答案為結束。以游戲規則開展，我想讓第一位同學告訴大家，精裝的禮物是什么？師生共同活動“找答案”使用情境教學法在此活動過程中能讓學

6、生初步從活動中體驗“問題的發與收”從而走進了遞歸的思維模式，為進一步學習遞歸算法埋下伏筆這樣的課堂導入方式是一種令人興奮的方式。令人興奮的原因有兩個：其一，以“活動”的方式來引導學生探討一個問題是學生們非常喜歡的方式，學生喜歡，就會產生強烈的興趣，但還不是學習動機。但因為“活動”與“所要探討的問題”十分的貼切，是問題的典型代表，學生強烈的興趣就會自然而然地轉化為學習動機。這種學習動機的激發方式比我們直白地告訴學生某某知識點有多么多么重要，我們一定要好好學要來的自然有效的多，是我們需要努力借鑒并執之以恒的。其二，由于遞歸算法的學習比較難，直接進行教學對學生的思維能力要求較高，往往達不到預想的效果

7、。但用新穎有趣的活動來引導學生在積極的參與過程中自然地思考老師希望他們思考的問題，并體驗問題解決的過程，就會獲得較好的學習效果和較高的學習效率。以“活動”的方式引導教學的形式雖然很好，但也是比較難設計的。難就難在“活動”的設計一定要能充分恰當地展示要學習的內容和要探討的問題。如果只是為了活動而活動，既浪費了寶貴的課堂教學時間，也降低了課堂教學效率，是非常不可取的。因此，成功的活動設計對教師的要求很高，需要老師有扎實的學科知識功底和豐富的社會閱歷。啟發主體師：前面我們學習了自定義函數，知道函數是為了實現某種功能而編寫的一段相對獨立的程序，并且可以多次的調用。算法描述：function what(

8、student)如果我知道答案，那么我就告訴你否則，我要問下一位同學再告訴你end function討論活動過程，總結游戲規則，了解活動規律，并將活動過程進行算法描述分析問題確定方案,培養學生思維程序化，為下面新學習遞歸算法做好移植準備這一部分的設計較之于前一段，立刻顯得平淡，缺乏“熱鬧”。然而，這看似平淡的教學過程卻是畫龍點睛之筆。如果沒有這一段教學的及時總結，對前一“活動”過程思維上的提升，那前面的活動就只能流于形式、止步于“熱鬧”了。因此，我們在用“活動”的方式引入教學之后，要注意及時總結活動并提升到所要探討的問題，這樣才算完成了教學。活動的開展，目的也是為了讓學生能較容易地掌握新知進行

9、鋪墊并對問題進行深入思考。學習新知展示題：小猴吃桃:    有一天小猴子摘若干個桃子,當即吃了一半還覺得不過癮,又多吃了一個。第二天接著吃剩下桃子中的一半，仍覺得不過癮又多吃了一個，以后小猴子都是吃尚存桃子一半多一個。到第10天早上小猴子再去吃桃子的時候，看到只剩下一個桃子。問小猴子第一天共摘下了多少個桃子?1.鼓勵學生進行討論，共同尋找答案或解決方法2.師生共同分析題： 以4位同學排成了行，（設從行的后面開始的第一位同學知道第10的桃子數（1個），倒數第二位同學知道第9天的桃子數是）從教師提問排在前面第一位（第7天）的同學，你知道，你今天的桃子數有多少？討論、比較、分析、

10、歸納實例教學，選擇“小猴吃桃”這一題的目的是為了簡化教材“裴波那契”數列的多函數調用，回避問題分析的復雜性較大的特點，從而使得重點難點得以輕松的突破。 目的是討論出，只有倒數第一位同學知道，其他有同學都不知道，但是他只要知道他后一位同學的桃子數就可以求出本人所具有的桃子數，（后同學的桃子數+1）*2就是本人的桃子數。看來作者真是一個善于通過“活動”的方式來完成教學的“高手”，在降低了分析問題的難度以后，再一次用活動的方式來引導學生來分析問題，這是一種真正意義上的循循善誘，比教師不厭其煩地教給學生十遍公式要來的高效的多。建立數學模型：假設第n,n<10天的桃子數為tao(n)那么 tao=

11、1 n=1tao(n)=(tao(n+1)+1)*2 n<10推導數學建模 我們能不能這樣設一個函數：算法描述： function你有多少桃子？（第幾天） 如果我第10天，那么我就有一個桃子。 否則，我的桃子數=（前一天的桃子數+1）*2 end function學生進行算法描述培養學生養成良好的編程習慣 還是的，在“活動”過后要及時的總結與提升。先在分析的基礎上建立數學模型，再用偽代碼來描述，嚴格按計算機解決問題的基本過程來展開課堂教學，不斷培養與強化學生良好的編程習慣。 學生編程實現：Function tao(ByVal days As Integer) As IntegerIf d

12、ays = 10 Thentao = 1Elsetao = (tao(days + 1) + 1) * 2End IfEnd Function分析算法的實現過程學生編程實現示圖協助學生算法實現過程的始末思維，培養學生的編程和調試程序能力，讓學生獲得成功的體檢再用示圖的方式來幫助學生進行思維，降低學生思維的難度（并沒有降低思維的質量），從而提高教學效率。再讓學生動手編寫代碼，實踐計算機解決問題基本過程的最后一步。至此，用遞歸算法解決“猴子摘桃”問題的全過程完成了。自主構建我們再來看第二題：（學生閱讀教材P68，讓學生閱讀教材的“裴波那契”，培養學生的自學能力、和知識遷移建構自我的知識體系）裴波那

13、契（Fibonacci leonardo，約1170-1250）是意大利著名數學家在他的著作算盤書中許多有趣的問題，最富成功的問題是著名的“兔子繁殖問題”： 如果每對兔子每月繁殖一對子兔，而子兔在出生后第二個月就有生殖能力，試問第一月有一對小兔子第十二月時有多少對兔子？1、1、2、3、5、8、13、21假設第n個月的兔子數目為f(n)，那么 f(n)=F(n-1)+f(n-2) 當n3， f(1)=f(2)=1 討論得出算法描述Function有多少對兔子（第幾月） 如果是第一月或第二月，那么就有一對兔子。 否則，（本月）兔子數=（本月-1）月的兔子數+（本月-2）月的兔子數end Funct

14、ionFunction tu(ByVal month As Integer) As IntegerIf month = 1 Or month = 2 Thentu = 1Elsetu = tu(month - 1) + tu(month - 2)End IfEnd Function閱讀思考、分析、討論，編程實現。 尊重學生的個體發展，讓學生進行自主探究學習，使用學主動、積極的學習新知識，培養他們的自學能力。培養學生分析問題、解決問題能力，煅練學生“數學建模”建構主義的學習觀認為：學習不是被動接收信息，而是主動地建構意義，以自己原有的知識經驗為基礎對外部信息進行主動地選擇、加工和處理，人而獲得自

15、己的意義過程。在學生經歷了上一問題解決的完整過程之后，再拋出較難的問題，并讓學生自主完成。一方面，學生有了前面的基礎，自主完成稍難一點問題的解決是完全可能的，另一方面，通過問題的“變式”，強化了新知，也訓練了學生獨立思考，分析解決問題的能力。深化知識閱讀教材的循環結構實現，比較討論兩種算法的區別和特點學生討論培養學生分析問題、歸納、梳理知識的能力，通過兩種算法的對比，讓學生深入體會遞歸算法的魅力。加深對本節課所學知識的理解。通過比較兩種算法的不同來加深學生對遞歸算法的理解是一種比較好的方法。不過，可惜的是這里沒能看到學生討論并總結不同的過程與結論。課堂小結我們今天所學習的算法是“遞歸算法”，我

16、們談談什么是遞歸算法，遞歸算法有什么特點。師生討論，共同小結：1. 遞歸算法是數值層層調用實現的，函數先由上向下調用，當達到最底層后，再將函數值層層向上返回。(遞下去，收回來，簡稱：遞歸)2. 必須有個結束條件（有個該收回來的條件）3. 可讀性強4. 計算機資源耗費大，所以效率比較底（常駐內存的數據比較多）達成共識最后的課堂小結是統一學生思維結果的過程，這在活動性課堂教學中是必不可少的，它能幫助學生將發散的思維歸結在教學的核心目標上，不至于讓學生在一節課下來，感覺不知道學到了什么（其實學到了很多，只是沒能總結出來）。然而，我們也看到，在小結的第4點上，在整個教學過程中，并沒有給予關注。所以這個

17、結論只是教師直接給出的，如果也能通過活動的方式來讓學生體會到遞歸算法的低效就更好了。當然，這部分也許是下一節課的教學內容，本節課的小結只是一個提示。還有一種可能，就是在前面的算法比較環節中讓學生體驗到了遞歸算法的低效。但一般來說，如果要讓學生通過問題來體驗遞歸算法的低效性，就一定要通過比較的方法，而且需要足夠的課時，相信，這一點在本節課上是難以實現的。布置作業1.N！（用遞歸算法編程實現）2.求1+2+3+4+5N （用遞歸算法編程實現）3.用遞推算法實現“猴子吃桃”問題求解鞏固和發展本節課的學習內容。【教學反思】從游戲的方式導入活動，充分的調動學生的思維，漸漸的走入了“遞歸的思維”模式，從而

18、引出“猴子吃桃”，使用的前面活動(禮物是什么?)的思維，誘導學生進入了“遞歸”思想解題。學生閱讀教材范例“裴波那契”，培養學生的自學能力和知識遷移建構自我的知識體系。內化遞歸算法的實現，再由遞歸思維的逆向思維討論“遞推”的算法，進行比較計算機資源的耗費高，可讀性差。為下一步導出結論做好了鋪墊。學好本節課的前提是：懂得自定義函數的使用方法，學生對自定義函數的理解程度，是本節課效果是否得以完成的關鍵。【案例分析】本案例語言流暢，結構清晰，對教材與學情的分析準確、到位，對教學目標和教學重、難點設計準確、合理。本案例覆蓋的是程序設計中“遞歸法與問題解決”這一知識點，適合用于這一知識點的第一節課。本案例能夠通過“活動”的形式，使學生了解使用遞歸法設計算法的基本過程，使學生能夠根據具體問題的要求，使用遞歸法設計算法、編寫遞歸函數、編寫程序、求解問題。本案例能夠通過“活動”（或游戲）的方式來導入教學，展開教學。而且能關注到培養學生自主學習探究能力的培養，并通過降低討論問題的復雜程度和圖示的方法來引導和幫助學生進行思考。再通過同一問題用不同算法來實現后的比較，來帶領學生總結遞歸算法的優缺點。這些都是在比較難的算法教學內容的教學過程中，突破教學重難點的好的方法，很值