楊平

（韶關(guān)學(xué)院數(shù)學(xué)與統(tǒng)計學(xué)院，廣東韶關(guān)512005）

任務(wù)驅(qū)動法在遞歸算法教學(xué)設(shè)計中的應(yīng)用

楊平

（韶關(guān)學(xué)院數(shù)學(xué)與統(tǒng)計學(xué)院，廣東韶關(guān)512005）

摘要：遞歸作為一種編程算法在程序設(shè)計中廣泛應(yīng)用，是編程思維的重點內(nèi)容之一.以任務(wù)驅(qū)動法在遞歸算法課堂教學(xué)中的應(yīng)用為例，設(shè)計趣味性任務(wù),由淺入深,激發(fā)學(xué)生的興趣，利用道具分解任務(wù)規(guī)模，促進(jìn)對問題本質(zhì)的理解，旨在提高學(xué)生的學(xué)習(xí)興趣，培養(yǎng)學(xué)生的編程能力，提高教學(xué)質(zhì)量.

關(guān)鍵詞：遞歸算法；編程算法；課堂教學(xué)；編程能力

遞歸作為一種編程算法在程序設(shè)計中廣泛應(yīng)用，是指函數(shù)在運行的過程中又直接或間接地調(diào)用該函數(shù)本身［1-2］.程序調(diào)用自身的編程技巧稱為遞歸，在函數(shù)中直接調(diào)用函數(shù)本身，稱為直接遞歸調(diào)用.在函數(shù)中調(diào)用其它函數(shù)，其它函數(shù)又調(diào)用原函數(shù)，這就構(gòu)成了函數(shù)自身的間接調(diào)用，稱為間接遞歸調(diào)用.

雖然用遞歸算法編寫的程序結(jié)構(gòu)清晰存在著自調(diào)用過程，程序控制反復(fù)進(jìn)入其自身，使程序的分析設(shè)計有一定困難，致使很多初學(xué)者往往對遞歸迷惑不解，也在這上面花了不少的時間，卻收效甚微.本文以“任務(wù)驅(qū)動法”來設(shè)計教學(xué)過程的內(nèi)容，首先從引人入勝的故事入手展開教學(xué)，自然簡單地引入遞歸概念，讓學(xué)生對知識點的認(rèn)識從感性到理性［3］.再從學(xué)生的角度出發(fā)合理地設(shè)計出學(xué)生能接受的教學(xué)內(nèi)容與環(huán)節(jié)，通過讓學(xué)生主動分析遞歸算法經(jīng)典案例，結(jié)合教學(xué)道具促進(jìn)學(xué)生容易完成“教學(xué)任務(wù)”，從而達(dá)到培養(yǎng)學(xué)生主動分析問題、解決問題的綜合能力.

1設(shè)計趣味性任務(wù),由淺入深,激發(fā)學(xué)生的興趣

課堂教學(xué)可以由一個古老的故事引入：從前有座山，山上有個廟，廟里有個老和尚和小和尚，老和尚給小和尚講故事，講的是:從前有座山，山上有個廟，廟里有個老和尚和小和尚，老和尚給小和尚講故事，講的是：從前有……

這是一個典型的“遞歸”故事，可以無限次遞歸下去.可以把這個故事比喻成遞歸調(diào)用，但在程序設(shè)計中，程序不可無限地遞歸下去，必須有遞歸結(jié)束條件，而且每次遞歸都應(yīng)該向結(jié)束條件邁進(jìn)，直到滿足結(jié)束條件而停止遞歸調(diào)用，同時適時宜地給出遞歸調(diào)用的定義.

遞歸調(diào)用的編程應(yīng)用有一個最著名的問題：相傳在很久以前，在中東地區(qū)的一個寺廟里，幾個和尚整天不停地移動著盤子，日復(fù)一日，年復(fù)一年，移盤不止，移動盤子的規(guī)則是這樣的：事先固定三根針，假設(shè)分別為A針、B針、C針，A針上套有64個中間帶孔的盤子，盤子大小不等，大的在下，小的在上，要求把這64個盤子從A針移到C針，在移動過程中可以借助于B針，每次只允許移動一個盤子，且移動過程中的每一步都必須保證在三根針上都是大盤在下、小盤在上.據(jù)說當(dāng)所有64個盤子全部移完的那一天就是世界的末日，故漢諾塔問題又被稱為“世界末日問題”.

從給出這個著名的案例著手一步一步引導(dǎo)學(xué)生積極思考，從而自主找出解決問題的方法，這樣的課堂的教學(xué)才能讓學(xué)生印象深刻，掌握遞歸本質(zhì).

2利用道具分解任務(wù)規(guī)模，促進(jìn)對問題本質(zhì)的理解

