漢諾塔問題與遞歸思想教學設(shè)計

1、一、教學思想（包括教學背景、教學目標）1、教學背景本課程“遞歸算法”，屬于數(shù)據(jù)結(jié)構(gòu)與算法課程中“棧和隊列”章節(jié)的重點和難點。數(shù)據(jù)結(jié)構(gòu)與算法已經(jīng)廣泛應(yīng)用于各行各業(yè)的數(shù)據(jù)存儲和信息處理中，與人們的社會生活密不可分。該課程是計算機類相關(guān)專業(yè)核心骨干課程，處于計算機學科的核心地位，具有承上啟下的作用。不僅成為全國高校計算機類碩士研究生入學的統(tǒng)考科目，還是各企業(yè)招聘信息類員工入職筆試的必考科目。數(shù)據(jù)結(jié)構(gòu)與算法課程面向計算機科學與技術(shù)、軟件工程等計算機類學生，屬于專業(yè)基礎(chǔ)課。2、教學大綱通過本課程的學習，主要培養(yǎng)學生以下幾個方面的能力：1） 理解遞歸的算法；2） 掌握遞歸算法的實現(xiàn)要素；3） 掌握數(shù)值與非

2、數(shù)值型遞歸的實現(xiàn)方法。根據(jù)學生在學習基礎(chǔ)和能力方面的差異性，將整個課程教學目標分成三個水平：合格水平（符合課標的最低要求），中等以上水平（符合課標的基本要求），優(yōu)秀水平（符合或超出課標提出的最高要求）。具體如下表：水平等級衡量標準合格可以正確理解遞歸算法的概念，并理解遞歸算法的遞歸分解和遞歸結(jié)束條件設(shè)計。中等以上在合格水平的基礎(chǔ)上，能熟練掌握數(shù)值型問題的遞歸算法設(shè)計；理解非數(shù)值型問題的遞歸算法設(shè)計。優(yōu)秀在中等水平基礎(chǔ)上，可以獨立分析并實現(xiàn)數(shù)值與非數(shù)值型問題遞歸的設(shè)計，解決復(fù)雜問題求解的遞歸方法。二、課程設(shè)計思路（包括教學方法、手段）“遞歸算法”課程以故事引入、案例驅(qū)動法、示范模仿、啟發(fā)式等多元

3、化教學方法，設(shè)計課程內(nèi)容。具體的課堂內(nèi)容如下所示：教學環(huán)節(jié)課堂內(nèi)容設(shè)計教法方法導入新課引導學生學習熱情明確教學目標課程教學課程總結(jié)思考拓展一、故事導入：結(jié)合故事突出主題生活中大人給小孩講故事時，講了掩耳盜鈴、入木三分后，若實在沒故事了，就會講說：從前有座山，山里有個廟，廟里有個老和尚講故事，講的什么呢？講的是從前有個山，山里有個廟，廟里有個老和尚講故事，講的什么呢？這就是一個典型的遞歸故事，可以無限次的遞歸下去?？梢园堰@個故事比喻成函數(shù)的遞歸調(diào)用，但和故事不同的是，在程序設(shè)計中，不可能無限遞歸下去，必須要有遞歸的結(jié)束條件。而且每次遞歸都應(yīng)該朝著能夠結(jié)束的條件去運行，直到滿足條件時終止遞歸調(diào)用。

4、重點學習內(nèi)容：1.理解遞歸的概念；2.掌握遞歸算法的實現(xiàn)要素； 3.掌握數(shù)值與非數(shù)值型遞歸的實現(xiàn)方法。二、案例引入：結(jié)合實例“階乘”講解遞歸算法的特征和設(shè)計方法。編寫代碼：int fact(int n) int value; if (n=0) value=1; else value=n*fact(n-1); return value;main() printf("%d",fact(5);分析執(zhí)行過程：前提：1) 原問題可以層層分解為類似的子問題，且子問題比原問題規(guī)模更??；2) 規(guī)模最小的問題具有直接解。設(shè)計方法：1) 尋找分解方法:將原問題轉(zhuǎn)化為子問題求解；2) 設(shè)計遞歸出

5、口:根據(jù)規(guī)模最小的子問題確定遞歸終止條件。 三、案例引入：結(jié)合故事突出主題結(jié)合hanoi典型實例，使學生能深入理解遞歸函數(shù)的設(shè)計方法，以及在實際問題中的應(yīng)用，培養(yǎng)學生分析問題的能力。設(shè)有三座塔座（A、B、C）,在一個塔座（設(shè)為A）上有64個盤片，盤片不等，按大盤在下，小盤在上的順序依次疊放?，F(xiàn)要將A塔上的盤片借助于B塔，移到C塔上并保持同樣順序疊排，移動盤片時必須遵守以下規(guī)則：1）每次只能移動一個圓盤；2）圓盤可以插在A、B、C任意一個塔座上；3）任何時候都不能將一個較大的圓盤放到 較小的圓盤之上。實物演示：根據(jù)一段動畫演示，觀察并共同分析hanoi的移動步驟，并總結(jié)遞歸函數(shù)的分解方法和遞歸出

