幺連福

（吉林化工學(xué)院，吉林132021）

?

基于c++語言的漢諾塔微課設(shè)計(jì)與實(shí)現(xiàn)

幺連福

（吉林化工學(xué)院，吉林132021）

摘要：本文對(duì)計(jì)算機(jī)專業(yè)基礎(chǔ)課數(shù)據(jù)結(jié)構(gòu)中的典型遞歸調(diào)用模型（漢諾塔問題）采用微課程模式授課的方案，編寫了基于c++語言的漢諾塔微課程序。

關(guān)鍵詞：c++；堆棧；遞歸；微課

遞歸算法是一種直接或者間接地調(diào)用自身算法的過程，在計(jì)算機(jī)編寫程序中，遞歸算法對(duì)解決某類問題是十分有效的，但在掌握該算法方面對(duì)于大多數(shù)學(xué)習(xí)者來說往往具有一定的困難，特別是對(duì)具體問題抽象出其遞歸模型來說難度較大［1］。根據(jù)學(xué)生的認(rèn)知特點(diǎn)和接受水平本文采用微課程模式對(duì)該問題進(jìn)行了探討，編寫了基于c++語言的漢諾塔微課程序?qū)崿F(xiàn)。

1　引言

1.1“微課”及其特點(diǎn)

“微課”是指為使學(xué)習(xí)者自足學(xué)習(xí)獲得最佳效果，經(jīng)過精心的信息化教學(xué)設(shè)計(jì)，以媒體形式展

開的圍繞某個(gè)知識(shí)點(diǎn)或教學(xué)環(huán)節(jié)開展的簡(jiǎn)短、完整的教學(xué)活動(dòng)。其主要特點(diǎn)：教學(xué)主題（或教學(xué)活動(dòng)）具體，教學(xué)目標(biāo)明確；教學(xué)設(shè)計(jì)精細(xì)，教學(xué)內(nèi)容精煉或教學(xué)活動(dòng)精彩；視頻格式符合流媒體要求、容量小，適合移動(dòng)設(shè)備閱讀［2-3］。

1.2遞歸算法及其特點(diǎn)

在數(shù)學(xué)與計(jì)算機(jī)科學(xué)中，遞歸算法是指在函數(shù)的定義中直接或間接使用函數(shù)自身的方法。它的實(shí)質(zhì)往往把問題轉(zhuǎn)化為規(guī)?？s小了的同類問題的子問題。在計(jì)算機(jī)編寫程序中，遞歸算法對(duì)解決一大類問題是十分有效的，它往往使算法的描述簡(jiǎn)潔而且易于理解。因此掌握好遞歸模型的抽象和實(shí)現(xiàn)與之對(duì)應(yīng)的遞歸算法是非常重要的。

2　遞歸調(diào)用微課程模式授課的方案

該課程整體設(shè)計(jì)主要有問題引入、授課提綱、具體過程和課程總結(jié)的微課模式［4］，具體內(nèi)容如下：

2.1問題引入

為了吸引學(xué)生注意力，首先以法國(guó)數(shù)學(xué)家愛德華·盧卡斯曾編寫過一個(gè)印度的古老傳說為背

景，給出漢諾塔問題：分別有3個(gè)標(biāo)號(hào)為A，B，C的柱子，在A柱子從下到上地穿好了由大到小的n只盤子，借助于B和C柱子，按照下面的法則移動(dòng)這些盤子：一次只移動(dòng)一只盤子，不管在哪根柱子上，小盤子必須在大盤子上面，最后把A柱子上的盤子都移動(dòng)到C柱子上面，試計(jì)算至少總共需要移動(dòng)的次數(shù)和具體移動(dòng)過程。

2.2微課提綱

2.2.1問題分析

以下為敘述方便，把各個(gè)柱子用其對(duì)應(yīng)字母代替，假設(shè)有2只盤子，不妨編號(hào)為大、小其移動(dòng)過程如下所示：把A上的小盤子移動(dòng)到B上記為：小（A）－＞B；再把A上的大盤子移動(dòng)到C上記為：大（A）－＞C；最后再把B上的小盤子移動(dòng)到C上記為：小（B）－＞C，顯然一共要移動(dòng)3次，不妨記為f（2）=3.對(duì)于具有3只盤子的情況先考慮借助于C把位于A較上面的2只盤子按移動(dòng)原則移動(dòng)到B上，再把A上面的最大盤子移動(dòng)到C上，最后借助于A把B上的2個(gè)盤子移動(dòng)到C上，移動(dòng)次數(shù)是f（3）=f（2）+1+f（2）=2*f（2）+1.

2.2.2遞歸模型與程序概述

