描述一下问题，假设有 A，B，C 三个柱子。A 柱子上有一定数目从高到低是小到大顺序的盘子叠起来，每次可以移动一个柱子上的 1 个盘子。并且任何时候小盘子永远在大盘子上。现在的问题是如何把 A 的 N 个盘子移动到 C。在线游戏

1.N = 1 ，A 移动到 C 就好。

2.N = 2，先移动第一个到 B，再把第二个移动到 C，再把 B 的移动到 C 就好。

3.N = 3 …

也许刚拿到的时候会不断尝试。仔细分析 2 的最后一步，会发现这个时候 A 没有盘子，B 有一个小的，C 有一个大的。如果把这个情况引入到 3，就是 A 没有盘子，C 有一个最大的，B 有两个较小的，把 B 的两个移动到 C 就行了。如何把 B 的两个移动到 C 参看 2 的解答即可。同样，如何把两个较小的盘子移动到 B 呢，也可以参看 2 的解答。

那么当 N 更大的时候呢？

这个时候肯定是需要寻找规律的。从 N = 3 的情况可以看出似乎 2 的解法可以用在了 3 上，并且可以发现 N 个盘子在移动到 C 之前一定是要让 N - 1 个盘子落在 B 并且第 1 大的落在 C，并且，

让 N - 1 落在 B 就一定要让 N - 2 落在 C，并且，

让 N - 2 落在 C 就一定要让 N - 3 落在 B，并且，

让 N - 3 落在 B 就一定要让 N - 4 落在 C，并且，

…

最后的结论就是探讨第 N 大的盘子落在 B 还是 C 上。如果是从数学的角度看，只要通过奇偶来判断是往 B 还是往 C 即可。那么如何用计算机来解答呢？

假设函数签名是 hanoi(n, a, b, c)。前三个输入以及输出分别为

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
> hanoi(1, "A", "B", "C")
A —-> C

> hanoi(2, "A", "B", "C")
A —-> B
A —-> C
B —-> C

> hanoi(3, "A", "B", "C")
A —-> C
A —-> B
C —-> B
A —-> C
B —-> A
B —-> C
A —-> C

从最简单的情况可以写出

1
2
3
4
5
6
7
def hanoi(n, a, b, c)
  if n == 1
    puts "#{a} --> #{c}"
  else
  # 所以当 n > 1 的时候呢？
  end
end

回顾上面的推导不难发现实际上如果要把 N 个盘子从 A 移动到 C。需要做的就是三步

  1. 移动 A 的 N - 1 个到 B
  2. 移动第 A 的 N 个 到 C
  3. 移动 B 的 N - 1 个到 C

这其中 A，B，C 柱子为了便于理解可以认为是起始柱，辅助柱和目标柱。这也函数 hanoi(n, a, b, c) 中后三个参数的意思就是。也就是说，再深入理解为

  1. 移动起始柱的 N - 1 个到辅助柱
  2. 移动起始柱的 N 个 到目标柱
  3. 移动辅助柱的 N - 1 个到目标柱

完善一下代码就是

1
2
3
4
5
6
7
8
9
def hanoi(n, a, b, c)
  if n == 1
    puts "#{a} --> #{c}"
  else
    hanoi(n - 1, a, c, b)
    hanoi(1, a, b, c)
    hanoi(n - 1, b, a, c)
  end
end