游戲起源

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

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

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

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

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

遺留下來的數(shù)學(xué)知識：金片數(shù)量與移動步數(shù)的關(guān)系是 2?–1：

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

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

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

  …

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

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

游戲規(guī)則分析

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

基本條件：

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

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

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

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

1. 放空你的大腦，先想想最簡單粗暴的解決邏輯：將珠子視為一個整體。
2. 若要滿足大珠子在下面的基本條件，一定要把 A 上最大的珠子清空，再把這個最大的珠子放在 C 柱上。（假設(shè)珠子數(shù)量為 N）
3. 如果要將其移動到 C 柱，首先要實現(xiàn)的必須是把 N-1 個珠子全部移到 B 柱上，

     這樣才能把第 N 個珠子（也就是最大的珠子）移到 C 柱上。

4. 把 N-1 珠子移到 B 柱子上，因為大珠的在下，小珠在上，所以這 N-1 個珠子在 B 柱上是有序的。
5. 最后，將這 N-1 個珠子從 B 柱移動到 C 柱，完成最終目標(biāo)。

實現(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，是不是先找到其中最大的珠子，然后先移動最大的珠子？所以這里的話實際上變成了重復(fù)第一步和第二步，從這 N-1 個珠子中找出最大的一個，移到 C，然后重復(fù)下去。

第三步其實相當(dāng)于改變了要求。假設(shè) K = N - 1。

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

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

第二步將 B 上的第 K 個珠子移動到 C。

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

如下所示。

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

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

輔助柱

什么是輔助柱？假設(shè)您現(xiàn)在擁有要在 A 上被移動的所有珠子，同時目標(biāo)是將其移動到 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)重復(fù)的操作，和遞歸很像，并且都可以用遞歸來實現(xiàn)。

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

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

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

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

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

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

package main
import "fmt"
// Record the number of game steps
var count int = 0
func main() {
    beadNum := 5 // This is the initial number of beads
    fmt.Printf("This is a Hannukah game with %d beads \n\r", beadNum)
    hanoi(beadNum, "A", "B", "C")
    fmt.Printf("Game over: %d steps spent in total \n\r", count)
}
// Hannukah game
func hanoi(beadNum int, pillarA string, pillarB string, pillarC string) {
    if beadNum == 1 {
        // If there is only one bead, move from A to C, game over
        move(beadNum, pillarA, pillarC)
    } else {
        // Step 2: move all the plates above N (that is, N-1 judgments) from A to B. At this time, C is the transfer station
        hanoi(beadNum-1, pillarA, pillarC, pillarB)
        // Step 2: move the Nth plate from A to C
        move(beadNum, pillarA, pillarC)
        // Step 3: move the remaining n-1 disks on B from B to C. At this time, A is the transfer station
        hanoi(beadNum-1, pillarB, pillarA, pillarC)
    }
}
// Move the beads
func move(beadNum int, pillarFrom string, pillarTo string) {
    count += 1
    fmt.Printf("Step %d: bead of %d from %s move to %s \n\r", count, beadNum, pillarFrom, pillarTo)
}

感謝您閱讀本文，如果您認(rèn)為文章寫得好，請關(guān)注我。