汉若塔

传说越南河内某间寺院有三根银棒，上串 64 个金盘，金盘尺寸由下到上依次变小。寺院里的僧侣依照一个古老的预言，以下述规则把这些盘子从第一根银棒移至第三根银棒上 (可以借助第二根银棒):

• 每次只能移动一个圆盘
• 大盘不能迭在小盘上面

预言说当这些盘子移动完毕，世界就会灭亡。这个传说叫做梵天寺之塔问题，即汉若塔问题。

用递归实现的代码很简洁:

public class Test {
    public static void main(String[] args) {
        hanoi(3, 'A', 'B', 'C');
    }

    /**
     * 把 n 个盘子从 a 柱移动到 c 柱，可以借助 b 柱
     *
     * @param n: 盘子的数量
     */
    public static void hanoi(int n, char a, char b, char c) {
        if (n == 1) {
            move(1, a, c);
            return;
        }

        hanoi(n-1, a, c, b); // 小和尚借助 c 柱把 a 柱最上面的 n-1 个盘子移动到 b 柱
        move(n, a, c);       // 老和尚把最下面的一个盘子从 a 柱移动到 c 柱
        hanoi(n-1, b, a, c); // 小和尚再借助 a 柱把 b 柱上的 n-1 个盘子移动到 c 柱
    }

    // sn 是盘子的序号: 开始时 a 柱上的盘子序号从上到下依次为 1, 2, 3, ..., n
    public static void move(int sn, char from, char to) {
        System.out.printf("%d: %c -> %c\n", sn, from, to);
    }
}

代码不多，但是一直理解不了这个递归为什么要这么写，直到大学时人工智能的老师给了个记忆的办法，从此就理解了:

老和尚比较懒 (有点大不敬，忽略之)，于是就叫小和尚把第一根柱子最上面的 n-1 个盘子借助第三根柱子先搬到第二根柱子上，然后老和尚自己把第一根柱子最下面的那个大盘子搬到第三根柱子上，再叫小和尚把第二根柱子上的 n-1 个盘子借助第一根柱子搬到第三根柱子上。