肖紅德

摘要：漢諾塔問題是一個古典數(shù)學(xué)問題，對于給定的盤子數(shù)量及每步移動盤子次序是確定的。因此，只要能夠確定盤子移動的規(guī)則，就可以通過計算機程序加以實現(xiàn)。遞歸算法雖然代碼簡單，但對于初學(xué)者而言，理解其內(nèi)涵存在困難，且算法執(zhí)行效率不高。提出一種基于非遞歸思想的移動方向判斷算法解決漢諾塔問題，通過與遞歸算法執(zhí)行時間比較，提出的判斷移動方向算法執(zhí)行效率更高，且算法思想相對更簡單、更容易理解。

關(guān)鍵詞：漢諾塔問題；遞歸算法；非遞歸算法；移動規(guī)律；算法效率

DOIDOI：10.11907/rjdk.173151

中圖分類號：TP312

文獻標識碼：A 文章編號：1672-7800（2018）008-0118-03

英文摘要Abstract：The Hanoi tower problem is a classical mathematical problem.Since the order of moving plate at each step is fixed for a given number of plates，the rules for moving plate can be readily determined by computer program.Although the code of recursive algorithm is simple，but for beginners，its meaning is not easy to understand，and the efficiency of its execution is not high.In this paper，we propose algorithm which is based on the non-recursive thinking and used to jude moving directions

to solve the problem of the Hanoi tower.By comparing with the execution time of the recursive algorithm，we can draw a conclusion that judge the algorithm proposed in this paper is more efficient，and its algorithmic thinking is relatively simple，easier to understand.

英文關(guān)鍵詞Key Words：the problem of hanoi tower；recursive algorithm； non-recursive algorithm； movement rule； algorithm efficiency

0 引言

漢諾塔問題是一個古典數(shù)學(xué)問題，也是計算機程序設(shè)計中用遞歸算法解題的經(jīng)典例子。問題描述如下：有3個底座A、B、C可以用來存放盤子，有64個大小不等的盤子，初始時64個盤子都在A座上且大盤子在下、小盤子在上（編號由上到下依次為1～64），若讓這64個盤子從A座移動到C座，在移動過程中需要滿足以下條件：每次只能移動一個盤子；A、B、C 3個底座上的盤子都需要保持大盤子在下、小盤子在上。要求給出每次移動盤子的具體步驟。

1 漢諾塔問題研究現(xiàn)狀

漢諾塔問題的研究已有大量成果。文獻[1-3]通過遞歸算法加以實現(xiàn)；文獻[4]給出關(guān)于移盤順序與移盤規(guī)律的兩個定理；文獻[5]中涉及多處對遞歸算法轉(zhuǎn)換為非遞歸算法的介紹，其中在介紹棧與二叉樹相關(guān)內(nèi)容時對遞歸與非遞歸結(jié)構(gòu)之間轉(zhuǎn)化以及在具體解決實際問題中有大量分析與具體實現(xiàn)過程；文獻[6-7]研究了遞歸算法轉(zhuǎn)換為非遞歸算法的過程；文獻[8-10]通過非遞歸算法實現(xiàn)該問題的求解；文獻[11-14]通過程序仿真演示移盤過程；文獻[15-16]給出了漢諾塔問題在教育教學(xué)改革中的具體應(yīng)用。

對于該問題，在很多計算機程序設(shè)計的教材與參考書中都有涉及，但有部分算法實現(xiàn)需要學(xué)習(xí)者有較為深厚的理論基礎(chǔ)，不能通過簡單的規(guī)則，使用比較基礎(chǔ)的語言進行簡明實現(xiàn)，致使不少初學(xué)者對該問題仍有困惑。

2 漢諾塔問題算法實現(xiàn)

2.1 算法準備

對于漢諾塔問題，給定n個盤子，其具有以下事實：

（1）對于n個圓盤，求解Hanoi問題，最少總移動次數(shù)是需要移動盤子次數(shù)的2n-1次，如文獻[9]中的定理1。

