漢諾塔問題遞歸算法與非遞歸算法比較

肖紅德

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

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

DOIDOI：10.11907/rjdk.173151

中圖分類號(hào)：TP312

文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：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 引言

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

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

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

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

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

2.1 算法準(zhǔn)備

對(duì)于漢諾塔問題，給定n個(gè)盤子，其具有以下事實(shí)：

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

（2）對(duì)于任意給定的圓盤數(shù)量n與給定源底座與目標(biāo)底座，移盤順序與移盤過程（每一次的移動(dòng)圓盤號(hào)、源底座、目標(biāo)底座）是確定的，如文獻(xiàn)[4]中的兩個(gè)定理。

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

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

對(duì)于事實(shí)（4）的證明：

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

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

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

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

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

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

2.2 算法實(shí)現(xiàn)

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

2.3 運(yùn)行時(shí)間測(cè)試

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

3 結(jié)語(yǔ)

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

參考文獻(xiàn)：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

（責(zé)任編輯：劉亭亭）