課前簡單制作出3個紙柱子與4個不同大小在空心紙盤.首先給出一個最簡單的情況，A針上只有一個盤，讓一個同學(xué)動手操作如何去完成案例任務(wù).當(dāng)然任何一個學(xué)生就能完成：直接把一個盤從A針移到C針.

其次給出A針上只有2個盤，讓2個同學(xué)起來操作如何去完成任務(wù).可以適當(dāng)引導(dǎo)學(xué)生把任務(wù)分解成3步：（1）學(xué)生甲讓學(xué)生乙把A針上的一個盤從A針移到B針上.（2）學(xué)生甲直接把A針上剩下的一個盤子移到C針.（3）學(xué)生乙把B針上的一個盤從B針移到C針上.可以發(fā)現(xiàn)一共移動了3=22-1次.

再給出A針只有3個盤，讓3個同學(xué)起來操作如何去完成任務(wù).可以適當(dāng)引導(dǎo)學(xué)生把任務(wù)分解成3步：（1）學(xué)生甲讓學(xué)生乙、丙把A針上的2個盤從A針移到B針上（用上的方法移動了3次）.（2）學(xué)生甲直接把A針上剩下的一個盤子移到C針.（3）學(xué)生乙、丙把B針上的2個盤從B針移到C針上（用上的方法移動了3次）.可以發(fā)現(xiàn)一共移動了3+1+3=7=23-1次.

圖1　初始狀態(tài)　

圖2　分解完成子問題

圖3　分解完成單步移動

圖4　分解完成整個問題

依次給出A針上只有4個盤的情況，如圖1～4所示.

利用前面每次的操作結(jié)果，同學(xué)們很快可以完成給定的任務(wù)，可以順其自然推理出：對于n個盤子需要移動2n-1次，把64個盤子都移動完畢約需1.8x1019次，假設(shè)每秒移動一次，約需一萬億年，不愧是世界末日問題，地球壽命才100億年.目前，由于計算機(jī)運算速度的限制，僅能找出問題的解決方法并解決較小n值的漢諾塔問題.

討論：漢諾塔問題屬于非數(shù)值問題，難以用數(shù)學(xué)公式表達(dá)其算法，可以從分析問題本身的規(guī)律入手.第一步，問題化簡，設(shè)A針上只有一個盤子，即n=1，則只需將1號盤從A針移到C針.第二步，問題分解，對于A針上有n（n＞1）個盤子的漢諾塔，可分為三個步驟求解：①將A針上n-1個盤子借助于C針移到B針；②把A針上剩下的一個盤子移到C針；③將B針上n-1個盤子借助于A針移到C針.

顯然，①、③兩步具有與原問題相同的性質(zhì)，只是在問題的規(guī)模上比原問題有所縮小，可用遞歸實現(xiàn).

整理上述分析結(jié)果，把第一步作為遞歸結(jié)束條件，將第二步分析得到的算法作為遞歸算法，可以寫出完整的遞歸算法描述.

定義一個函數(shù)movedisk（int n，char fromneedle，char tempneedle，char toneedle），該函數(shù)的功能是將fromneedle針上的n個盤子借助于tempneedle針移動到toneedlee針，這樣移動n個盤子的遞歸算法描述如下.

按照上述算法可編寫出如下C語言程序：

3任務(wù)驅(qū)動法教學(xué)內(nèi)容的展開

適當(dāng)對遞歸調(diào)用教學(xué)內(nèi)容的展開，在逐步求解的過程中培養(yǎng)學(xué)生的探索精神和分析、綜合歸納問題的能力.引導(dǎo)學(xué)生探索遞歸調(diào)用編程在其他方面應(yīng)用，總結(jié)遞歸調(diào)用編程的通用方法與思維.

3.1數(shù)值問題

可以表達(dá)為數(shù)學(xué)公式的問題，如求斐波那契數(shù)列的第n項、求非負(fù)整數(shù)N的階乘、求兩個整數(shù)的最大公約數(shù)等.

首先來看一個數(shù)值問題的遞歸算法的典型例子，斐波那契數(shù)列Fib（n）的遞推定義是：

按照上式，求第n項斐波那契數(shù)列的遞歸函數(shù)如下：

對于數(shù)值問題，由于可以表達(dá)為數(shù)學(xué)公式，所以可以從數(shù)學(xué)公式入手推導(dǎo)出問題的遞歸公式，然后確定問題的邊界條件，從而確定遞歸的算法和遞歸結(jié)束條件.

3.2非數(shù)值問題

