游戲起源

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

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

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

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

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

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

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

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

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

  …

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

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

游戲規(guī)則分析

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

基本條件：

• 一次只能移動(dòng)一顆珠子
• 小珠子一定要在大珠子上面

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

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

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

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

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

4. 把 N-1 珠子移到 B 柱子上，因?yàn)榇笾榈脑谙拢≈樵谏希赃@ N-1 個(gè)珠子在 B 柱上是有序的。
5. 最后，將這 N-1 個(gè)珠子從 B 柱移動(dòng)到 C 柱，完成最終目標(biāo)。

實(shí)現(xiàn)第一步：將 A 上的 N-1 個(gè)珠子移動(dòng)到 B。

為什么先把 N-1 移到 B 上？因?yàn)槟愕淖罱K實(shí)現(xiàn)是將所有的珠子從 A 移到 C，并且順序不能改變。只能大的在下，小的在上。

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

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

第二步將 A 上的第 N 個(gè)珠子（最大的珠子）移動(dòng)到 C。

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

第三步將 B 上的 N-1 個(gè)珠子移動(dòng)到 C。

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

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

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

第一步將 B 上的 K-1 個(gè)珠子移動(dòng)到 A。

第二步將 B 上的第 K 個(gè)珠子移動(dòng)到 C。

第三步將 A 上的 K-1 個(gè)珠子移動(dòng)到 C

如下所示。

首先找到剩余的珠子中最大的一個(gè)（在該演示中是 4 號(hào)）。然后移動(dòng)它。

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

輔助柱

什么是輔助柱？假設(shè)您現(xiàn)在擁有要在 A 上被移動(dòng)的所有珠子，同時(shí)目標(biāo)是將其移動(dòng)到 C，那么 B 是這 N-1 個(gè)珠子的輔助柱。因?yàn)樗麄冎荒軙簳r(shí)留在這里，否則不符合游戲規(guī)則。

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

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

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

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

Golang 實(shí)現(xiàn)

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

要使用遞歸，有兩個(gè)必要條件

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

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

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

•  第一步，將 {這 N-1 個(gè)珠子} 從A移動(dòng)到B
• 第二步，將 {第 N 個(gè)珠子} 從A移動(dòng)到C
• 第三步，將 {其余 N-1 個(gè)珠子} 從 B 移到 C

以下是用 Golang 實(shí)現(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)注我。