第4章算法與數(shù)據(jù)結(jié)構(gòu)4.3遞歸法教學(xué)設(shè)計(jì)教學(xué)背景信息科技是現(xiàn)代科學(xué)技術(shù)領(lǐng)域的重要部分，主要研究以數(shù)字形式表達(dá)的信息及其應(yīng)用中的科學(xué)原理、思維方法、處理過(guò)程和工程實(shí)現(xiàn)。當(dāng)代高速發(fā)展的信息科技對(duì)全球經(jīng)濟(jì)、社會(huì)和文化發(fā)展起著越來(lái)越重要的作用。義務(wù)教育信息科技課程具有基礎(chǔ)性、實(shí)踐性和綜合性，為高中階段信息技術(shù)課程的學(xué)習(xí)奠定基礎(chǔ)。信息科技課程旨在培養(yǎng)科學(xué)精神和科技倫理，提升自主可控意識(shí)，培育社會(huì)主義核心價(jià)值觀，樹(shù)立總體國(guó)家安全觀，提升數(shù)字素養(yǎng)與技能。教材分析本節(jié)課的教學(xué)內(nèi)容選自人教/地圖出版社選擇性必修1數(shù)據(jù)與數(shù)據(jù)結(jié)構(gòu)第4章算法與數(shù)據(jù)結(jié)構(gòu)4.3遞歸法。學(xué)情分析此節(jié)課針對(duì)的對(duì)象是高二年級(jí)的學(xué)生。學(xué)生學(xué)習(xí)過(guò)信息技術(shù)基礎(chǔ)知識(shí)，對(duì)計(jì)算機(jī)、網(wǎng)絡(luò)、物聯(lián)網(wǎng)等技術(shù)有基本了解:已經(jīng)學(xué)習(xí)了Python語(yǔ)言的基本概念，并掌握了基本的結(jié)構(gòu)和算法;對(duì)現(xiàn)代生活中的信息系統(tǒng)有所觀察和積累。本章通過(guò)“編寫(xiě)對(duì)弈程序”項(xiàng)目，引領(lǐng)同學(xué)們開(kāi)展自主選題，建議從確定主題、選擇數(shù)據(jù)結(jié)構(gòu)、設(shè)計(jì)算法和編寫(xiě)程序等幾個(gè)方面入手，完成小組項(xiàng)目，發(fā)布應(yīng)用程序，詳細(xì)記錄研究過(guò)程并形成研究報(bào)告。教學(xué)目標(biāo)1.體驗(yàn)使用遞歸法解決問(wèn)題的過(guò)程，解決實(shí)際問(wèn)題，提升計(jì)算思維能力。2.理解迭代法和遞歸法的異同，利用迭代或遞歸思想指導(dǎo)算法設(shè)計(jì)。教學(xué)重點(diǎn)與難點(diǎn)教學(xué)重點(diǎn):體驗(yàn)使用遞歸法解決問(wèn)題的過(guò)程，解決實(shí)際問(wèn)題，提升計(jì)算思維能力。教學(xué)難點(diǎn):理解迭代法和遞歸法的異同，利用迭代或遞歸思想指導(dǎo)算法設(shè)計(jì)。教學(xué)方法與教學(xué)手段案例分析法、講授法、任務(wù)驅(qū)動(dòng)法。教學(xué)過(guò)程問(wèn)題導(dǎo)入體驗(yàn)探索漢諾塔問(wèn)題漢諾塔問(wèn)題是由一位法國(guó)數(shù)學(xué)家在19世紀(jì)提出的，直到現(xiàn)在，簡(jiǎn)化版的漢諾塔玩具在玩具店中仍然隨處可見(jiàn)。漢諾塔的假設(shè)是：在一個(gè)銅板上，插著三根寶石針，分別被編號(hào)為a、b、c。在a針上，從下到上放置了由大到小的64個(gè)金片，要把這些金片借助b針，從a針全部移動(dòng)到c針。移動(dòng)規(guī)則是：一次只能移動(dòng)一片，并且無(wú)論在哪一根針上，小片必須放置在大片上面。思考：1.若a針上只有3個(gè)金片，如圖4.3.1所示，如何將3個(gè)金片從a針移到c針？2.如果a針上有4個(gè)金片，如何將4個(gè)金片從a針移到c針？如何設(shè)計(jì)算法實(shí)現(xiàn)這個(gè)過(guò)程？遞歸法的概念與特征生活中有這樣一種蔬菜——洋蔥，它的可食用部分是一層一層包裹起來(lái)的，僅從外觀上看，無(wú)從判斷它的內(nèi)里。同樣，有這樣一種問(wèn)題，也是層層包裹起來(lái)的，我們只有像“剝洋蔥”一樣，層層分解，才能把一個(gè)復(fù)雜問(wèn)題轉(zhuǎn)化為簡(jiǎn)單問(wèn)題來(lái)解決。思考活動(dòng)小球的排列與階乘有5個(gè)顏色各不相同的小球，將這5個(gè)小球按順序排列在一起。思考：共有多少種排列方法？小球排列是數(shù)學(xué)中典型的排列問(wèn)題，根據(jù)數(shù)學(xué)知識(shí)，可以得到共有種排列方法。5!即5的階乘。一個(gè)自然數(shù)的階乘是所有小于及等于該數(shù)的正整數(shù)的積，并且規(guī)定0!=1。若f(n)=n!，根據(jù)階乘的定義，可以得出：n!=n×(n1)×...×5×4×3×2×1，即1!=1，2!=2×1，3!=3×2×1，4!=4×3×2×1，...分析這些算式，可以發(fā)現(xiàn)它們存在著如下關(guān)系：1!=1，2!=2×1!，3!=3×2!，4!=4×3!，...，n!=n×(n1)!。因而，為了計(jì)算f(5)，要先計(jì)算f(4)；而要計(jì)算f(4)，又得先計(jì)算f(3)；欲計(jì)算f(3)，又得先計(jì)算f(2)；計(jì)算f(2)，又得先計(jì)算f(1)。f(1)的值為1!=1。這個(gè)計(jì)算過(guò)程，如圖4.3.2（參見(jiàn)教材P128）所示。在上述程序中，函數(shù)f又調(diào)用了函數(shù)f，這種通過(guò)直接或間接地調(diào)用自身來(lái)解決問(wèn)題的方法被稱為遞歸。使用遞歸算法解決問(wèn)題需要具備兩個(gè)要件：遞歸定義和遞歸的邊界條件。確定遞歸定義使用遞歸解決的問(wèn)題都可以通過(guò)同一套規(guī)則（即相同的程序）轉(zhuǎn)化為比該問(wèn)題更為簡(jiǎn)單的子問(wèn)題，這套規(guī)則被稱為該問(wèn)題的遞歸定義或遞歸公式。例如，f(n)=n×f(n1)就是計(jì)算階乘的遞歸公式。確定遞歸的邊界條件經(jīng)過(guò)不斷縮小問(wèn)題規(guī)模，問(wèn)題最終能夠得以解決。如圖4.3.2（參見(jiàn)教材P128）所示，5!經(jīng)過(guò)不斷簡(jiǎn)化，最終轉(zhuǎn)化為求1!，而1!=1。這種能直接得到結(jié)果，從而終止遞歸的情況，稱為遞歸的邊界條件。實(shí)踐活動(dòng)再談斐波那契數(shù)列在第2章學(xué)習(xí)數(shù)組時(shí)我們知道，斐波那契數(shù)列指的是這樣一個(gè)數(shù)列：1，1，2，3，5，8，13，21，34，...即從第3項(xiàng)開(kāi)始，每一項(xiàng)都是前面兩項(xiàng)的和。如果用f(n)表示計(jì)算斐波那契數(shù)列的函數(shù)，那么，f(n)=f(n1)+f(n2)（n＞2，n∈N）。請(qǐng)根據(jù)斐波那契數(shù)列的遞歸定義，參考圖4.3.2，畫(huà)出其遞歸過(guò)程的示意圖，并編寫(xiě)計(jì)算斐波那契數(shù)列的程序。不僅是在數(shù)學(xué)問(wèn)題中存在遞歸，生活中也存在很多類似遞歸的現(xiàn)象，如圖4.3.4所示的玩具套娃。只要認(rèn)真觀察，就能發(fā)現(xiàn)更多生活中的遞歸，甚至還能創(chuàng)造更多的遞歸，體會(huì)生活之美。遞歸法的應(yīng)用使用遞歸法可以解決許多復(fù)雜困難的問(wèn)題，這些問(wèn)題有一些共同特征：通過(guò)一套相同的規(guī)則，最終轉(zhuǎn)化為一個(gè)相對(duì)比較簡(jiǎn)單的小問(wèn)題，然后再一步一步地返回，最終使問(wèn)題得以解決。本節(jié)體驗(yàn)探索中的漢諾塔就是這樣一個(gè)問(wèn)題。要想使用遞歸法解決問(wèn)題，首先得證明這個(gè)問(wèn)題的每次轉(zhuǎn)化都能滿足同一套規(guī)則。思考活動(dòng)用遞歸法解決漢諾塔問(wèn)題本節(jié)的體驗(yàn)探索中提出了3個(gè)金片和4個(gè)金片的漢諾塔，如果用迭代法解決，將會(huì)十分復(fù)雜，甚至無(wú)從下手。思考：漢諾塔問(wèn)題能否用遞歸法解決？請(qǐng)說(shuō)明理由。以漢諾塔問(wèn)題為例，說(shuō)明使用遞歸法解決問(wèn)題的一般步驟。1.推斷問(wèn)題可用遞歸法解決對(duì)于a上的64個(gè)金片，如果能把前63個(gè)金片借助c移動(dòng)到b，那么就可以將a上的第64個(gè)金片直接由a移動(dòng)到c。這樣64個(gè)金片的移動(dòng)問(wèn)題轉(zhuǎn)化為解決63個(gè)金片的移動(dòng)問(wèn)題。對(duì)于b上的63個(gè)金片，如果能把前62個(gè)金片借助c移動(dòng)到a，那么就可以將b上的第63個(gè)金片直接由b移動(dòng)到c。這樣63個(gè)金片的移動(dòng)問(wèn)題轉(zhuǎn)化為解決62個(gè)金片的移動(dòng)問(wèn)題。......可以看出，漢諾塔問(wèn)題是一個(gè)典型的遞歸問(wèn)題。遞歸的終止條件是1個(gè)金片的移動(dòng)。2.確定遞歸定義對(duì)于a上的n個(gè)金片，需要把a(bǔ)上面的n1個(gè)金片借助c移動(dòng)到b上，a上面僅剩1個(gè)金片，將這個(gè)金片由a移動(dòng)到c上即可。然后再將b上的n1個(gè)金片，借助a移動(dòng)到c上，就完成了金片移動(dòng)。這是漢諾塔遞歸定義的文字表述。如果用Hanoi表示求解漢諾塔問(wèn)題的函數(shù)，那么函數(shù)Hanoi與金片的數(shù)量n以及a、b、c三根針的位置有關(guān)。用Hanoi(n,a,b,c)表示n個(gè)金片從a通過(guò)b移動(dòng)到c，move(a,b)表示金片從a移動(dòng)到b，那么第n個(gè)金片的移動(dòng)過(guò)程應(yīng)如下：將a上的n1個(gè)金片通過(guò)c移動(dòng)到b，即Hanoi(n1,a,c,b)；將a上最后一個(gè)金片移動(dòng)到c，即move(a,c)；將b上的n1個(gè)金片通過(guò)a移動(dòng)到c，即Hanoi(n1,b,a,c)。對(duì)于n=1的情況，只需move(a,c)，由此我們就得到了漢諾塔的遞歸定義。實(shí)踐活動(dòng)編程解決漢諾塔問(wèn)題1.編程實(shí)現(xiàn)漢諾塔問(wèn)題的解決，運(yùn)行程序，并驗(yàn)證其正確性。提示：move(a,b)在屏幕上輸出“由a移動(dòng)到b”。2.改變漢諾塔程序的輸入?yún)?shù)，觀察程序的運(yùn)行結(jié)果，推斷金片的移動(dòng)次數(shù)與金片數(shù)之間的關(guān)系公式，推算64個(gè)金片的移動(dòng)次數(shù)。折半查找順序查找一般常用于被查找對(duì)象所在序列是無(wú)序的或排序情況未知的情況。實(shí)際生活中，我們經(jīng)常遇到這樣的情況：被查找對(duì)象所在序列是有序的。例如，新華字典中的漢字是按照漢語(yǔ)拼音順序排列的。如果在字典中查找“希”字，我們通常不會(huì)從字典的第一頁(yè)開(kāi)始找起，而是先大致翻到后面的位置，如果找不到就繼續(xù)推測(cè)是往前翻還是往后翻，而且每次翻動(dòng)的頁(yè)數(shù)越來(lái)越少，直到找到為止。實(shí)踐活動(dòng)為“單詞管理程序”增加查找功能小明經(jīng)過(guò)100天的學(xué)習(xí)掌握了5000多個(gè)英文單詞。為了鞏固記憶、掌握新單詞，他打算編寫(xiě)一個(gè)管理單詞的小程序，小程序中包括添加新單詞和查找單詞等多個(gè)功能。請(qǐng)使用Python語(yǔ)言編寫(xiě)一個(gè)使用折半查找的程序，幫助他實(shí)現(xiàn)查找單詞的功能。項(xiàng)目實(shí)施完成項(xiàng)目，匯報(bào)交流一、項(xiàng)目活動(dòng)完成確定的主題項(xiàng)目，發(fā)布程序，撰寫(xiě)研究報(bào)告，小組交流展示。在學(xué)習(xí)遞歸法后，綜合運(yùn)用遞歸、迭代、解析和枚舉等各種方法，查閱相關(guān)的Python資料，完成各小組的程序。以五子棋對(duì)弈項(xiàng)目為例，制作完成時(shí)，發(fā)布應(yīng)用程序，界面如圖4.3.10所示。改變編寫(xiě)的程序中的參數(shù)，反復(fù)調(diào)試，測(cè)試程序的健壯性。有條件應(yīng)當(dāng)使用多種操作系統(tǒng)測(cè)試制作完成的應(yīng)用程序。各小組在完成作品的基礎(chǔ)上，形成主題研究報(bào)告，涵蓋設(shè)計(jì)意圖與特色、設(shè)計(jì)過(guò)程、主要算法和程序、體會(huì)與經(jīng)驗(yàn)等各個(gè)方面。召開(kāi)班級(jí)展示會(huì)，各小組展示、交流各自編寫(xiě)的程序，講評(píng)項(xiàng)目研究報(bào)告，取長(zhǎng)補(bǔ)短。二、項(xiàng)目檢查1.完成主題項(xiàng)目后，正式發(fā)布程序，程序可正確運(yùn)行，能實(shí)現(xiàn)項(xiàng)目功能。2.整理主題學(xué)習(xí)項(xiàng)目研究報(bào)告，召開(kāi)各小組交流展示會(huì)?？偨Y(jié)評(píng)價(jià)1.總結(jié)本章的核心概念與關(guān)鍵能力。2.根據(jù)自己的掌握情況填寫(xiě)下表。學(xué)習(xí)內(nèi)容掌握程度將需要解決的問(wèn)題步驟化□不了解□了解□理解為需要解決的問(wèn)題選取適當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)□不了解□了解□理解設(shè)計(jì)迭代算法解決問(wèn)題□不了解□了解□理解設(shè)計(jì)遞歸算法解決問(wèn)題□不了解□了解□理解課后作業(yè)1.對(duì)于有序數(shù)組而言，查找算法一定要折半嗎？能不能折三分之一、四分之一或者折更多呢？此外，還有黃金分割查找等方法。通過(guò)互聯(lián)網(wǎng)查閱資料，并編寫(xiě)程序?qū)崿F(xiàn)黃金分割查找。2.如果數(shù)據(jù)是用二叉樹(shù)組