漢諾塔（Tower?of?Hanoi），又稱(chēng)河內(nèi)塔，是一個(gè)源于印度古老傳說(shuō)的益智玩具。大梵天創(chuàng)造世界的時(shí)候做了三根金剛石柱子，在一根柱子上從下往上按照大小順序摞著64片黃金圓盤(pán)。大梵天命令婆羅門(mén)把圓盤(pán)從下面開(kāi)始按大小順序重新擺放在另一根柱子上。并且規(guī)定，在小圓盤(pán)上不能放大圓盤(pán)，在三根柱子之間一次只能移動(dòng)一個(gè)圓盤(pán)。

2020年8月3日，夏焱以33.039秒的成績(jī)成功打破6層漢諾塔吉尼斯世界紀(jì)錄。

概述

有三根桿子A，B，C。A桿上有N個(gè) - N>1穿孔圓盤(pán)，盤(pán)的尺寸由下到上依次變小。要求按下列規(guī)則將所有圓盤(pán)移至C桿： 每次只能移動(dòng)一個(gè)圓盤(pán)； 大盤(pán)不能疊在小盤(pán)上面。 提示：可將圓盤(pán)臨時(shí)置于B桿，也可將從A桿移出的圓盤(pán)重新移回A桿，但都必須遵循上述兩條規(guī)則。

由來(lái)及傳說(shuō)

由來(lái)

法國(guó)數(shù)學(xué)家愛(ài)德華·盧卡斯曾編寫(xiě)過(guò)一個(gè)印度的古老傳說(shuō)：在世界中心貝拿勒斯（在印度北部）的圣廟里，一塊黃銅板上插著三根寶石針。印度教的主神梵天在創(chuàng)造世界的時(shí)候，在其中一根針上從下到上地穿好了由大到小的64片金片，這就是所謂的漢諾塔。不論白天黑夜，總有一個(gè)僧侶在按照下面的法則移動(dòng)這些金片：一次只移動(dòng)一片，不管在哪根針上，小片必須在大片上面。僧侶們預(yù)言，當(dāng)所有的金片都從梵天穿好的那根針上移到另外一根針上時(shí)，世界就將在一聲霹靂中消滅，而梵塔、廟宇和眾生也都將同歸于盡。

不管這個(gè)傳說(shuō)的可信度有多大，如果考慮一下把64片金片，由一根針上移到另一根針上，并且始終保持上小下大的順序。這需要多少次移動(dòng)呢?這里需要遞歸的方法。假設(shè)有n片，移動(dòng)次數(shù)是f - n.顯然f - 1=1,f - 2=3,f - 3=7，且f - k+1=2*f - k+1。此后不難證明f - n=2^n-1。n=64時(shí)，

假如每秒鐘一次，共需多長(zhǎng)時(shí)間呢？一個(gè)平年365天有31536000 秒，閏年366天有31622400秒，平均每年31556952秒，計(jì)算一下：

18446744073709551615秒

這表明移完這些金片需要5845.54億年以上，而地球存在至今不過(guò)45億年，太陽(yáng)系的預(yù)期壽命據(jù)說(shuō)也就是數(shù)百億年。真的過(guò)了5845.54億年，不說(shuō)太陽(yáng)系和銀河系，至少地球上的一切生命，連同梵塔、廟宇等，都早已經(jīng)灰飛煙滅。

印度傳說(shuō)

和漢諾塔故事相似的，還有另外一個(gè)印度傳說(shuō)：舍罕王打算獎(jiǎng)賞國(guó)際象棋的發(fā)明人──宰相西薩·班·達(dá)依爾。國(guó)王問(wèn)他想要什么，他對(duì)國(guó)王說(shuō)：“陛下，請(qǐng)您在這張棋盤(pán)的第1個(gè)小格里賞給我一粒麥子，在第2個(gè)小格里給2粒，第3個(gè)小格給4粒，以后每一小格都比前一小格加一倍。請(qǐng)您把這樣擺滿棋盤(pán)上所有64格的麥粒，都賞給您的仆人吧！”國(guó)王覺(jué)得這個(gè)要求太容易滿足了，就命令給他這些麥粒。當(dāng)人們把一袋一袋的麥子搬來(lái)開(kāi)始計(jì)數(shù)時(shí)，國(guó)王才發(fā)現(xiàn)：就是把全印度甚至全世界的麥粒全拿來(lái)，也滿足不了那位宰相的要求。

那么，宰相要求得到的麥粒到底有多少呢？總數(shù)為

1+2+2^2 + … +2^63=2^64-1

等于移完漢諾塔的步驟數(shù)——共3853步。我們已經(jīng)知道這個(gè)數(shù)字有多么大了。人們估計(jì)，全世界兩千年也難以生產(chǎn)這么多麥子！