對于本身難以用數(shù)學(xué)公式表達(dá)的問題，如著名的漢諾塔問題、八皇后、九連環(huán)問題等非數(shù)值問題，求解的一般方法是要設(shè)計一種算法，找到解決問題的一系列操作步驟.如果能夠找到解決問題的一系列遞歸操作過程，同樣可以用遞歸的方法解決這些非數(shù)值問題，尋找非數(shù)值問題的遞歸算法可以從分析問題本質(zhì)的規(guī)律入手，可以按照下列步驟進(jìn)行分析：（1）將問題進(jìn)行化簡與最大限度縮小問題規(guī)模，分析問題在最簡單情況下的求解方法與過程，這時的算法應(yīng)當(dāng)是最簡單的非遞歸算法.（2）將問題分解為若干個小問題，其中至少有一個小問題具有與原問題相同的性質(zhì)，只是在規(guī)模上比原問題有所縮小，將分解后的每個小問題作為一個整體，描述用這些較小的問題解決原來較大問題的算法.由第（2）步得到的算法就是一個解決原問題的遞歸算法，第（1）步將問題的規(guī)?？s到最小時的條件就是該遞歸算法的結(jié)束條件.

最后引導(dǎo)學(xué)生總結(jié)遞歸程序設(shè)計的思維與原理，適宜于用遞歸算法求解的問題的充分必要條件是：一是問題具有某種可借用的類同自身的子問題描述的性質(zhì)；二是某一有限步的子問題有直接的解存在.

編寫遞歸程序有兩個要點：一是要找到正確的遞歸算法公式，這是編寫遞歸程序的基礎(chǔ)；二是要確定遞歸算法的結(jié)束條件，這是決定遞歸程序是否能正常終止的關(guān)鍵.

任務(wù)驅(qū)動法課堂教學(xué)的最后，可以設(shè)計一些比較典型容易實現(xiàn)的任務(wù)，讓學(xué)生趁熱打鐵，通過完成任務(wù)，加深對教學(xué)內(nèi)容的掌握與理解.

4結(jié)語

遞歸算法在程序設(shè)計中十分有用.遞歸算法的實質(zhì)是把問題轉(zhuǎn)化為規(guī)?？s小了的同類問題的子問題.然后遞歸調(diào)用函數(shù)來表示問題的解.當(dāng)一個問題蘊(yùn)含了遞歸關(guān)系且結(jié)構(gòu)比較復(fù)雜時，采用遞歸算法能使程序變得簡潔和清晰，增加了程序的可讀性，并能夠很容易地解決一些用非遞歸算法很難解決的問題.

以任務(wù)驅(qū)動法來設(shè)計遞歸算法課堂教學(xué)內(nèi)容與過程，在任務(wù)驅(qū)動教學(xué)過程中培養(yǎng)學(xué)生的探索精神和分析問題的能力，激發(fā)學(xué)生的求知欲［3-4］，切實提高了課堂教學(xué)效果.

參考文獻(xiàn)：

［1］譚浩強(qiáng).C程序設(shè)計［M］.4版.北京：清華大學(xué)出版社，2010.

［2］嚴(yán)蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)（C語言版）［M］.北京：清華大學(xué)出版社，2004.

［3］唐大仕.“遞歸算法”微課教學(xué)設(shè)計——以“文科計算機(jī)基礎(chǔ)（下）”為例［J］.計算機(jī)教育，2013（17）：5-7.

［4］王婧.任務(wù)驅(qū)動法在計算機(jī)課程教學(xué)中的應(yīng)用 ［J］.計算機(jī)教育，2011（8）：51-55.

（責(zé)任編輯：邵曉軍）

中圖分類號：TP399；G642

文獻(xiàn)標(biāo)識碼：A

文章編號：1007-5348（2016）04-0075-05

［收稿日期］2016-03-01 ［基金項目］韶關(guān)學(xué)院教育教學(xué)改革研究項目（SYJY20131431）；韶關(guān)學(xué)院2013年度科研項目（韶學(xué)院〔2013〕205號）.

［作者簡介］楊平(1977-),男,湖南臨湘人,韶關(guān)學(xué)院數(shù)學(xué)與統(tǒng)計學(xué)院講師,碩士；研究方向：計算機(jī)應(yīng)用技術(shù).

Application of Task Driven Method in the Recursive Algorithm in Teaching Design

YANG Ping
（CollegeofMathematicsandStatistics，ShaoguanUniversity，Shaoguan512005，Guangdong，China）

Abstract:Recursionas aprogrammingalgorithmis widely usedinprogramdesign，whichis oneof thekey content of programming thinking.As an example，the application of task driven method in the recursive algorithm for classroomteaching，and designing interesting tasks，is easy to understand，to stimulate students’interest，to use props to decompose the scale of the task，to promote the understanding of the nature of the problem,in order to improve the students’interest in learning，to train students programming ability，and to improve the quality of teaching.

Key words:recursivealgorithm；programmingalgorithm；classroomteaching；programmingability