使用 Go 语言实现汉诺塔（Hanota）算法
我最近重温了一下《猩球崛起》这部电影。在电影中，凯撒就玩了河内塔游戏。你还有印象吗？其实独自一人玩一些游戏是好难的😭（译者不知作者为何这么说🤔，难道是无聊嘛？🤓），今天我们就用 Golang 来实现一下汉诺塔游戏。
游戏起源
相传最早发明这个问题的人是法国数学家爱德华·卢卡斯（Edouard Lucas）。
在世界中心的贝拿勒斯（印度北部）圣殿中，有三根宝石针插入了一个黄铜盘中。在印度教主神梵天（Brahma）创世时，将其中一根针上从下到上装配了 64 个金片，这也就是所谓的汉诺塔。
无论白天黑夜，总会有一位僧人按照接下来的规则移动这些金片：一次只移动一片，无论在哪根针上，小片必须在大片之上。
比丘们预言，当所有的金片从梵天所的装配宝石针上移到另一个宝石针上时，世界将在雷霆中毁灭，梵天塔、寺庙和众生也将灭亡。
这个传说有很多变种，虽不知道是谁创作的，但其留下的数学问题非常经典。
遗留下来的数学知识：金片数量与移动步数的关系是 ：
1 个金片需要的步数是 2 的 1 次方减 1
2 个金片需要的步数是 2 的 2 次方减 1
3 个金片需要的步数是 2 的 3 次方减 1
…
n 个金片需要的步数是 2 的 n 次方减 1
如果传说属实，修士们需要 步移动才能完成这个任务；假设他们每秒移动一片黄金，则需要 5849 亿年才能完成。整个宇宙只有 137 亿年，宇宙毁灭还为时尚早。。。
游戏规则分析
假设这个游戏中有 3 个柱子，即 A、B 和 C。需要移动的是珠子，其中一个柱子上已经有 N 个有序的珠子，最大的在底部，珠子按顺序越来越小。另外 2 个是空柱子。
基本条件：
-
一次只能移动一颗珠子 -
小珠子一定要在大珠子上面
初始状态如下图所示：
最终目标是将柱子上的所有珠子移到另一根柱子上。如下所示：
游戏实现思路
-
放空你的大脑，先想想最简单粗暴的解决逻辑：将珠子视为一个整体。
-
若要满足大珠子在下面的基本条件，一定要把 A 上最大的珠子清空，再把这个最大的珠子放在 C 柱上。（假设珠子数量为 N）
-
如果要将其移动到 C 柱，首先要实现的必须是把 N-1 个珠子全部移到 B 柱上，这样才能把第 N 个珠子（也就是最大的珠子）移到 C 柱上。
-
把 N-1 珠子移到 B 柱子上，因为大珠的在下，小珠在上，所以这 N-1 个珠子在 B 柱上是有序的。
-
最后，将这 N-1 个珠子从 B 柱移动到 C 柱，完成最终目标。
实现第一步：将 A 上的 N-1 个珠子移动到 B。
为什么先把 N-1 移到 B 上？因为你的最终实现是将所有的珠子从 A 移到 C，并且顺序不能改变。只能大的在下，小的在上。
那么必须先将最大的珠子移到 C，否则条件不成立。要将最大的珠子从 A 移到 C，必须腾出 A 上最大的珠子，也就是必须把最大珠子上面的所有珠子全部移走。
而你只有 3 根柱子，C 上不能有其他珠子，否则不符合条件，因此这 N-1 颗珠子只能放在 B 上，并且它们会依旧井然有序。
第二步将 A 上的第 N 个珠子（最大的珠子）移动到 C。
这很简单，只需一步将最大的珠子从 A 移动到 C。如下所示。
第三步将 B 上的 N-1 个珠子移动到 C。
提示：要实现将 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 号）。然后移动它。
循环重复以上步骤，直到只剩下最后一颗（最小的）珠子，直接移动到 C，游戏结束。
辅助柱
什么是辅助柱？假设您现在拥有要在 A 上被移动的所有珠子，同时目标是将其移动到 C，那么 B 是这 N-1 个珠子的辅助柱。因为他们只能暂时留在这里，否则不符合游戏规则。
这里需要先找到辅助支柱，先别想怎么实现，先理清逻辑。
要实现从 A 到 B 的移动，那么 C 就是辅助柱。
要实现从 A 到 C 的移动，那么 B 是辅助支柱。
要实现从 B 到 C 的移动，那么 A 就是辅助柱。
Golang 实现
从上面的分析可以看出，这其实是一个循环重复的操作，和递归很像，并且都可以用递归来实现。
要使用递归，有两个必要条件
-
求递归公式 -
找到退出条件
在这个游戏中，退出条件是在只有一颗珠子的情况下直接移动到C柱。
那么递归公式是什么呢？根据以上逻辑分析，可以分解为三个步骤：
-
第一步，将 {这 N-1 个珠子} 从A移动到B -
第二步，将 {第 N 个珠子} 从A移动到C -
第三步，将 {其余 N-1 个珠子} 从 B 移到 C
以下是用 Golang 实现的伪代码
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)
}
感谢您阅读本文，如果您认为文章写得好，请关注我。
如果您发现本文有任何错误，请留言讨论。
祝您拥有美好的一天！