6、口。設(shè)計思想（三步法）： 1）把A塔上的n-1個盤片借助C塔移至B塔；2）把第n個盤片從A塔移至C塔；3）把B塔上的n-1個盤片借助A塔移至C塔。遞歸出口：當n=1時，無需借助，直接移動即可。編寫代碼：根據(jù)算法設(shè)計思想編寫程序代碼。#include <stdio.h>int count=0;void move(int n,char x,char z)printf("%d:%c->%cn",n,x,z);count+;void hanoi(int n,char x,char y,char z)if(n=1)move(1,x,z);elsehanoi(n-1,

7、x,z,y);move(n,x,z);hanoi(n-1,y,x,z);main()int n;printf("please input n:");scanf("%d",&n);hanoi(n,'A','B','C');printf("nthe count is %dn",count);運行程序：為了查看運行執(zhí)行次數(shù)，增加count計數(shù)器以便統(tǒng)計移動次數(shù)。觀察n和count之間的數(shù)值關(guān)系。 n count1 1 2 3 3 7 4 15 5 31 count = 2n-1 思考：

8、若移動速度為1個/秒，則需要(264-1)/365/24/3600 >= 5849億年。四、總結(jié)和思考總結(jié)：對于階乘這類數(shù)值型問題，可以表達成數(shù)學公式，然后從相應(yīng)的公式入手推導，解決這類問題的遞歸定義，同時確定這個問題的邊界條件，找到結(jié)束遞歸的條件。對于漢諾塔這類非數(shù)值型問題，雖然很難找到數(shù)學公式表達，但可將問題進行分解，問題規(guī)模逐漸縮小，直至最小規(guī)模有直接解。思考：數(shù)值型問題：斐波那契數(shù)列的遞歸設(shè)計。非數(shù)值型問題：八皇后問題的遞歸設(shè)計。故事引入、知識遷移法講授法案例引入法、示范模仿法結(jié)果展示啟發(fā)式教學法故事引入、任務(wù)驅(qū)動法示范模仿法、實物n=3的實例演示、啟發(fā)式教學法環(huán)境下實際演示代碼

9、分析算法深入分析利用計算器計算次數(shù)闡述總結(jié)知識拓展三、教學特色（總結(jié)教學特色和效果）遞歸算法課程主要討論遞歸設(shè)計的思想和實現(xiàn)。從階乘實例入手，由淺入深，層層深入介紹了遞歸的設(shè)計要點和算法的實現(xiàn)。從漢諾塔問題，通過“邊提問，邊思考”的方式逐層深入地給出算法的分析和設(shè)計過程。通過故事引入、案例導入、實例演示、PPT展示、實現(xiàn)效果等“多元化教學方式”，努力擴展課堂教學主戰(zhàn)場。加上逐步引導、問題驅(qū)動，啟發(fā)學生對算法的理解，并用實例演示展示算法的分析過程，在編譯環(huán)境下實現(xiàn)該算法，加深對算法實現(xiàn)過程的認識。1、知識點的引入使用故事誘導法講授通過“老和尚講故事”引入函數(shù)的遞歸調(diào)用，并通過“世界末日問題”故事

10、引入非數(shù)值型問題的遞歸分析，激發(fā)學習積極性，挖掘?qū)W生潛能。2、重點、難點內(nèi)容采用案例驅(qū)動式教學方法課程內(nèi)容通過案例驅(qū)動，培養(yǎng)學生計算思維能力和設(shè)計能力；學生不但可以激發(fā)學習積極性和主動性，提高學生獨立思考，深入研究，分析問題、解決問題的能力，從而促進學生綜合能力發(fā)展。3、注重應(yīng)用性的實例教學法整個教學實例都圍繞遞歸分析的尋找分解方法和遞歸出口設(shè)計這兩個要素展開引導、分析、演示和總結(jié)。通過實際問題的解決，使學生不但掌握“遞歸算法”這一知識點，同時鍛煉學生分析和解決復(fù)雜問題的能力，將兩者結(jié)合完成分析和程序設(shè)計實現(xiàn)，滿足應(yīng)用型人才的培養(yǎng)要求。4、用啟發(fā)引導式教學法實現(xiàn)知識點的拓展和延續(xù)本課程中的“遞歸算法”是以階乘這類數(shù)值型問題和漢諾塔這類非數(shù)值型問題分別討論。對于現(xiàn)實生活中，斐波那契數(shù)列這類數(shù)值型和八皇后這類非數(shù)值型情況，在設(shè)計中提出了不同的分析策略，在課程結(jié)束啟發(fā)大家思考，實現(xiàn)知識點的拓展和延續(xù)。5、運用現(xiàn)代化教學手段豐富教學形式在講授相關(guān)知識的時候，采用動畫演示、視頻資料、編譯環(huán)境、Windows計算器以及相關(guān)的圖片資料等多元化方式。這樣在增加學習興