關(guān)于遞歸算法在高中信息技術(shù)課中的教學(xué)策略的探究 論文

關(guān)于遞歸算法在高中信息技術(shù)課中的教學(xué)策略的探究單的生活場景入手，將同一問題分別運(yùn)用遞歸法和迭代法，通過對(duì)比的方法使得學(xué)生理解遞歸算法的遞歸調(diào)用和遞歸的結(jié)束條件，以及實(shí)際應(yīng)用中應(yīng)注意的問題。關(guān)鍵字：遞歸法，比較法，案例法，教學(xué)策略，迭代法，python下面我從以下幾個(gè)方面談?wù)勥f歸法的教學(xué)策略。一、提出問題：桿上有若干木盤，規(guī)定每次移動(dòng)一個(gè)木盤，且小的木盤只能疊在大的木盤上面，設(shè)計(jì)算法，用盡可能少的次數(shù)把所有木盤從A桿移動(dòng)到C桿上。二、分析問題：盤移動(dòng)到BnCB桿上的第一個(gè)木盤移動(dòng)到C33變得復(fù)雜起來，如果A桿上有64個(gè)木盤，每秒移動(dòng)一次，那么完成這項(xiàng)任務(wù)需要5845.42機(jī)按照算法的步驟完成木盤的移動(dòng)功能。三、遞歸算法知識(shí)學(xué)習(xí)：1、分治思想：K個(gè)子問K略。分治策略可以用“分、治、合”三個(gè)過程進(jìn)行概括，“分”的過程是自頂向下的過程，先從整體上去把握問題，分解KK個(gè)問題進(jìn)行求解，如果子問題的規(guī)模仍然不夠小，則將其再分解為K個(gè)子問題，直到問題規(guī)模足夠小，可以直接求出結(jié)果，的解，自下而上逐步求出原問題的解。n個(gè)盤子移動(dòng)問題，可以分成三個(gè)子問題，第一個(gè)問題如何把n-1個(gè)盤子借助C桿(輔助桿)移動(dòng)到Bn個(gè)盤子移動(dòng)到Cn-1個(gè)盤子借助A桿(輔助桿)移動(dòng)到C桿上。我們?cè)賮矸治龅谝粋€(gè)子問題，如果n-1>1，我們將第一個(gè)問題再n-2個(gè)盤子借助借助B桿移動(dòng)到Cn-1個(gè)盤子移動(dòng)到Bn-2個(gè)盤子借助A桿從C桿移動(dòng)到B盤子數(shù)為1的時(shí)候，直接將盤子從起始桿移動(dòng)到目標(biāo)桿。2、遞歸算法：遞歸算法應(yīng)用的場景是當(dāng)要解決的多個(gè)問題之間是具有相似性的時(shí)候，通過直接或間接下層模塊傳遞過來的值計(jì)算自己的結(jié)果再向上傳遞，最后最上層模塊的程序得到最終結(jié)果。當(dāng)我們要求解4的階乘(4!)的時(shí)候，我們可以想到4!=4*3!，3!=2*1!，2!=2*1!如果我們認(rèn)為4的階乘規(guī)模比較大，那么3的階乘規(guī)模就會(huì)小一些，2的階乘會(huì)更小一些，1的階1的階乘代入到22的階乘等于2,2的階乘代入33的階乘等于6,3的階乘代入44的階乘等于的階乘調(diào)用了33的階乘問題與4的階乘題可以用遞歸算法進(jìn)行求解。個(gè)盤子的移動(dòng)的問題和n-1個(gè)盤子移動(dòng)問題具有相似性，這樣可以通過定義漢諾塔遞歸函數(shù)，函數(shù)內(nèi)容可以調(diào)用函數(shù)自身功能求解問題。3、遞歸法的知識(shí)準(zhǔn)備數(shù)學(xué)模型，比如在斐波那契數(shù)列中，遞歸關(guān)系表達(dá)式為f[i]=f[i-1]+f[i-2]，f2=f1=1，第二個(gè)月和第一個(gè)月的兔子數(shù)量為調(diào)用問題。用python語言定義遞歸函數(shù)：def函數(shù)名稱(參數(shù)):結(jié)束條件滿足獲取結(jié)果，向上層傳遞否則，調(diào)用下層函數(shù)滿足結(jié)束條件實(shí)際上就是問題規(guī)模要足夠的小，能夠直接求出結(jié)果，然后向上層傳遞。調(diào)用下層函數(shù)，就是先求出規(guī)模為n的問題的子問題。4、遞歸算法的基本特征：（1）、函數(shù)調(diào)用。函數(shù)參數(shù)值較小，子問題具有通用性。（2）、遞歸函數(shù)結(jié)束條件，可以直接計(jì)算其結(jié)果，計(jì)算出結(jié)果后向上傳遞。（3）、遞歸算法要解決的問題和其子問題具有相似性。（4）、遞歸的規(guī)模要適當(dāng)。復(fù)雜，所用空間較多，棧空間就會(huì)溢出。5、分治與遞歸的關(guān)系：問題。四、應(yīng)用遞歸算法解決問題應(yīng)用遞歸算法求解漢諾塔的問題，漢諾塔遞歸函數(shù)實(shí)現(xiàn)：defhanno(n,s,m,t)：#定義遞歸函數(shù)，n層塔，將盤子從s借助m移動(dòng)到t，m為輔助桿ifn==1:print(s,‘-->’,t)#將一個(gè)盤子從s移動(dòng)到telse:hanno(n-1,s,t,m)#將前n-1個(gè)盤子從s移動(dòng)到m上print(s,‘-->’,t)#將最底下的最后一個(gè)盤子從s移動(dòng)到t上hanno(n-1,m,s,t)#將m上的n-1個(gè)盤子移動(dòng)到t上#主程序n=int(input(‘請(qǐng)輸入漢諾塔的層數(shù)’)hanno(n,’A’,’B’,’C’)input(“運(yùn)行完畢，請(qǐng)按回車鍵退出…”)運(yùn)行結(jié)果：請(qǐng)輸入漢諾塔的層數(shù)：3A-->C(1)A-->B(2)C-->B(3)A-->C(4)B-->A(5)B-->C(6)A-->C(7)當(dāng)漢諾塔的層次為3(2)(3)看成是第一個(gè)子問題，(4)看成是第二個(gè)子問題，(5)(6)(7)看成是第三個(gè)子問題。(1)(2)(3)是把A桿上的兩個(gè)盤子移動(dòng)到BCK12問題，(3)是第一個(gè)子問題第三個(gè)子問題，記為K13問題。五、比較迭代法和遞歸法解決問題關(guān)系：需要進(jìn)行參數(shù)壓棧和出棧，所以遞歸比迭代所用時(shí)間和空間都要多。迭代程序可以轉(zhuǎn)換成等價(jià)的遞歸程序。如斐波那契數(shù)列求第n項(xiàng)值為例。deffib1(n):#遞歸求Fibonacce數(shù)列第n個(gè)月的兔子對(duì)數(shù)ifn==1orn==2:#最小規(guī)模問題，可以直接求出結(jié)果，遞歸的邊界條件return1else:returnfib1(n-1)+fib1(n-2)deffib2(n):迭代法求Fibonacce數(shù)列第n個(gè)月的兔子對(duì)數(shù)f1=f2=1foriinrange(3,n+1)：f1,f2=f2,f1+f2#先計(jì)算f1+f2，然后將f2值給f1，再將f1+f2的值給f2returnf2遞歸算法是把求解第nn-1個(gè)月的兔子對(duì)數(shù)和求n-2個(gè)月的兔子對(duì)數(shù)又分解為n-2個(gè)月的兔子對(duì)數(shù)問題和n-3個(gè)月題，逐層向上反饋，直到求出第n個(gè)月的兔子對(duì)數(shù)。歸法的關(guān)系表達(dá)式。迭代求出或逼近目標(biāo)結(jié)果，多采用循環(huán)的方式，程序結(jié)構(gòu)往往較遞歸要復(fù)雜。六、遞歸算法的局限性：棧溢出等。所以在規(guī)模較小的時(shí)候，不提倡用遞歸算法設(shè)計(jì)程序解決問題。七、教學(xué)反思：K遞歸算法的局限性。思路清楚了，接下來，就是怎么實(shí)現(xiàn)的問題，引導(dǎo)學(xué)生分析規(guī)模問題和子問題之間的關(guān)系，函數(shù)，調(diào)用自身實(shí)現(xiàn)問題解決。問題。算法。解決了，靈活應(yīng)用到自己學(xué)習(xí)中，就是一種很好的學(xué)習(xí)能力。解決問題的方法，引導(dǎo)學(xué)生知道遞歸法的調(diào)用深度與問題大小的關(guān)系。參考文獻(xiàn)：[1]中華人民共和國教育