使用 Go 语言实现汉诺塔(Hanota)算法

我最近重温了一下《猩球崛起》这部电影。在电影中,凯撒就玩了河内塔游戏。你还有印象吗?其实独自一人玩一些游戏是好难的😭(译者不知作者为何这么说🤔,难道是无聊嘛?🤓),今天我们就用 Golang 来实现一下汉诺塔游戏。

游戏起源

相传最早发明这个问题的人是法国数学家爱德华·卢卡斯(Edouard Lucas)。

在世界中心的贝拿勒斯(印度北部)圣殿中,有三根宝石针插入了一个黄铜盘中。在印度教主神梵天(Brahma)创世时,将其中一根针上从下到上装配了 64 个金片,这也就是所谓的汉诺塔。

无论白天黑夜,总会有一位僧人按照接下来的规则移动这些金片:一次只移动一片,无论在哪根针上,小片必须在大片之上。

比丘们预言,当所有的金片从梵天所的装配宝石针上移到另一个宝石针上时,世界将在雷霆中毁灭,梵天塔、寺庙和众生也将灭亡。

这个传说有很多变种,虽不知道是谁创作的,但其留下的数学问题非常经典。

遗留下来的数学知识:金片数量与移动步数的关系是二的n次方-1:

1 个金片需要的步数是 2 的 1 次方减 1
2 个金片需要的步数是 2 的 2 次方减 1
3 个金片需要的步数是 2 的 3 次方减 1

n 个金片需要的步数是 2 的 n 次方减 1

如果传说属实,修士们需要  步移动才能完成这个任务;假设他们每秒移动一片黄金,则需要 5849 亿年才能完成。整个宇宙只有 137 亿年,宇宙毁灭还为时尚早。。。

游戏规则分析

假设这个游戏中有 3 个柱子,即 A、B 和 C。需要移动的是珠子,其中一个柱子上已经有 N 个有序的珠子,最大的在底部,珠子按顺序越来越小。另外 2 个是空柱子。

基本条件:

  • 一次只能移动一颗珠子
  • 小珠子一定要在大珠子上面

初始状态如下图所示:

使用 Go 语言实现汉诺塔(Hanota)算法

最终目标是将柱子上的所有珠子移到另一根柱子上。如下所示:

使用 Go 语言实现汉诺塔(Hanota)算法

游戏实现思路

  1. 放空你的大脑,先想想最简单粗暴的解决逻辑:将珠子视为一个整体。

  2. 若要满足大珠子在下面的基本条件,一定要把 A 上最大的珠子清空,再把这个最大的珠子放在 C 柱上。(假设珠子数量为 N)

  3. 如果要将其移动到 C 柱,首先要实现的必须是把 N-1 个珠子全部移到 B 柱上,这样才能把第 N 个珠子(也就是最大的珠子)移到 C 柱上。

  4. 把 N-1 珠子移到 B 柱子上,因为大珠的在下,小珠在上,所以这 N-1 个珠子在 B 柱上是有序的。

  5. 最后,将这 N-1 个珠子从 B 柱移动到 C 柱,完成最终目标。

实现第一步:将 A 上的 N-1 个珠子移动到 B。

为什么先把 N-1 移到 B 上?因为你的最终实现是将所有的珠子从 A 移到 C,并且顺序不能改变。只能大的在下,小的在上。

那么必须先将最大的珠子移到 C,否则条件不成立。要将最大的珠子从 A 移到 C,必须腾出 A 上最大的珠子,也就是必须把最大珠子上面的所有珠子全部移走。

而你只有 3 根柱子,C 上不能有其他珠子,否则不符合条件,因此这 N-1 颗珠子只能放在 B 上,并且它们会依旧井然有序。

使用 Go 语言实现汉诺塔(Hanota)算法

第二步将 A 上的第 N 个珠子(最大的珠子)移动到 C。

这很简单,只需一步将最大的珠子从 A 移动到 C。如下所示。

使用 Go 语言实现汉诺塔(Hanota)算法

第三步将 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

如下所示。

使用 Go 语言实现汉诺塔(Hanota)算法

首先找到剩余的珠子中最大的一个(在该演示中是 4 号)。然后移动它。

使用 Go 语言实现汉诺塔(Hanota)算法

循环重复以上步骤,直到只剩下最后一颗(最小的)珠子,直接移动到 C,游戏结束。

辅助柱

什么是辅助柱?假设您现在拥有要在 A 上被移动的所有珠子,同时目标是将其移动到 C,那么 B 是这 N-1 个珠子的辅助柱。因为他们只能暂时留在这里,否则不符合游戏规则。

这里需要先找到辅助支柱,先别想怎么实现,先理清逻辑。

要实现从 A 到 B 的移动,那么 C 就是辅助柱。
要实现从 A 到 C 的移动,那么 B 是辅助支柱。
要实现从 B 到 C 的移动,那么 A 就是辅助柱。

Golang 实现

从上面的分析可以看出,这其实是一个循环重复的操作,和递归很像,并且都可以用递归来实现。

要使用递归,有两个必要条件

  1. 求递归公式
  2. 找到退出条件

在这个游戏中,退出条件是在只有一颗珠子的情况下直接移动到C柱。

那么递归公式是什么呢?根据以上逻辑分析,可以分解为三个步骤:

  • 第一步,将 {这 N-1 个珠子} 从A移动到B
  • 第二步,将 {第 N 个珠子} 从A移动到C
  • 第三步,将 {其余 N-1 个珠子} 从 B 移到 C

以下是用 Golang 实现的伪代码

使用 Go 语言实现汉诺塔(Hanota)算法

感谢您阅读本文,如果您认为文章写得好,请关注我。

如果您发现本文有任何错误,请留言讨论。

祝您拥有美好的一天!

链接:https://betterprogramming.pub/implementing-the-hanota-algorithm-using-golang-7c3b9e142448
(版权归原作者所有,侵删)

相关新闻

历经多年发展,已成为国内好评如潮的Linux云计算运维、SRE、Devops、网络安全、容器云、Go、Python开发专业人才培训机构!