教案課程名稱數據結構與算法設計課程代碼總學時64課程負責人任課教師

單元教案授課日期年月日—月日授課地點授課班級班級人數教學單元單元4遞歸教學時數4教學目標AOB1:掌握計算機程序設計中的線性表、棧、隊列、樹和圖的邏輯結構與存儲結構。了解遞歸的數據邏輯組織結構；AOB3:掌握對算法的科學分析方法。BOB1:能根據實際問題中的數據特性選擇適當的數據結構；EOB1:掌握使用搜索引擎、論壇、幫助文檔、課外書籍等方法解決學習中出現的問題；教學方式混合式教學評價方式課堂考勤（20%），課堂活動參與程度（30%）線下課堂教學參與程度（50%）教學資源1.算法與數據結構（Java語言描述），陳媛，清華大學大學出版社2.電腦50臺（含eclips）;3.網絡學習資源：/forums/ST_Arithmetic：課程平臺網址：/teacher/mainCourse/courseHome.html?courseOpenId=u3bwaoaqhzdgvlcf34d8ea單元教學設計第一次課（2學時）教學內容4.1遞歸的概念若一個對象部分地包含它自己，或用它自己給自己定義，則稱這個對象是遞歸的。若一個過程直接地或間接地調用自己，則稱這個過程是遞歸的過程。4.2遞歸設計：遞歸問題，必須符合以下三個條件可以把一個問題轉化為一個新的問題，這個新的問題的解決方法與原問題的解法相同，只是所處理的對象有所不同；可以通過轉化過程使問題得到簡化；要有明確的結束遞歸的條件，否則遞歸將會無止境地進行下去，直到耗盡系統資源，必須要有終止遞歸的條件。適用遞歸解決的問題1.定義是遞歸的2.數據結構是遞歸的3.問題的解法是遞歸的遞歸的執行過程遞歸設計步驟1.對原問題f(s)進行分析，假設出合理的“較小問題”f(s’)；2.假設f(s’)是可解的，在此基礎上確定f(s)的解，即給出f(s)與f(s’)的關系；3.確定特定情況，即（f(1)或f(0)）的解，由此作為遞歸出口。教學重點遞歸設計教學難點遞歸設計教學流程教學環節教師活動學生活動講評和考勤（5分鐘）1平臺發布任務2考勤1考勤講授（80分鐘）1.遞歸的概念（10分鐘）2.遞歸設計（5分鐘）3.適用遞歸解決的問題（50分鐘）4.遞歸的執行過程（10分鐘）5.遞歸設計步驟（5分鐘）1.積極回答教師提問2.認真思考、記錄關鍵內容3.積極參與課堂的討論和互動總結與發布課后任務（5分鐘）1.總結課堂內容以及在練習過程中出現的，問題。2.布置課后任務1.思考教師總結2.記錄課后任務第二次課（2學時）教學內容遞歸的評價遞歸的優點：可解決復雜問題；可縮短程序代碼、提高編程效率遞歸的缺點：不能提高程序的運行效率遞歸運行效率問題斐波那契數列的遞歸調用樹遞歸與回溯回溯法是從問題的某一種可能出發，搜索從這種情況出發所能達到的所有可能。當這一條路走到“盡頭”的時候，再倒回上一節點，從另一個可能出發，繼續搜索。回溯是一種思想，遞歸是一種解決問題的方法。回溯可以用遞歸來實現，也可以不用遞歸實現。迷宮問題迷宮中設置很多隔壁，對前進方向形成了多處障礙。假設迷宮的每個岔路口只有東南西北四個方向或是這四個方向的子集。回溯法思想：一種不斷試探且及時糾正錯誤的搜索方法。；從入口出發，按某一方向向前探索，若某處可以到達，則到達新起點；否則試探下一方向。；若所有的方向均沒有通路，則沿原路返回到前一點，換下一個方向再繼續試探，直到所有可能的通路都試探到。；結果是或找到一條通路，或無路可走又返回到入口點。遞歸實現：從入口出發，每到一個結點（岔路口），按東南西北的秩序訪問相應方向的下一個結點，如果相應方向沒有可以訪問的結點，則訪問下一個方向。如果四個方向全被訪問完，則返回到前一個結點。直到找到出口或回到入口。遞歸的關鍵問題為防止遞歸的無休止調用，在遞歸函數中要及時返回，這是結束條件的作用；在所有的遞歸函數中都有一個終止遞歸的條件判斷；遞歸函數可以簡化程序，但一般不能提高程序的執行效率。教學重點遞歸的評價教學難點遞歸的評價教學流程教學環節教師活動學生活動講評和考勤（5分鐘）1.平臺發布任務2.考勤1.考勤講授（60分鐘）1.遞歸的評價（10分鐘）2.遞歸運行效率問題（15分鐘）3.遞歸與回溯（15分鐘）4.迷宮問題（15分鐘）5.遞歸的關鍵（5分鐘）1.積極回答教師提問2.認真思考、記錄關鍵內容3.積極參與課堂的討論和互動代碼實現演示（20分鐘）1.斐波那契數列的遞歸調用樹的代碼實現（20分鐘）1.認真思考、記錄關鍵內容總結與發布課后任務（5分鐘）1.總結課堂內容以及在練習過程中出現的，問題。2.布置課后任務1.思考教師總結2.記錄課后任務教學效果與反思根據單元測驗結果，80%的學生教好掌握了教學內容，達成了單元教學目標。其中教學目標AOB1、AOB2、AOB3、BOB1、BOB2、EOB1、EOB2、EOB3達成情況較好，但EOB1、EOB3達成情況一般。結合學生的課堂練習，在線測試等教學活動的結果來看，課堂出勤比較好，沒有缺課的情況；課堂練