資源簡介

教學設計
課程基本信息
課題 5.2 迭 代 與 遞 歸 （二）遞 歸
教學目標
1. 通過小猴摘桃子啟發理解遞歸的算法思想。 2. 引導能合理選用數據結構，理清遞歸公式及結束條件，遞歸的遞推與回歸兩個階段。 3. 通過實例的形式用自然語言、流程圖、Python語言描述遞歸算法。 4. 引導學生掌握遞歸算法的一般設計思路。 5. 引導學生自覺應用遞歸算法，解決生活、學習中的問題。
教學內容
教學重點： 1. 遞歸公式及結束條件，遞歸的遞推與回歸兩個階段。
2. 自覺應用遞歸算法，解決生活、學習中的問題。
教學難點： 自覺應用遞歸算法，解決生活、學習中的問題。
教學過程
一、認識本節課的學習目標，自學教材內容。 二、情境導入：猜猜E娃娃有幾個銅幣？ 三、遞歸算法基本思想： 通過函數自己調用自己來實現，也就是在其定義中直接或間接調用自身的方法，稱之為遞歸。
1、確定遞歸公式
2、確定遞歸結束條件 四、遞歸算法的執行過程 1、遞推：將復雜的問題（規模為n)的求解遞推出一些簡單的問題（規模小于n）的求解。此階段，必須有終止遞推的情況。 2、回歸：獲得最簡單情況的解后，逐級返回依次得到稍復雜問題的解。 逐層調用，直到邊界（遞推） 代入計算，依次返回（回歸） 五、遞歸實現要點: （1）有明確的結束遞歸的邊界條件（終止條件）及終止時的邊界值。 （2）函數的描述中包含其本身。 （1）抽象建模
（2）設計算法
（3）編寫程序并調試 六、課堂實踐： 用遞歸算法求 n 的階乘 七、遞歸的作用 1、分解成規模較小的同類型問題。 2、用遞歸函數替代多重循環。 3、解決本來就是用遞歸形式定義的問題。 八、課堂小練： （1）用遞歸算法求裴波那契數列為：1，1，2，3，5，8，13 ……（填空） def fx(n): if n<2: （1） else: （2） return f print（fx(10)) （2）程序設計并調試： 一個樓梯有n階，上樓可以一步上一階，也可以一步上二階。要求：編寫一個程序，輸入一個正整數n(表示樓梯階數)，輸出共有多少種不同的走法可以到達第n階。 九、漢諾塔游戲： 1. 抽象與建模 2.設計算法 3.編寫程序 十、課堂小結 1、遞歸算法的概念 2、遞歸算法的兩個條件和階段 十一、自我評價 對自己的表現進行客觀的評價，并思考后續完善的方向。（3=優秀，2=一般，1=仍需加油） 評分項自我評價能計算小猴摘桃并總結遞歸算法的基本思想 3 2 1掌握遞歸算法的兩個條件和兩個階段 3 2 1能自主學習教材并用自然語言、Python語言描述遞歸算法 3 2 1能夠編程實現斐波那契數列、階乘的遞歸實現 3 2 1掌握遞歸算法的設計思路，理解其數學原理和注意事項 3 2 1能用遞歸算法解決學習、生活中的應用 3 2 1
十一、課后作業 1.求最大公約數：早在公元前300年左右，歐幾里得就在他的著作《幾何原本》中給出了高效的解法——輾轉相除法。 輾轉相除法的方法是用較大的數X除以較小的數Y，得到余數Z 如果余數為0，則較小數Y就是兩者的最大公約數。 例如：33和9 的最大公約數就是9與6的最大公約數3 以下程序#號劃線處代碼為（ ） A.a B. gcd(b,a%b) C. gcd(b,a//b) D. gcd(b,a) 2. def zh(n): if n<=1: f='1' else: f=zh(n//2)+str(n%2) return f print(zh(18)) 該程序段運行后的輸出值為( ) A、10100 B、10010 C、11010 D、11000 3.有如下數列a1,a2,a3,…的定義如下: a1=1,a2=1 ,…,an =3an-1+2an-2(n>2)。為求該數列的第n項值,現利用遞歸算法實現,Python代碼如下,請在劃線處填入合適的代碼。 def yuan(x): if x<=2 : return ① else : ② n=int(input(“n=“)) print(yuan(n)) 作業答案：
1. B
2. B
3. ①1 ② return 3*yuan(x-1)+2*yuan(x-2)

展開更多......

收起↑