相關(guān)預(yù)言

有預(yù)言說(shuō)，這件事完成時(shí)宇宙會(huì)在一瞬間閃電式毀滅。也有人相信婆羅門(mén)至今還在一刻不停地搬動(dòng)著圓盤(pán)。

其他相關(guān)

與宇宙壽命

如果移動(dòng)一個(gè)圓盤(pán)需要1秒鐘的話，等到64個(gè)圓盤(pán)全部重新落在一起，宇宙被毀滅是什么時(shí)候呢？

讓我們來(lái)考慮一下64個(gè)圓盤(pán)重新摞好需要移動(dòng)多少次吧。1個(gè)的時(shí)候當(dāng)然是1次，2個(gè)的時(shí)候是3次，3個(gè)的時(shí)候就用了7次……這實(shí)在是太累了因此讓我們邏輯性的思考一下吧。3個(gè)的時(shí)候能夠移動(dòng)最大的3盤(pán)時(shí)如圖所示。到此為止用了7次。

接下來(lái)如右圖，在上面再放上3個(gè)圓盤(pán)時(shí)還要用7次（把3個(gè)圓盤(pán)重新放在一起需要的次數(shù)）。因此，4個(gè)的時(shí)候是“3個(gè)圓盤(pán)重新摞在一起的次數(shù)”+1次+“3個(gè)圓盤(pán)重新摞在一起需要的次數(shù)”=2x“3個(gè)圓盤(pán)重新摞在一起的次數(shù)”+1次=15次。

那么，n個(gè)的時(shí)候是2x“（n-1）個(gè)圓盤(pán)重新摞在一起的次數(shù)”+1次。由于1 個(gè)的時(shí)候是1次，結(jié)果n個(gè)的時(shí)候?yàn)椋?的n次方減1）次。

1個(gè)圓盤(pán)的時(shí)候 2的1次方減1

2個(gè)圓盤(pán)的時(shí)候 2的2次方減1

3個(gè)圓盤(pán)的時(shí)候 2的3次方減1

4個(gè)圓盤(pán)的時(shí)候 2的4次方減1

5個(gè)圓盤(pán)的時(shí)候 2的5次方減1

……..

n個(gè)圓盤(pán)的時(shí)候 2的n次方減1

也就是說(shuō)，n=64的時(shí)候是（2的64次方減1）次。

因此，如果移動(dòng)一個(gè)圓盤(pán)需要1秒的話，

宇宙的壽命=2的64次方減1（秒）

2的64次方減1到底有多大呢？動(dòng)動(dòng)計(jì)算器，答案是一個(gè)二十位的數(shù)字約是

1.84467440*10^19

用一年=60秒x60分x24小時(shí)x365天來(lái)算的話，大約有5800億年吧。

太陽(yáng)及其行星形成于50億年前，其壽命約為100億年。

漢諾塔問(wèn)題在數(shù)學(xué)界有很高的研究?jī)r(jià)值，而且至今還在被一些數(shù)學(xué)家們所研究。

也是我們所喜歡玩的一種益智游戲，它可以幫助開(kāi)發(fā)智力，激發(fā)我們的思維。

經(jīng)典題目

有三根相鄰的柱子，標(biāo)號(hào)為A,B,C，A柱子上從下到上按金字塔狀疊放著n個(gè)不同大小的圓盤(pán)，要把所有盤(pán)子一個(gè)一個(gè)移動(dòng)到柱子B上，并且每次移動(dòng)同一根柱子上都不能出現(xiàn)大盤(pán)子在小盤(pán)子上方，請(qǐng)問(wèn)至少需要多少次移動(dòng)，設(shè)移動(dòng)次數(shù)為H - n）。

首先我們肯定是把上面n-1個(gè)盤(pán)子移動(dòng)到柱子C上，然后把最大的一塊放在B上，最后把C上的所有盤(pán)子移動(dòng)到B上，由此我們得出表達(dá)式：

H⑴ = 1

H - n = 2*H - n-1）+1 - n>1）

那么我們很快就能得到H - n）的一般式：

H - n = 2^n – 1 - n>0

并且這種方法的確是最少次數(shù)的，證明非常簡(jiǎn)單，可以嘗試從2個(gè)盤(pán)子的移動(dòng)開(kāi)始證，你可以試試。

進(jìn)一步加深問(wèn)題（解法原創(chuàng)*_*）：

