我最近重溫了一下《猩球崛起》這部電影。在電影中，凱撒就玩了河內(nèi)塔游戲。你還有印象嗎？其實獨自一人玩一些游戲是好難的??（譯者不知作者為何這么說??，難道是無聊嘛？??），今天我們就用 Golang 來實現(xiàn)一下漢諾塔游戲。

游戲起源

相傳最早發(fā)明這個問題的人是法國數(shù)學家愛德華·盧卡斯（Edouard Lucas）。

在世界中心的貝拿勒斯（印度北部）圣殿中，有三根寶石針插入了一個黃銅盤中。在印度教主神梵天（Brahma）創(chuàng)世時，將其中一根針上從下到上裝配了 64 個金片，這也就是所謂的漢諾塔。

無論白天黑夜，總會有一位僧人按照接下來的規(guī)則移動這些金片：一次只移動一片，無論在哪根針上，小片必須在大片之上。

比丘們預言，當所有的金片從梵天所的裝配寶石針上移到另一個寶石針上時，世界將在雷霆中毀滅，梵天塔、寺廟和眾生也將滅亡。

這個傳說有很多變種，雖不知道是誰創(chuàng)作的，但其留下的數(shù)學問題非常經(jīng)典。

遺留下來的數(shù)學知識：金片數(shù)量與移動步數(shù)的關系是二的n次方-1:

1 個金片需要的步數(shù)是 2 的 1 次方減 1
2 個金片需要的步數(shù)是 2 的 2 次方減 1
3 個金片需要的步數(shù)是 2 的 3 次方減 1
…
n 個金片需要的步數(shù)是 2 的 n 次方減 1

如果傳說屬實，修士們需要??步移動才能完成這個任務；假設他們每秒移動一片黃金，則需要 5849 億年才能完成。整個宇宙只有 137 億年，宇宙毀滅還為時尚早。。。

游戲規(guī)則分析

假設這個游戲中有 3 個柱子，即 A、B 和 C。需要移動的是珠子，其中一個柱子上已經(jīng)有 N 個有序的珠子，最大的在底部，珠子按順序越來越小。另外 2 個是空柱子。

基本條件：

• 一次只能移動一顆珠子
• 小珠子一定要在大珠子上面

初始狀態(tài)如下圖所示：

最終目標是將柱子上的所有珠子移到另一根柱子上。如下所示：

游戲?qū)崿F(xiàn)思路

1. 放空你的大腦，先想想最簡單粗暴的解決邏輯：將珠子視為一個整體。
2. 若要滿足大珠子在下面的基本條件，一定要把 A 上最大的珠子清空，再把這個最大的珠子放在 C 柱上。（假設珠子數(shù)量為 N）
3. 如果要將其移動到 C 柱，首先要實現(xiàn)的必須是把 N-1 個珠子全部移到 B 柱上，這樣才能把第 N 個珠子（也就是最大的珠子）移到 C 柱上。
4. 把 N-1 珠子移到 B 柱子上，因為大珠的在下，小珠在上，所以這 N-1 個珠子在 B 柱上是有序的。
5. 最后，將這 N-1 個珠子從 B 柱移動到 C 柱，完成最終目標。

實現(xiàn)第一步：將 A 上的 N-1 個珠子移動到 B。

為什么先把 N-1 移到 B 上？因為你的最終實現(xiàn)是將所有的珠子從 A 移到 C，并且順序不能改變。只能大的在下，小的在上。

那么必須先將最大的珠子移到 C，否則條件不成立。要將最大的珠子從 A 移到 C，必須騰出 A 上最大的珠子，也就是必須把最大珠子上面的所有珠子全部移走。

而你只有 3 根柱子，C 上不能有其他珠子，否則不符合條件，因此這 N-1 顆珠子只能放在 B 上，并且它們會依舊井然有序。

第二步將 A 上的第 N 個珠子（最大的珠子）移動到 C。

這很簡單，只需一步將最大的珠子從 A 移動到 C。如下所示。

第三步將 B 上的 N-1 個珠子移動到 C。

提示：要實現(xiàn)將 N-1 個珠子移動到 C，是不是先找到其中最大的珠子，然后先移動最大的珠子？所以這里的話實際上變成了重復第一步和第二步，從這 N-1 個珠子中找出最大的一個，移到 C，然后重復下去。

第三步其實相當于改變了要求。假設 K = N - 1。

這時 B 柱有 K 個珠子，A 柱是空的，C 柱有最大的珠子，所以 B 柱有 K 個珠子就相當于它是空的。

第一步將 B 上的 K-1 個珠子移動到 A。
第二步將 B 上的第 K 個珠子移動到 C。
第三步將 A 上的 K-1 個珠子移動到 C

如下所示。

首先找到剩余的珠子中最大的一個（在該演示中是 4 號）。然后移動它。

循環(huán)重復以上步驟，直到只剩下最后一顆（最小的）珠子，直接移動到 C，游戲結束。

輔助柱

什么是輔助柱？假設您現(xiàn)在擁有要在 A 上被移動的所有珠子，同時目標是將其移動到 C，那么 B 是這 N-1 個珠子的輔助柱。因為他們只能暫時留在這里，否則不符合游戲規(guī)則。

這里需要先找到輔助支柱，先別想怎么實現(xiàn)，先理清邏輯。

要實現(xiàn)從 A 到 B 的移動，那么 C 就是輔助柱。
要實現(xiàn)從 A 到 C 的移動，那么 B 是輔助支柱。
要實現(xiàn)從 B 到 C 的移動，那么 A 就是輔助柱。

Golang 實現(xiàn)

從上面的分析可以看出，這其實是一個循環(huán)重復的操作，和遞歸很像，并且都可以用遞歸來實現(xiàn)。

要使用遞歸，有兩個必要條件

1. 求遞歸公式
2. 找到退出條件

在這個游戲中，退出條件是在只有一顆珠子的情況下直接移動到C柱。

那么遞歸公式是什么呢？根據(jù)以上邏輯分析，可以分解為三個步驟：

• 第一步，將 {這 N-1 個珠子} 從A移動到B
• 第二步，將 {第 N 個珠子} 從A移動到C
• 第三步，將 {其余 N-1 個珠子} 從 B 移到 C

以下是用 Golang 實現(xiàn)的偽代碼

鏈接：https://betterprogramming.pub/implementing-the-hanota-algorithm-using-golang-7c3b9e142448

（版權歸原作者所有，侵刪）