经典回顾之汉诺塔问题（附 Java 实现案例）

有没有玩过这个游戏，游戏规则：

将 A 柱中的所有大小不一的盘子全部按照从小到大的顺序挪到 C 柱上，在移动的过程中，盘子必须始终保持从小到大的顺序放置（大盘在下小盘在上），每次只能移动一个盘子，并且盘子不能私藏到柱子之外哟！

有没有看懂游戏规则呢？来看一个实际的例子演示吧！

只有一个盘子

傻子也知道，直接移动到C座就OK了。

有两个盘子 [1 2]

把1移动到B

把2移动到C

把1移动到C

有三个盘子 [1 2 3]

把1移动到C

把2移动到B

把1移动到B

把3移动到C

把1移动到A

把2移动到C

把1移动到C

看下图：

你发现什么规律了吗？虽说好像感觉有一定规律，但好像说不出来个所以然。

规律

对于上面的例子，我们可以总结出两点：

最后一步肯定是把1移动到C
如果盘子数大于1（1就直接移了），肯定要把最大的盘子上面的全部盘子放到B上，然后将最大的放到C上

由上面的两点，我们来探究一下递归关系。

假设有n个盘子，分别标记为 [1 2 3... n] 大数表示大盘子，已经在A座上放好。

初始状态

A：有n个盘子  
B：空  
C：空

我们现在有一个方法：hanoi(int n, String a, String b, String c) ，作用就是将n个盘子从a座借助b座移动到c座。

我们先不考虑它是怎么移过去的。

下面我们使用这个方法，结合上面我们总结的规律进行移动盘子。

第一步，将[1 2 3... n-1]个盘子从A移动到B上，再将 n 盘子移动到C上

// 将A上的n-1个盘子借助C移动到B上  
hanoi(n-1, A, C, B)  
// 将A上的一个盘子移动到C  
hanoi(1, A, B, C)

现在我们的盘子情况为

A：空  
B：有n-1个盘子  
C：最大的n盘子

重点，难点：

由于最大的n盘子上可以放任何盘子，你可以完全忽略它的存在，不用管它，这时候的情形（忽略n盘子的存在）是不是跟初始状态类似呢（一个有盘子，其余的没有盘子）？是的，只不过顺序位置发生了变化并且盘子的数量减少了一个。

我们的总盘子数为：n-1

这时候，我们的B座就是初始状态的A座，A座就是初始状态的B座，C座还是C座。

第二步，将B座上的[1 2 3... n-1-1] 从B移动到A上，将n-1盘子从B移动到C

// 将B上的n-1-1个盘子借助C移动到A上
hanoi(n-2, B, C, A)
// 将B上的一个盘子移动到C
hanoi(1, B, A, C)

现在我们的盘子情况为

A：有n-1-1个盘子
B：空
C：最大的n盘子和倒数第二个n-1盘子

C上的盘子已经摆好，可以认为是空座，是不是又回到了初始状态的情形呢？是的，盘子数减一。

第三步，将A座上的[1 2 3... n-2-1] 从A移动到B上，将n-2盘子从A移动到C

// 将A上的n-2-1个盘子借助C移动到A上
hanoi(n-3, A, C, B)
// 将A上的一个盘子移动到C
hanoi(1, A, B, C)

又回到类似第一步执行后的情形了，如此反复，直到所有盘子都成功移动到C上为止。

经过上述的推敲，我们知道，每经过一步，盘子数少一个，并且A和B两座的位置互换（这里指他们轮流充当初始状态A的角色）。

代码实现(Java)

public static void hanoi(int n, String a, String b, String c) {
    if (n == 1) {
        System.out.println("将" + a + "最上面的盘子移动到" + c);
        return;
    }
    // 当前盘子在a上，将当前盘子数-1放到b上
    hanoi(n-1, a, c, b);
    // 剩下一个放到c上
    hanoi(1, a, b, c);
    // 当前盘子在b上，b是下一轮的a， a b 换位置，进行下一轮
    hanoi(n-1, b, a, c);
}

调用

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

解释一下a b c 和A B C的关系

A B C是实际的盘子座，a b c表示的是一种状态，即初始状态a 表示有待移动的若干个盘子的座，b c始终表示空座（c上可能有盘子，但已经摆好，可以认为为空）。

每移动一轮，A座与B座交换存盘子，若A有盘子，A就是参数a，若B有盘子，B就是参数a，C位置不动。

总之a 始终代表堆着盘子待移动的座。

生活中很多我们觉得有趣的东西，其实都可以通过算法来模拟实验，算法是一种抽象，归纳，总结的过程。

好了，学会了吗？