假如現(xiàn)在每種大小的盤(pán)子都有兩個(gè)，并且是相鄰的，設(shè)盤(pán)子個(gè)數(shù)為2n，問(wèn)：⑴假如不考慮相同大小盤(pán)子的上下要多少次移動(dòng)，設(shè)移動(dòng)次數(shù)為J - n）；⑵只要保證到最后B上的相同大小盤(pán)子順序與A上時(shí)相同，需要多少次移動(dòng)，設(shè)移動(dòng)次數(shù)為K - n）。

⑴中的移動(dòng)相當(dāng)于是把前一個(gè)問(wèn)題中的每個(gè)盤(pán)子多移動(dòng)一次，也就是：

J - n = 2*H - n = 2*（2^n – 1） = 2^ - n+1）-2

在分析⑵之前

，我們來(lái)說(shuō)明一個(gè)現(xiàn)象，假如A柱子上有兩個(gè)大小相同的盤(pán)子，上面一個(gè)是黑色的，下面一個(gè)是白色的，我們把兩個(gè)盤(pán)子移動(dòng)到B上，需要兩次，盤(pán)子順序?qū)⒆兂珊诘脑谙?，白的在上，然后再把B上的盤(pán)子移動(dòng)到C上，需要兩次，盤(pán)子順序?qū)⑴cA上時(shí)相同，由此我們歸納出當(dāng)相鄰兩個(gè)盤(pán)子都移動(dòng)偶數(shù)次時(shí)，盤(pán)子順序?qū)⒉蛔儯駝t上下顛倒。

現(xiàn)在回到最開(kāi)始的問(wèn)題，n個(gè)盤(pán)子移動(dòng)，上方的n-1個(gè)盤(pán)子總移動(dòng)次數(shù)為2*H - n-1），所以上方n-1個(gè)盤(pán)子的移動(dòng)次數(shù)必定為偶數(shù)次，最后一個(gè)盤(pán)子移動(dòng)次數(shù)為1次。

討論問(wèn)題⑵，

綜上兩點(diǎn)，可以得出，要把A上2n個(gè)盤(pán)子移動(dòng)到B上，首先可以得出上方的2n-2個(gè)盤(pán)子必定移動(dòng)偶數(shù)次，所以順序不變，移動(dòng)次數(shù)為：

J - n-1） = 2^n-2

然后再移動(dòng)倒數(shù)第二個(gè)盤(pán)子，移動(dòng)次數(shù)為2*J - n-1）+1 = 2^ - n+1）-3，

最后移動(dòng)最底下一個(gè)盤(pán)子，所以總的移動(dòng)次數(shù)為：

K - n = 2*（2*J - n-1）+1）+1 = 2*（2^ - n+1）-3）+1 = 2^ - n+2）-5

開(kāi)天辟地的神勃拉瑪（和中國(guó)的盤(pán)古差不多的神吧）在一個(gè)廟里留下了三根金剛石的棒，第一根上面套著64個(gè)圓的金片，最大的一個(gè)在底下，其余一個(gè)比一個(gè)小，依次疊上去，廟里的眾僧不倦地把它們一個(gè)個(gè)地從這根棒搬到另一根棒上，規(guī)定可利用中間的一根棒作為幫助，但每次只能搬一個(gè)，而且大的不能放在小的上面。計(jì)算結(jié)果非?？植溃ㄒ苿?dòng)圓片的次數(shù)）大約是1.84467440*10^19，眾僧們即便是耗盡畢生精力也不可能完成金片的移動(dòng)了。

算法介紹

其實(shí)算法非常簡(jiǎn)單，當(dāng)盤(pán)子的個(gè)數(shù)為n時(shí)，移動(dòng)的次數(shù)應(yīng)等于2^n – 1（有興趣的可以自己證明試試看）。后來(lái)一位美國(guó)學(xué)者發(fā)現(xiàn)一種出人意料的簡(jiǎn)單方法，只要輪流進(jìn)行兩步操作就可以了。首先把三根柱子按順序排成品字型，把所有的圓盤(pán)按從大到小的順序放在柱子A上，根據(jù)圓盤(pán)的數(shù)量確定柱子的排放順序：若n為偶數(shù)，按順時(shí)針?lè)较蛞来螖[放 A B C；

若n為奇數(shù)，按順時(shí)針?lè)较蛞来螖[放 A C B。

⑴按順時(shí)針?lè)较虬褕A盤(pán)1從現(xiàn)在的柱子移動(dòng)到下一根柱子，即當(dāng)n為偶數(shù)時(shí)，若圓盤(pán)1在柱子A，則把它移動(dòng)到B；若圓盤(pán)1在柱子B，則把它移動(dòng)到C；若圓盤(pán)1在柱子C，則把它移動(dòng)到A。

