這個遊戲大家想必都不陌生：

當然，遊戲是有規則的，否則把所有的圈圈們連根拔起，一下扔過去就結束了。。。

規則一：每次操作隻能移動一個圈圈，把它從一個柱子移到另一個柱子上；

規則二：大圈圈不能架在小圈圈的上面。

今天咱們就來說說這個遊戲。

遊戲的名字，最通俗的叫法是漢諾塔，英文名Tower of Hanoi。

Hanoi在英文裡是河内（越南首都）的意思，所以，其實還是叫河内塔更準确些。

神話故事

這是一個古印度的遊戲，源自古印度神話：

學過計算機編程基礎的小盆友們都知道，解決河内塔問題大體有兩種思路：疊代和非疊代。

疊代的解法

疊代的方法非常簡單，也很好玩。

記得那個經典的笑話嗎：

把大象放進冰箱要幾步？

分三步：

1、把冰箱門打開；

2、把大象塞進去；

3、把冰箱門關上。

嗯，跟這個笑話類似：

你不是想要找一個辦法把8個盤子都移到C棒嗎？

分三步：

1、假設有了一個辦法，把前7個盤子一起都移到B棒。

2、把最大的盤子移到C棒。

3、再用想象中的辦法，把B棒上那7個盤子都移到C棒那個最大的盤子上。

問題就解決了。

圖中深黃色的盤子可視為任意數量：對任何N個盤子的情況，都可以簡化為将N-1個盤子先移到中轉棒，将最大的盤子移到目标棒，再将N-1個盤子移到目标棒

那麼如何完成第一步和第三步裡，把7個盤子整體移動呢？

繼續疊代：先把前6個盤子都移到C棒，再把最大的那個移到B棒，再把C棒上那6個盤子移回B棒上來。

每一次疊代，都使得需要移動的盤子數減少了1；一直疊代下去，直到最原始的情況：把一個盤子移到另一根棒子上。

這個原始情況解決了，那麼依次倒回去，所有的問題都解決了。

仍然用大象和冰箱的例子作比，那就是：

中間的第二步，如何把大象塞進去呢？

先把大象頭塞進去；

再把大象身體塞進去；

再把大象腿和尾巴塞進去。

大象的頭如何塞進去呢？

先把鼻子塞進去；

再把臉塞進去；

再把後腦勺一股腦塞進去。

大象鼻子怎麼塞進去呢？

先把第一段鼻子塞進去；

再把第二段鼻子塞進去；

……

疊代法，就是這麼簡（bao）單（li）而且易（liu）行（mang）！

正因為如此，這個方法也成為大學裡教授計算機編程思想的必修内容之一：幾乎所有的計算機專業的大學生都遇到過這個問題和解法。

程序是解決了，但這其實并不是一個正常人類能看懂和操作的方法；你能寫出這樣的程序讓計算機給出答案，可是當你實際遇到8個盤子疊起來時，還是一樣抓瞎沒轍，并沒有實際的指導意義。

有沒有直觀的、操作性強的統一解法呢？

當然有。

這就是所謂非疊代的解法。

以下慎入，因為當你看完後，你會發現此遊戲的所有樂趣都被剝奪殆盡，隻剩下了極其簡單和無聊的解謎過程

非疊代的解法

同樣以8個盤子為例：

A棒上的8個盤子要全部移到目标C棒，

所以：

最大的8号盤的目标是C棒。

次大的7号盤的目标就應該是B棒。

以此類推，6号盤的目标又是C棒。

5号盤的目标是B棒。

4号盤的目标是C棒。

3号盤的目标是B棒。

2号盤的目标是C棒。

最小的1号盤，目标是B棒。

總而言之：

1、3、5、7号盤的目标是中轉棒B；

2、4、6、8号盤的目标是目标棒C。

這8個目标把整個問題分成了8步，而且和剛剛疊代法那不負責任的3步比起來，這8步的指導意義是很強的：

第一個目标，就是将最小的1号盤移到中轉棒B棒上。——這個目标當然一步就能實現：

然後将2号盤移到目标棒C棒上。——也是一步就可以實現：

下一個目标，就是把3号盤移到B棒。這時由于1号盤占上了B棒的坑位，所以要先把它挪到C棒，騰出B棒的位置，再把3号盤移過來：

下面類似：1号移回A，2号移上B，1号移上B，4号移到C：

後面的思路都一樣，不再贅述：總之，8個目标是分别讓1、2、3、4、5、6、7、8号盤依次就位：

當8号盤在C棒就位以後，下面就是要讓7号去C棒。

要實現這一點，6号要去A，5号去C，4号去A，3号去C，2号去A，1号去C。

也就是說，接下來的一步是讓1号盤移到C棒。

再重複一下問題的關鍵：對于8個盤的情況，其實盤子們分别要去的目标是唯一的——

1、3、5、7号盤去中轉棒B，

2、4、6、8号盤去目标棒C。

不僅如此！

在操作中的每一步，你想要移動的目标盤和你實際移動的盤之間，保持間隔始終為偶數，就一定沒問題。

舉例來說，在某一個中間狀态，12345号盤一起堆在C棒上，你想把它們一起弄到B棒；這時1、3、5号盤的目标就是B棒，2、4号盤的目标是A棒。所以此時要做的第一步就是把1号盤移到B棒。

嗯，你已經獲得了這個遊戲的精髓。

這麼一來，這個遊戲還有什麼樂趣可言呢？？

沒有了。

即使是64個盤子，我們也能一下得到所有的中間狀态：把所有盤子從小到大編号，所有的奇數号盤子（1，3，5，7，...）一律去中轉棒，所有的偶數号盤子（2，4，6，8，...）一律去目标棒；當第64個盤子就位以後，再将所有的奇數号盤子的目标定為目标棒，把剩下的偶數号盤子的目标定為中轉棒，直至第63個盤子就位；然後再繼續重複這一過程，直至所有盤子就位。

好枯燥，好簡單，好無聊！

複雜度

那麼我們來看看這個話題裡最後一個有點意思的内容：

操作開銷和時間開銷。

要實現64個盤子移位的終極目标，要做多少次有效的移動？

——所謂有效移動是指，假設這些婆羅門和後代們把其中的算法和過程都研究得很清楚，奇偶數的盤子都沒有數錯，老眼昏花、頭昏腦脹，移的過程亂七八糟等等，所有這些意外統統不出現：

那麼一共至少要多少步呢？

很好算。

1個盤子就位需要1步，

2個盤子都就位需要3步，

從3個盤子開始，就需要先用3步使前2個盤子都移到中轉棒，再來1步使第三個盤子就位，再來3步使前2個盤子都移到目标棒，一共就是3 1 3=7步。

4個盤子全部就位，需要7 1 7=15步。

按照歸納法進行簡單的計算，容易知道：

n個盤子全部就位，需要總步數為：2的n次方-1。

也就是說，對于梵天神64個盤子的完整版，婆羅門和後人們一共隻需要移動2的64次方-1步，就可以就位啦！

這個過程其實很快的，隻要他們能做到并且維持每秒移動1個盤子的速度，那麼一共隻要2的64次方-1秒，合5800億年，就能把64個盤子正确就位，使得宇宙在閃電中毀滅！

不過，據科學家分析，宇宙的壽命也就在150億年左右……

好吧梵天還是你赢了！！~