漢諾塔問(wèn)題遞歸算法與非遞歸算法比較

肖紅德

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

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

DOIDOI：10.11907/rjdk.173151

中圖分類(lèi)號(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 引言

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

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

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

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

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

2.1 算法準(zhǔn)備

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

本文所寫(xiě)程序均運(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次后取平均值，通過(guò)與遞歸算法時(shí)間對(duì)比，得出對(duì)于漢諾塔問(wèn)題，基于非遞歸思想的判斷移動(dòng)方向算法實(shí)現(xiàn)效率更高。

3 結(jié)語(yǔ)

從解決漢諾塔問(wèn)題的移盤(pán)規(guī)律出發(fā)，通過(guò)分析發(fā)現(xiàn)移盤(pán)順序特點(diǎn)，設(shè)計(jì)一種解決漢諾塔問(wèn)題的基于非遞規(guī)思想的移動(dòng)方向判斷算法實(shí)現(xiàn)過(guò)程。由于算法中利用了上次移動(dòng)目標(biāo)底座，在即將要移動(dòng)的盤(pán)子中排除了上次的目標(biāo)底座，因此在進(jìn)行底座之間的移盤(pá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）問(wèn)題的算法探索與研究[J].物聯(lián)網(wǎng)技術(shù)，2013（7）：48-49.

[4] 王明.梵塔問(wèn)題的兩個(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] 張建波.一種將遞歸過(guò)程轉(zhuǎn)換為非遞歸過(guò)程的方法研究[J].計(jì)算機(jī)教育，2017（8）：139-142.

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

[9] 盧芳芳，孫燮華，仇蘇愷，等.Hanoi塔問(wèn)題非遞歸的新算法[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ī)：專(zhuān)業(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é)任編輯：劉亭亭）