背景
最近在辅导小孩们学习编程，在介绍函数递归时，最典型的就是汉诺塔问题了。
我在这里总结一下，以方便大家的学习。
汉诺塔问题源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着 64 片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。
技术分析
如果我们要思考每一步怎么移可能会非常复杂，但是可以将问题简化。
我们可以先假设除 a 柱最下面的盘子之外，已经成功地将 a 柱上面的 63个盘子移到了 b 柱，这时我们只要再将最下面的盘子由 a 柱移动到 c 柱即可。
当我们将最大的盘子由 a 柱移到 c 柱后，b 柱上便是余下的 63 个盘子，a 柱为空。因此现在的目标就变成了将这 63 个盘子由 b 柱移到 c 柱。这个问题和原来的问题完全一样，只是由 a 柱换为了 b 柱，规模由 64 变为了 63。因此可以采用相同的方法，先将上面的 62 个盘子由 b 柱移到 a 柱，再将最下面的盘子移到 c 柱。
以此内推，再以 b 柱为缓冲，将 a 柱上面的 62 个圆盘最上面的 61 个圆盘移动到 b 柱，并将最后一块圆盘移到 c 柱。
我们已经发现规律，我们每次都是以 a 或 b 中一根柱子为缓冲，然后先将除了最下面的圆盘之外的其它圆盘移动到辅助柱子上，再将最底下的圆盘移到 c 柱子上，不断重复此过程。
这个反复移动圆盘的过程就是递归，例如我们每次想解决 n 个圆盘的移动问题，就要先解决（n-1）个盘子进行同样操作的问题。
于是可以编写一个函数，move(n, a, b, c)。可以这样理解：move(盘子数量, 起点, 缓冲, 终点)。
<u>1. a 上只有一个盘子的情况，直接搬到 c，代码如下</u>:
if n == 1:
print(a, '-->', c)
<u>2. a 上不止有一个盘子的情况</u>:
首先，需要把 n-1 个盘子搬到 b 柱子缓冲。打印出的效果是：a --> b。
move(n - 1, a, c, b)
再把最大的盘子搬到 c 柱子，也是最大尺寸的一个。打印出：a-->c。
move(1, a, b, c)
最后，把剩下 b 柱的 n-1 个盘子搬到 c 上，此时缓冲变成了起点，起点变成了缓冲。
move(n - 1, b, a, c)
代码实现
<b>Python 实现汉诺塔问题</b>
i = 0
def move(n, a, b, c):
global i
if (n == 1):
i += 1
print('移动第 {0} 次 {1} --> {2}'.format(i, a, c))
return
move(n - 1, a, c, b)
move(1, a, b, c)
move(n - 1, b, a, c)
move(3, "a", "b", "c")
# 移动第 1 次 a --> c
# 移动第 2 次 a --> b
# 移动第 3 次 c --> b
# 移动第 4 次 a --> c
# 移动第 5 次 b --> a
# 移动第 6 次 b --> c
# 移动第 7 次 a --> c
<b>C# 实现汉诺塔问题</b>
class Program
{
private static int i = 0;
static void Move(int n, string a, string b, string c)
{
if (n == 1)
{
Console.WriteLine("移动第 {0} 次 {1}-->{2}", ++i, a, c);
return;
}
Move(n - 1, a, c, b);
Move(1, a, b, c);
Move(n - 1, b, a, c);
}
static void Main(string[] args)
{
Move(3, "a", "b", "c");
}
}
总结
我发现，把自己积累的知识教给小孩们还是很有意思的。等我们的小会议室装修好，我会开展更多的分享活动。欢迎大家来参加呀。今天就到这里吧！See You！
相关图文：