⑵接著，把另外兩根柱子上可以移動(dòng)的圓盤(pán)移動(dòng)到新的柱子上。即把非空柱子上的圓盤(pán)移動(dòng)到空柱子上，當(dāng)兩根柱子都非空時(shí)，移動(dòng)較小的圓盤(pán)。這一步?jīng)]有明確規(guī)定移動(dòng)哪個(gè)圓盤(pán)，你可能以為會(huì)有多種可能性，其實(shí)不然，可實(shí)施的行動(dòng)是唯一的。

⑶反復(fù)進(jìn)行⑴⑵操作，最后就能按規(guī)定完成漢諾塔的移動(dòng)。

所以結(jié)果非常簡(jiǎn)單，就是按照移動(dòng)規(guī)則向一個(gè)方向移動(dòng)金片：

如3階漢諾塔的移動(dòng)：A→C,A→B,C→B,A→C,B→A,B→C,A→C。

易語(yǔ)言

子程序?漢諾塔盤(pán)子運(yùn)動(dòng)

.參數(shù)?盤(pán)子數(shù)，整數(shù)型

.參數(shù)?柱子甲，文本型

.參數(shù)?柱子乙，文本型

.參數(shù)?柱子丙，文本型

.如果?（盤(pán)子數(shù)?=?1）

'?如果只有一個(gè)盤(pán)，則直接將它從柱子一移動(dòng)到柱子三

移動(dòng)?（1，柱子甲，柱子丙）

.否則

'?把1?~?n?–?1個(gè)盤(pán)從柱子一移動(dòng)到柱子二，用柱子三作為中轉(zhuǎn)

漢諾塔盤(pán)子運(yùn)動(dòng)?（盤(pán)子數(shù)?－?1，柱子甲，柱子丙，柱子乙）

'?把第n個(gè)盤(pán)從柱子一移動(dòng)到柱子三

移動(dòng)?（盤(pán)子數(shù)，柱子甲，柱子丙）

'?把1?~?n?–?1個(gè)盤(pán)從柱子二移動(dòng)到柱子三，用柱子一作為中轉(zhuǎn)

漢諾塔盤(pán)子運(yùn)動(dòng)?（盤(pán)子數(shù)?－?1，柱子乙，柱子甲，柱子丙）

.如果結(jié)束

.子程序?移動(dòng)

.參數(shù)?盤(pán)子號(hào)，整數(shù)型

.參數(shù)?甲柱子，文本型

.參數(shù)?乙柱子，文本型

路徑?=?路徑?+?“步驟”?+?到文本?（步驟）?+?“：”?+?“把”?+?到文本?（盤(pán)子號(hào)）?+?“號(hào)圓盤(pán)從柱子?”?+?甲柱子?+?“?移動(dòng)到”?+?乙柱子?+?“上?”?+?#換行符

步驟?=?步驟?+?1

.子程序?_計(jì)算圖形按鈕_被單擊

.局部變量?盤(pán)子總數(shù)，整數(shù)型

.局部變量?現(xiàn)在柱子，文本型

.局部變量?中間柱子，文本型

.局部變量?目標(biāo)柱子，文本型

'?把盤(pán)子編輯框.內(nèi)容傳給現(xiàn)在柱子

現(xiàn)在柱子?=?盤(pán)子編輯框.內(nèi)容

'?把中間編輯框.內(nèi)容傳給中間柱子

中間柱子?=?中間編輯框.內(nèi)容

'?把目標(biāo)編輯框.內(nèi)容傳給目標(biāo)柱子

目標(biāo)柱子?=?目標(biāo)編輯框.內(nèi)容

.如果真?（到數(shù)值?（現(xiàn)在柱子）?≤?0?或?到數(shù)值?（中間柱子）?≤?0?或?到數(shù)值?（目標(biāo)柱子）?≤?0?或?到數(shù)值?（個(gè)數(shù)編輯框.內(nèi)容）?≤?0?或?到數(shù)值?（個(gè)數(shù)編輯框.內(nèi)容）?>?10）

信息框?（“柱子或圓盤(pán)數(shù)量只能是大于0小于10的數(shù)字！”，#錯(cuò)誤圖標(biāo)，“出現(xiàn)錯(cuò)誤了：”）

返回? -

.如果真結(jié)束

盤(pán)子總數(shù)?=?到數(shù)值?（個(gè)數(shù)編輯框.內(nèi)容）

結(jié)果編輯框.內(nèi)容?=?“”

路徑?=?“”

'?首次調(diào)用漢諾塔盤(pán)子運(yùn)動(dòng)?（）程序

漢諾塔盤(pán)子運(yùn)動(dòng)?（盤(pán)子總數(shù)，現(xiàn)在柱子，中間柱子，目標(biāo)柱子）

結(jié)果編輯框.內(nèi)容?=?路徑

步驟?=?1