（2）對于任意給定的圓盤數(shù)量n與給定源底座與目標底座，移盤順序與移盤過程（每一次的移動圓盤號、源底座、目標底座）是確定的，如文獻[4]中的兩個定理。

（3）盤子在底座上的移動規(guī)律為：最小盤（第1號盤）移動與其它大盤（第2-n號盤）移動是交叉進行的，即移動一次最小盤，就要移動一次其它大盤。如果n為奇數(shù)，則最小盤子的移動規(guī)律是A→C→B→A…的循環(huán)移動，即先由底座A移動到底座C，再移動一次大盤子，再將最小的盤子由底座C移動到底座B，再移動一次大盤子，再將最小盤子底座B移動到底座A，再移動一次大盤子…；如果n為偶數(shù)，則最小盤子的移動規(guī)律是A→B→C→A…的循環(huán)移動；大盤子移動的規(guī)律是在兩次最小盤子移動之間進行的。

（4）每個盤子需要移動的次數(shù)是確定的，每個盤子需要移動的次數(shù)為2n-i。

對于事實（4）的證明：

①當n=1時，i=1，只需將一個盤子從底座A移動到底座C，結(jié)論成立。

②假設(shè)n=k（k≥1）時結(jié)論成立，即每個盤子需要移動的次數(shù)為2n-i。

③當n=k+1（k≥1）時，由漢諾特問題的遞歸調(diào)用算法可知，前k個盤子需要整體移動2次，即前k個盤子移動的次數(shù)是當n=k（k≥1）時的2倍，表示為2×2k-i=2（k+1）-i；第n=k+1（k≥1）個盤子只需移動一個盤子，表示為2n-（k+1），即當n=k+1（k≥1）時，每個盤子移動的次數(shù)2n-i成立。

通過對漢諾塔問題算法過程特點的分析，提出一種操作更簡單、效率更高的算法實現(xiàn)過程。

通過對移盤順序在底座之間移動規(guī)律的分析得出：在一個底座得到一個最小盤子，之后一次移盤必定在其它兩個底座之間進行。如果其它兩個底座都沒有盤子，則算法結(jié)束；如果其它兩個底座上只有一個底座有盤子，則從有盤子的底座移向沒有盤子的底座；如果其它兩個底座都有盤子，則從底座頂端盤子小的一個底座移動到另一個底座，即在判斷其它兩個底座從一個底座移向另一個底座之前需要判斷這兩個底座上最頂端的盤子哪個小，移盤方向是從底座上最頂端盤子小的一個底座移向另一個底座。在實現(xiàn)過程中，把每個底座用一個數(shù)組表示，每次數(shù)組操作都在數(shù)組尾部進行，移出一個盤子表示數(shù)組減少一個元素，移入一個元素表示數(shù)組增加一個元素，類似于棧的出棧與入棧操作。按照該操作規(guī)律，提出判斷移動方向算法。

判斷移動方向算法是在排除上次移入最小盤子（編號為1的盤子）底座的基礎(chǔ)上判斷在剩余兩個底座中，由哪個底座移入另一個底座的算法。判斷準則為：哪個底座上最上面盤子小則哪個作為移出底座，另一個作為移入底座；如果其中一個底座上沒有盤子，則將非空盤底座作為移出底座，另一個作為移入底座；如果兩個底座都沒有盤子，則移動盤子結(jié)束。

2.2 算法實現(xiàn)

在算法實現(xiàn)過程中，采取一些對比兩種算法執(zhí)行效率一致性的措施，具體如下：每個底座都使用一個對應(yīng)的數(shù)組表示，為簡化輸出過程，程序中將移盤操作簡化為對應(yīng)底座移出與移入數(shù)據(jù)的操作，即簡單的賦值操作。移動盤子采用對應(yīng)數(shù)組元素賦值的方式表示，每個數(shù)組元素的下標采用指針變量的形式指向等。對于類似的操作，采用一致的處理辦法表達，這樣的處理結(jié)果才能體現(xiàn)出不同算法思想在執(zhí)行效率上的差別。

