起源

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

传说越南河内某间寺院有三根银棒，上串 64 个金盘。寺院里的僧侣依照一个古老的预言，以上述规则移动这些盘子；预言说当这些盘子移动完毕，世界就会灭亡。这个传说叫做梵天寺之塔问题（Tower of Brahma puzzle）。但不知道是卢卡斯自创的这个传说，还是他受他人启发。
若传说属实，僧侣们需要264−12^{64} - 1步才能完成这个任务；若他们每秒可完成一个盘子的移动，就需要 5849 亿年才能完成。整个宇宙现在也不过 137 亿年。

这个传说有若干变体：寺院换成修道院、僧侣换成修士等等。寺院的地点众说纷纭，其中一说是位于越南的河内，所以被命名为“河内塔”。另外亦有“金盘是创世时所造”、“僧侣们每天移动一盘”之类的背景设定。

求解思想


解法的基本思想是递归。假设有 A、B、C 三个塔，A 塔有NN块盘，目标是把这些盘全部移到 C 塔。那么先把 A 塔顶部的N−1N - 1块盘移动到 B 塔，再把 A 塔剩下的大盘移到 C，最后把 B 塔的 N−1N - 1块盘移到 C。
f(n)=f(n−1)∗2+1f(n) = f(n - 1) * 2 + 1
复杂度应为2n−12^n - 1

如此递归地使用下去, 就可以求解。

递归解

盘子自上到下编号依次为1、2、3 … n

1
2
3
4
5
6
7
8
9
10
11
12
13
public class Main {
    public void hanoi(int n, char a, char b, char c){       //目标操作a->c, 中间变量b
        if(n == 1) System.out.println("1th plate: " + a + "->" + c);
        else{
            hanoi(n - 1, a, c, b); //现将1~ n-1从a移到b
            System.out.println(n + "th plate: " + a + "->" + c); //将n移到c
            hanoi(n - 1, b, a, c); //将1~ n-1从b移到c
        }
    }
    public static void main(String[] args) {
        new Main().hanoi(3, 'a', 'b', 'c');
    }
}

运行结果：

1
2
3
4
5
6
7
8
9
10
/Users/ray/Library/Java/JavaVirtualMachines/openjdk-15.0.2/Contents/Home/bin/java -javaagent:/Users/ray/Library/Application Support/JetBrains/Toolbox/apps/IDEA-U/ch-0/211.7142.45/IntelliJ IDEA.app/Contents/lib/idea_rt.jar=63346:/Users/ray/Library/Application Support/JetBrains/Toolbox/apps/IDEA-U/ch-0/211.7142.45/IntelliJ IDEA.app/Contents/bin -Dfile.encoding=UTF-8 -classpath /Users/ray/IdeaProjects/oj/out/production/oj com.company.Main
1th plate: a->c
2th plate: a->b
1th plate: c->b
3th plate: a->c
1th plate: b->a
2th plate: b->c
1th plate: a->c

Process finished with exit code 0