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

幺連福

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

?

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

幺連福

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

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

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

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

1　引言

1.1“微課”及其特點

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

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

1.2遞歸算法及其特點

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

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

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

2.1問題引入

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

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

2.2微課提綱

2.2.1問題分析

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

2.2.2遞歸模型與程序概述

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

2.2.3程序運行特點

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

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

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

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

2.2.4知識總結(jié)

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

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

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

（4）遞歸的一般模式

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

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

2.2.5思考題

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

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

3　結(jié)束語

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

參考文獻：

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

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

［3］蔣詠華.高校微課建設(shè)問題及其對策研究［J］.中國現(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

中圖分類號：O141.3

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

文章編號：1672-545X（2016）03-0268-02

收稿日期：2015-12-14

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