基于c++語言的漢諾塔微課設計與實現

幺連福

（吉林化工學院，吉林132021）

?

基于c++語言的漢諾塔微課設計與實現

幺連福

（吉林化工學院，吉林132021）

摘要：本文對計算機專業基礎課數據結構中的典型遞歸調用模型（漢諾塔問題）采用微課程模式授課的方案，編寫了基于c++語言的漢諾塔微課程序。

關鍵詞：c++；堆棧；遞歸；微課

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

1　引言

1.1“微課”及其特點

“微課”是指為使學習者自足學習獲得最佳效果，經過精心的信息化教學設計，以媒體形式展

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

1.2遞歸算法及其特點

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

2　遞歸調用微課程模式授課的方案

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

2.1問題引入

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

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

2.2微課提綱

2.2.1問題分析

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

2.2.2遞歸模型與程序概述

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

2.2.3程序運行特點

（1）運行過程中動態展現移動的過程，是學生深刻理解遞歸調用算法是如何實現的，有利于

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

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

時間，以驗證遞歸調用所用時間與漢諾塔階數的指數型遞增關系。

2.2.4知識總結

（1）遞歸算法的優點結構清晰，可讀性強，而且容易用數學歸納法來證明算法的正確性，因此它為設計算法、調試程序帶來很大方便。

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

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

（4）遞歸的一般模式

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

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

2.2.5思考題

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

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

3　結束語

遞歸調用問題是數據結構課程中一個重要的知識點，也是數據結構課程中最難的部分之一，采用該授課方式后，通過動態演示，激發了學生的學習興趣，調動其積極性，加深了對遞歸算法的理解，獲得了較好的教學效果。

參考文獻：

［1］徐翀.微課在數據結構課程中的應用［J］.中國教育信息化，2014，（12）:37-39.

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

［3］蔣詠華.高校微課建設問題及其對策研究［J］.中國現代教育裝備，2014，（23）:73-75.

［4］陳坤.地方高校微課的建設與應用研究—以山西大同大學為例［D］.山西師范大學，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

文獻標識碼：A

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

收稿日期：2015-12-14

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