2.3 運行時間測試

本文所寫程序均運行于虛擬機VMware-workstation_full_12.1.1.6932下，主機處理器為：Intel（R） Core（TM） i7-4790 CPU @ 3.60GHz，虛擬機下使用的系統(tǒng)為windows XP，內(nèi)存1G，處理器1個。由于每次運行程序需要的時間有差別，所得到的時間都是在運行3次后取平均值，通過與遞歸算法時間對比，得出對于漢諾塔問題，基于非遞歸思想的判斷移動方向算法實現(xiàn)效率更高。

3 結(jié)語

從解決漢諾塔問題的移盤規(guī)律出發(fā)，通過分析發(fā)現(xiàn)移盤順序特點，設(shè)計一種解決漢諾塔問題的基于非遞規(guī)思想的移動方向判斷算法實現(xiàn)過程。由于算法中利用了上次移動目標底座，在即將要移動的盤子中排除了上次的目標底座，因此在進行底座之間的移盤方向時只需判斷其它兩個底座，哪個是源底座哪個是目標底座即可，直到剩余這兩個底座都為空時，則完成了目標求解。

參考文獻：

[1] 譚浩強.C程序設(shè)計（第四版）[M].北京：清華大學(xué)出版社，2010.

[2] 吳曉晨.遞歸程序設(shè)計教學(xué)方法的研究[J].天津科技，2017，44（1）：69-73.

[3] 姚云霞.對漢諾塔（Hanoi）問題的算法探索與研究[J].物聯(lián)網(wǎng)技術(shù)，2013（7）：48-49.

[4] 王明.梵塔問題的兩個定理[J].應(yīng)用數(shù)學(xué)，1999（2）：112-114.

[5] 嚴蔚敏，陳文博.數(shù)據(jù)結(jié)構(gòu)及應(yīng)用算法教程[M].北京：清華大學(xué)出版社，2011.

[6] 戴莉萍，黃龍軍，劉清華.自底向上記錄式Hanoi塔非遞歸算法[J].實驗科學(xué)與技術(shù)，2016，14（1）：51-54.

[7] 張建波.一種將遞歸過程轉(zhuǎn)換為非遞歸過程的方法研究[J].計算機教育，2017（8）：139-142.

[8] 李玉華，崔鳳云，劉曉慶.漢諾塔問題的層次迭代算法[J].計算機工程與應(yīng)用，2008，44（35）：73-75.

[9] 盧芳芳，孫燮華，仇蘇愷，等.Hanoi塔問題非遞歸的新算法[J].計算機工程與應(yīng)用，2006，42（17）：108-110.

[10] 趙東躍.漢諾塔非遞歸算法研究[J].計算機應(yīng)用與軟件，2008，25（5）：241-243.

[11] 戴莉萍，黃龍軍，劉清華，等.記錄式Hanoi塔非遞歸算法及快速仿真[J].電氣電子教學(xué)學(xué)報，2015，37（6）：112-116.

[12] 李健.漢諾塔算法演示系統(tǒng)的設(shè)計與實現(xiàn)[J].現(xiàn)代計算機：專業(yè)版，2011（24）：76-80.

[13] 衛(wèi)洪春.圖形環(huán)境下的漢諾塔演示[J].電子設(shè)計工程，2014（15）：8-10.

[14] 李兆歆，張大坤.基于VSL語言的三維動態(tài)交互移動實現(xiàn)及其應(yīng)用[J].計算機工程與設(shè)計，2010，31（2）：455-458.

[15] 曾夏玲.基于計算思維能力培養(yǎng)的“輕游戲”教學(xué)模式初探[J].職教論壇，2015（11）：79-82.

[16] 李清霞，孫欣.益智課堂，數(shù)學(xué)核心素養(yǎng)踐行之地——以“漢諾塔”活動課為例[J].中國教師，2017（10）.

（責任編輯：劉亭亭）