高中信息技術(shù)粵教版高中選修1算法與程序設(shè)計(jì)第四章算法與程序?qū)崿F(xiàn)4.4.5

第四章遞歸算法與遞歸程序 遞歸算法四川省內(nèi)江市第六中學(xué)尤丹【教材分析】“遞歸算法與遞歸程序”是廣東教育出版社《算法與程序設(shè)計(jì)》選修1第四章的內(nèi)容。遞歸算法是計(jì)算機(jī)程序設(shè)計(jì)中的一種重要的算法，是較難理解的算法之一。“遞歸算法”的基本思想：把規(guī)模大的、較難解決的問題變成規(guī)模較小的、易解決的同一問題。規(guī)模較小的問題又變成規(guī)模更小的問題，并且小到一定程度直到可以直接得出它的解，從而得到原來問題的解。本節(jié)課設(shè)置了前置學(xué)習(xí)知識(shí)點(diǎn)：自定義函數(shù)，在學(xué)習(xí)自定義函數(shù)的基礎(chǔ)上，學(xué)習(xí)遞歸算法的程序?qū)崿F(xiàn)是自定義函數(shù)的一種具體應(yīng)用，培養(yǎng)學(xué)生“自頂向下”、“逐步求精”的意識(shí)起著重要的作用。由于教材中的“斐波那契兔子問題”是遞歸的多函數(shù)調(diào)用，遞歸過程較為復(fù)雜，所以本節(jié)課在設(shè)計(jì)時(shí)充分考慮學(xué)情，設(shè)計(jì)一些生活中、數(shù)學(xué)中常見的遞歸問題，讓學(xué)生通過學(xué)習(xí)和反復(fù)的練習(xí)，由淺入深地理解“遞歸算法”，并善于用遞歸思想解決復(fù)雜的遞歸問題。【學(xué)情分析】本節(jié)課授課對(duì)象是高一年級(jí)的學(xué)生。學(xué)生有一定的知識(shí)儲(chǔ)備，有一定的計(jì)算機(jī)操作能力，也具有基本的編程思想。在學(xué)習(xí)《算法與程序設(shè)計(jì)》的過程中，學(xué)習(xí)了程序設(shè)計(jì)的三種基本結(jié)構(gòu)，在學(xué)習(xí)程序設(shè)計(jì)三種基本結(jié)構(gòu)的應(yīng)用過程中培養(yǎng)了學(xué)生用計(jì)算機(jī)編程解決現(xiàn)實(shí)中一些問題的能力,特別是在學(xué)習(xí)循環(huán)語句的過程中，應(yīng)用了大量的“遞推”算法。前一節(jié)課學(xué)習(xí)了如何自定義函數(shù)，在此基礎(chǔ)上深入學(xué)習(xí)和體會(huì)自定義函數(shù)的應(yīng)用。以遞推算法的逆向思維進(jìn)行問題求解，在學(xué)習(xí)過程中體會(huì)遞歸算法的基本思想。多維度的思考問題和解決問題是提高學(xué)生的學(xué)習(xí)興趣關(guān)鍵。同時(shí)學(xué)生通過初中數(shù)學(xué)和高中數(shù)學(xué)的學(xué)習(xí)，對(duì)函數(shù)也有基本的了解和掌握。將函數(shù)知識(shí)與模塊化程序設(shè)計(jì)的思想相結(jié)合，能夠讓學(xué)生在理解“遞歸算法”的基礎(chǔ)上，利用“遞歸思想”解決遞歸問題，也充分體現(xiàn)了STEM教育的多學(xué)科融合思想。【設(shè)計(jì)思路】本堂課設(shè)計(jì)思路是從“找位置”不同的真實(shí)情境出發(fā)，引入課題；以簡單數(shù)學(xué)問題“求階乘”，讓學(xué)生將數(shù)學(xué)問題計(jì)算機(jī)程序化解決，體驗(yàn)從“分析問題”→“設(shè)計(jì)算法”→“編寫程序”→“調(diào)試程序”的求解過程，從而漸進(jìn)式地讓學(xué)生接收遞歸思想，了解遞歸算法的原理。然后通過分析、解決“年齡計(jì)算”、“猴子吃桃”等問題強(qiáng)化、鞏固知識(shí)，學(xué)生通過知識(shí)遷移建構(gòu)自我知識(shí)體系，從而達(dá)到教學(xué)效果。本節(jié)課以信息技術(shù)課程為載體，以“遞歸算法的實(shí)現(xiàn)”為項(xiàng)目，采用項(xiàng)目式教學(xué)法。教師將STEM教育理念融入教學(xué)中，以學(xué)生為主體，教師引導(dǎo)學(xué)生進(jìn)行多學(xué)科融合的學(xué)習(xí)，提升學(xué)生發(fā)現(xiàn)問題和解決問題的能力?！窘虒W(xué)目標(biāo)】1.知識(shí)與技能(1)理解什么是“遞歸算法”，能用“遞歸算法”的思想分析問題。(2)能夠應(yīng)用自定義函數(shù)方法實(shí)現(xiàn)“遞歸算法”的編程。2.過程與方法(1)通過生活中的“遞歸現(xiàn)象”，讓學(xué)生初步思考和理解“遞歸算法”思想。(2)學(xué)生參與討論，通過思考、動(dòng)手操作，體驗(yàn)“遞歸算法”的程序。3.情感態(tài)度與價(jià)值觀(1)通過利用“遞歸算法”解決實(shí)際問題，讓學(xué)生體驗(yàn)成功。(2)結(jié)合數(shù)學(xué)中的實(shí)例，激發(fā)學(xué)生的數(shù)學(xué)建模意識(shí)，培養(yǎng)學(xué)生多維度的思考問題和解決問題。(3)多學(xué)科融合，促進(jìn)學(xué)科知識(shí)的遷移?！窘虒W(xué)重點(diǎn)】1.遞歸算法的含義。2.自定義函數(shù)實(shí)現(xiàn)遞歸算法的編程。【教學(xué)難點(diǎn)】1.用遞歸算法的思想分析和解決問題。2.自定義函數(shù)實(shí)現(xiàn)遞歸算法的編程?！窘谭▽W(xué)法】項(xiàng)目教學(xué)法、任務(wù)驅(qū)動(dòng)法、合作討論法、講授法、演示法【教學(xué)過程】教學(xué)環(huán)節(jié)教師活動(dòng)學(xué)生活動(dòng)設(shè)計(jì)意圖復(fù)習(xí)舊知溫故知新回顧自定義函數(shù)：為了實(shí)現(xiàn)某種功能而編寫的一段相對(duì)獨(dú)立的程序，并且能夠多次調(diào)用。Function函數(shù)名(參數(shù)As數(shù)據(jù)類型)As數(shù)據(jù)類型函數(shù)體EndFunction回顧、思考復(fù)習(xí)舊知通過前置課程讓學(xué)生理解自定義函數(shù)的定義和格式，為新課教學(xué)做好準(zhǔn)備。創(chuàng)設(shè)情境問題導(dǎo)入創(chuàng)設(shè)情境問題導(dǎo)入“找位置活動(dòng)”：選擇兩組學(xué)生表演1.第1組從第一位同學(xué)開始依序報(bào)出自己的位置?；顒?dòng)規(guī)則：(1)第1組同學(xué)從第一位同學(xué)開始。(2)依次報(bào)出自己所在位置序號(hào)。(3)一直到最后一個(gè)同學(xué)報(bào)完。2.第2組從最后一名同學(xué)開始報(bào)出自己的位置?；顒?dòng)規(guī)則：(1)從最后一位同學(xué)開始。(2)每位同學(xué)只能問他相鄰的同學(xué)且每位同學(xué)最多只能問一次和被問一次，當(dāng)任何一個(gè)同學(xué)知道了答案,要求立即告訴曾經(jīng)問過他的那個(gè)同學(xué)（不能告訴其他同學(xué)）以此類推。(3)直到每位同學(xué)知道自己的位置后，游戲結(jié)束。思考與討論：（1）這兩種“找位置”的方法的共性是什么？（2）第二種方法與第一種方法相比存在什么不同點(diǎn)？（3）第二種“找位置”的結(jié)束條件是什么？第1組學(xué)生表演，由最后一名同學(xué)分析自己得到位置的過程。明確活動(dòng)規(guī)則。第2組學(xué)生表演,由最后一位同學(xué)分析自己得到位置的過程。以小組為單位思考和討論問題小組代表發(fā)言1.采用情境教學(xué)法，從真實(shí)情境出發(fā)，培養(yǎng)學(xué)生發(fā)現(xiàn)問題并解決問題的能力。2.學(xué)生從活動(dòng)中體驗(yàn)“問題的發(fā)生與解決”，初步理解遞歸的思維模式，能夠初步將實(shí)際問題計(jì)算機(jī)程序化。3.活動(dòng)中的問題促進(jìn)學(xué)生積極思考，激發(fā)學(xué)生學(xué)習(xí)興趣。4.為進(jìn)一步學(xué)習(xí)遞歸算法埋下伏筆。自主學(xué)習(xí)知識(shí)梳理活動(dòng)1分析：從第一個(gè)同學(xué)依次向后遞推，從而得到自己的位置。（遞推）活動(dòng)2分析：最后一個(gè)同學(xué)想知道自己的位置，就必須向前面的同學(xué)詢問位置，前面的同學(xué)又得向前面的同學(xué)詢問，直到一個(gè)同學(xué)的前面沒有人，他就是第一個(gè)，然后向他后面的同學(xué)報(bào)告自己的位置，以此類推，直到最后一個(gè)同學(xué)知道自己的位置后，報(bào)告位置。（遞歸）1.遞歸算法（1）遞歸算法是（自己調(diào)用自己）的編程方法。函數(shù)先由上向下調(diào)用（遞推），當(dāng)達(dá)到最底層后，再將函數(shù)值層層向上返回（回歸）。(遞推+回歸就是遞歸)（2）必須有一個(gè)（結(jié)束）調(diào)用遞歸函數(shù)的條件。2.“找位置”算法描述：Functionwz(nAsInteger)AsIntegerIf我知道位置Then我就告訴你Else我要問了下一個(gè)同學(xué)，再告訴你EndIfEndFunction討論、分析明確活動(dòng)過程分小組結(jié)合《學(xué)案》自主討論、總結(jié)1.讓學(xué)生進(jìn)行自主探究學(xué)習(xí)，使學(xué)生主動(dòng)、積極的學(xué)習(xí)新知識(shí)，培養(yǎng)他們的自學(xué)能力。2.通過自主學(xué)習(xí)，引導(dǎo)學(xué)生發(fā)現(xiàn)、整理基礎(chǔ)知識(shí)，提煉核心問題。3.培養(yǎng)學(xué)生整理信息、發(fā)現(xiàn)問題的能力。4.為知識(shí)應(yīng)用打下夯實(shí)基礎(chǔ)。以問導(dǎo)思知識(shí)精講計(jì)算一個(gè)正整數(shù)n的階乘。一、分析問題f(1)=1f(2)=f(1)*2f(1)=1f(2)=f(1)*2f(3)=f(2)*3f(4)=f(3)*4f(5)=f(4)*5f(n)=f(n-1)*nf(n)=f(n-1)*nn=1，1！=1n=2，2！=1*2n=3，3！=1*2*3n=4，4！=1*2*3*4n=5，5！=1*2*3*4*5n！=1*2*3*4*5*……*n2.數(shù)學(xué)遞推公式：用jc（n）表示n的階乘jc=1n=1jc=jc（n-1）*nn>13.結(jié)束遞歸調(diào)用的條件：n=1，jc=1調(diào)用遞歸函數(shù)jc(n)開始調(diào)用遞歸函數(shù)jc(n)開始結(jié)束輸入n輸出ss=jc(n)自定義函數(shù)流程圖自定義函數(shù)流程圖開始結(jié)束jc=jc(m-1)*mm=1?jc=1否是編寫程序PrivateSubCommand1_Click()DimnAsInteger,sAsDoublen=InputBox("n=")s=jc(n)PrintsEndSubFunctionjc(mAsInteger)AsDoubleIfm=1Thenjc=1Elsejc=jc(m-1)*mEndIfEndFunction四、調(diào)試程序自主思考小組討論比較、分析、歸納推導(dǎo)數(shù)學(xué)建模進(jìn)行算法描述分析算法的實(shí)現(xiàn)過程掌握自定義函數(shù)的使用規(guī)則和方法編寫程序?qū)崿F(xiàn)算法1.實(shí)例教學(xué)，“求階乘”簡化教材“裴波那契”數(shù)列的多函數(shù)調(diào)用，回避問題分析的復(fù)雜性。2.選擇學(xué)生熟悉的數(shù)學(xué)問題，利用計(jì)算機(jī)編程解決熟悉的數(shù)學(xué)問題，促進(jìn)學(xué)科融合。3.實(shí)現(xiàn)多元化學(xué)習(xí)方式和跨學(xué)科思維能力的培養(yǎng)。4.由淺入深，促進(jìn)知識(shí)的內(nèi)化和遷移。自主構(gòu)建深化知識(shí)學(xué)生活動(dòng)：猴子吃桃有一天小猴子摘了若干個(gè)桃子，當(dāng)即吃了一半還覺得不過癮，又多吃了一個(gè)。第二天接著吃剩下桃子中的一半，仍覺得不過癮,又多吃了一個(gè)。以后小猴子每天都是吃剩下桃子的一半多一個(gè)。到第10天早上小猴子再去吃桃子的時(shí)候，看到只剩下一個(gè)桃子。請(qǐng)問：小猴子在第1天時(shí)共摘下了多少個(gè)桃子?活動(dòng)要求1.結(jié)合學(xué)案，分組完成。2.小組長組織組員，合作學(xué)習(xí)，完成學(xué)案的填寫。3.完成學(xué)案后，小組同學(xué)共同完成VB程序代碼的填寫。4.根據(jù)題目要求運(yùn)行程序，調(diào)試程序，檢驗(yàn)結(jié)果。5.小組代表分享解題方法和思路。一、分析問題1.遞歸過程分析2.數(shù)學(xué)遞推公式3.結(jié)束遞歸調(diào)用的條件二、設(shè)計(jì)算法用自然語言或流程圖描述算法三、編寫程序PrivateSubCommand2_Click()DimnAsInteger,tAsIntegern=t=Print"桃子數(shù)t=";tEndSubFunctiontao(dAsInteger)AsInteger函數(shù)體EndFunction四、調(diào)試程序小組合作分析、討論、歸納、總結(jié)明確活動(dòng)要求根據(jù)要求完成問題分析、學(xué)案填寫、程序填空、結(jié)果檢驗(yàn)1.引導(dǎo)學(xué)生從模仿開始，由易到難、循序漸進(jìn)，逐步過渡到獨(dú)立進(jìn)行遞歸算法應(yīng)用。2.尊生學(xué)生的個(gè)體發(fā)展，讓學(xué)生進(jìn)行自主探究學(xué)習(xí)。并開展討論，培養(yǎng)學(xué)生之間互相協(xié)作、共同解決問題的能力。3.滲透程序設(shè)計(jì)的思想、方法。提高學(xué)生數(shù)學(xué)思維和計(jì)算思維。4.培養(yǎng)學(xué)生的編程和調(diào)試程序的能力，讓學(xué)生獲得成功的體驗(yàn)。課堂小結(jié)鞏固知識(shí)遞歸算法（1）遞歸算法是自己調(diào)用自己的編程方法。函數(shù)先由上向下調(diào)用，當(dāng)達(dá)到最底層后，再將函數(shù)值層層向上返回。(遞歸就是遞推+回歸)（2）必須有一個(gè)結(jié)束調(diào)用遞歸函數(shù)的條件。師生討論共同