資源簡介

教學設計
課程基本信息
學科 信息技術 年級 高二年級 學期 秋季
課題 《遞歸》
教科書 書 名：信息技術選擇性必修1《數據與數據結構》 出版社：廣東教育出版社
教學目標
1.理解遞歸算法的概念、基本思想及其編程實現原理。 2.學會分析并建立合理的遞歸數學模型。 3.通過階乘、斐波那契數列的案例，理清遞歸算法解決問題的執行過程，能夠自主設計遞歸函數解決實際問題。
教學重難點
教學重點： 1.遞歸算法的基本思想及其編程實現原理。 2.遞歸算法數學模型及其程序結構。 3.python編程遞歸算法的實際應用。 教學難點： 1.遞歸算法數學模型及其程序結構。 2.python編程遞歸算法的實際應用。
教學過程
一、導入新課 播放一個簡單易懂的生活情景動畫《電影院找座位》，引入遞歸的概念。 （一）教師：看完了動畫，同學們發現了什么特點嗎？ 實際上，電影院找座位的過程就是一個遞歸的過程，當你問前一排觀眾，前一排的觀眾又繼續向前問，這個過程我們叫做“遞”，即把問題不斷分解為可操作性的小問題。第一排的觀眾可以直接得到答案后，接下來要把答案傳遞給第二排的觀眾，去解決他的問題，第二排的觀眾計算出自己的排數后再傳遞給第三排，以此類推，直到傳遞回自己的位置，這個過程我們叫做“歸”，即把小問題的結果返回給大問題，達到最終目的，整個過程連接在一起，就叫做“遞歸”。其中，在分解的過程中，一直到第一排就結束了，它已經到盡頭了，不能再往前推了，我們把它稱之為遞歸終結條件，或遞歸出口。中間的每一個環節都叫做遞歸的公式。 （二）總結遞歸的概念：大問題的解決中嵌套著與原問題相似的規模較小的問題，這種問題的解決方法在計算機科學中稱為遞歸，它通過函數自己調用自己來實現，即一個函數在其定義中直接或間接調用自身的一種方法。 講授新課 （一）通過階乘的例子，理解遞歸算法的執行過程。 1.通過階乘的定義引導學生寫出階乘的函數關系式，并分析里面包含的遞歸規律： 當n=1時，f（n）=1(遞歸結束條件），當n>1時，f（n）=n*f（n-1 ）為遞歸公式，再進一步引導學生寫出階乘問題的遞歸程序代碼： def f (n): if n == 1: return 1 else: return n* f（n-1 ） print(f(5)) 2.通過動畫演示程序在計算F（5），即5的階乘運算的全過程，演示完動畫后，再總結遞歸的執行過程，就是指在遞歸終止條件滿足之前，層層推下去，在遞歸終止條件滿足之后，再層層回歸的全過程，以此加深學生對遞歸的理解。 3.實操演示。 （二）以斐波那契數列為例，體驗遞歸算法實現的整個過程。 1.分析斐波那契數列數列的來源：斐波那契是意大利數學家，他提出了一個有趣的兔子繁殖的問題：一對剛出生的小兔子，一個月后就能成長為成年兔，再過一個月后(即第三個月起)，就每月生一對兔子。新生的兔子也按這個規律繁殖?，F在僅有一對剛出生的小兔子，問在沒有兔子死亡的情況下，一年后總共繁殖成多少對兔子。根據題意，通過一個圖來模擬演示，前幾個月兔子的繁殖情況，并匯總成表格，如下圖所示： 2.通過這個表格數據，引導學生發現規律，逐步建立遞歸算法的數學模型。 教師：請同學們思考一下，通過這個表格，可以發現每個月兔子數量之間有什么關系呢？ 學生：老師，通過觀看表格中的數據，可以發現，兔子的數量隨著時間增長的越來越多，而且每個月的大兔子數量一定等于上個月的兔子總數，，，，而每個月的小兔子數量一定等于上個月的大兔子數量，也就是前一個月的兔子數量總和。從第三項開始，后面的數總是等于前兩個數之和。 教師：由表格可知，當n=1時，f(n)=1，當n=2時，f(n)=1，當n>2時，f(n)=f(n-1) + f(n-2)，其中，當n=1時，f(n)=1，當n=2時，f(n)=1，為遞歸終止條件，當n>2時，f(n)=f(n-1) + f(n-2)為遞歸公式。 由此，可以可以得到斐波那契數列的程序代碼為： def f(n)： if n == 1 or n == 2: return 1 else: return f(n-1) + f(n-2) print(f(12)) 3.演示程序代碼在執行函數f（5）的過程。(先逐層分解問題，直至遞歸終止條件獲得答案后，再逐層返回答案。） 4.實操演示。 三、課堂小結 四、課后作業 遞歸算法求年齡：有5個人坐在一起，問第5人多少歲？他說比第4個人大兩歲。問第4人的歲數？他說比第3個人大兩歲。問第3個人，又說比第2個人大兩歲。問第2個人，他說比第1個人大兩歲。最后問第1個人，他說10歲。請問第五個人多大？ （一）寫出年齡問題的遞歸終止條件。 （二）請寫出年齡問題的遞歸公式。 （三）請嘗試編寫年齡問題的程序代碼。

展開更多......

收起↑