在以上分析的基礎(chǔ)上進(jìn)一步分析，對(duì)于n+1只盤子的情況可以由一下3個(gè)步驟完成：借助于C把位于A較上面的n只盤子按移動(dòng)原則移動(dòng)到B上；再把A上面的最大盤子移動(dòng)到C上；然后再借助于A把B上的n只盤子移動(dòng)到C上，從而推導(dǎo)出該問題的遞歸模型：f（n+1）=2*f（n）+1，如果設(shè)其對(duì)應(yīng)c++函數(shù)為hannoi（n+1，A，B，C），上面描述移動(dòng)n+1只盤子的主要過程，可分別調(diào)用hannoi（n，A，C，B）和hannoi（n，B，A，C）來完成，直到n=2為止，與之對(duì)應(yīng)的程序采用C++語言完成。

2.2.3程序運(yùn)行特點(diǎn)

（1）運(yùn)行過程中動(dòng)態(tài)展現(xiàn)移動(dòng)的過程，是學(xué)生深刻理解遞歸調(diào)用算法是如何實(shí)現(xiàn)的，有利于

以后對(duì)具體問題抽象和使用遞歸算法。

（2）漢諾塔階數(shù)（盤子只數(shù)）在考慮時(shí)間可行性的前提下由使用者任意輸入，同時(shí)記錄運(yùn)行

時(shí)間，以驗(yàn)證遞歸調(diào)用所用時(shí)間與漢諾塔階數(shù)的指數(shù)型遞增關(guān)系。

2.2.4知識(shí)總結(jié)

（1）遞歸算法的優(yōu)點(diǎn)結(jié)構(gòu)清晰，可讀性強(qiáng)，而且容易用數(shù)學(xué)歸納法來證明算法的正確性，因此它為設(shè)計(jì)算法、調(diào)試程序帶來很大方便。

（2）使用遞歸的策略必須確定遞歸公式明確的遞歸結(jié)束條件，也稱遞歸出口條件。漢諾塔問題的遞歸結(jié)束條件為n=2.

（3）避免棧溢出在遞歸調(diào)用的過程當(dāng)中系統(tǒng)為每一層的返回點(diǎn)、局部量等開辟了棧來存儲(chǔ)。遞歸次數(shù)過多容易造成棧溢出和運(yùn)行效率較低。

（4）遞歸的一般模式

recursion（int n，其他參數(shù)列表）｛If n==出口參數(shù)值｛輸出邊界條件及其它必要操作｝

else｛recursion（n-1，其它實(shí)參數(shù)表）及其它必要操作｝｝

2.2.5思考題

（1）當(dāng)n=64時(shí)，由遞歸函數(shù)可知需要移動(dòng)盤子的次數(shù)是2^64-1，假如每秒鐘移動(dòng)一只盤子，共需多長(zhǎng)時(shí)間？

（2）在充分理解遞歸算法的基礎(chǔ)上，自行試設(shè)計(jì)漢諾塔非遞歸程序，試比較兩者對(duì)相同階數(shù)的的運(yùn)行時(shí)間。

3　結(jié)束語

遞歸調(diào)用問題是數(shù)據(jù)結(jié)構(gòu)課程中一個(gè)重要的知識(shí)點(diǎn)，也是數(shù)據(jù)結(jié)構(gòu)課程中最難的部分之一，采用該授課方式后，通過動(dòng)態(tài)演示，激發(fā)了學(xué)生的學(xué)習(xí)興趣，調(diào)動(dòng)其積極性，加深了對(duì)遞歸算法的理解，獲得了較好的教學(xué)效果。

參考文獻(xiàn)：

［1］徐翀.微課在數(shù)據(jù)結(jié)構(gòu)課程中的應(yīng)用［J］.中國(guó)教育信息化，2014，（12）:37-39.

［2］陳智敏，呂巾嬌，劉美鳳.我國(guó)高校教師微課教學(xué)設(shè)計(jì)現(xiàn)狀研究［J］.現(xiàn)代教育技術(shù)，2014，（8）:20-23.

［3］蔣詠華.高校微課建設(shè)問題及其對(duì)策研究［J］.中國(guó)現(xiàn)代教育裝備，2014，（23）:73-75.

［4］陳坤.地方高校微課的建設(shè)與應(yīng)用研究—以山西大同大學(xué)為例［D］.山西師范大學(xué)，2015，（4）：31-37.

C++language Course Design and Implementation Based on Micro Hanoi

YAO Lian-fu
（Department of Information and Control，Chemical Industry College of，Jilin 132021，China）

Abstract：Recursive algorithm is one of important algorithm in data structure Course，In this paper，author devised the micro class scheme of recursive model（Tower of Hanoi），and the programming.

Key words：c++；stack；recursion；micro lesson

中圖分類號(hào)：O141.3

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

文章編號(hào)：1672-545X（2016）03-0268-02

收稿日期：2015-12-14

作者簡(jiǎn)介：幺連福（1971-），男，吉林四平人，碩士，副教授，研究方向：算法分析和相關(guān)軟件開發(fā)。