主要内容 #

1. Hanoi问题介绍
2. Hanoi问题由来
3. 编程求解

1. Hanoi问题介绍 #

汉诺塔（港台：河内塔）（Tower of Hanoi）是根据一个传说形成的数学问题：
有三根杆子A，B，C。A杆上有 N 个 (N>1) 穿孔圆盘，盘的尺寸由下到上依次变小。要求按下列规则将所有圆盘移至 C 杆：

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

提示：可将圆盘临时置于 B 杆，也可将从 A 杆移出的圆盘重新移回 A 杆，但都必须遵循上述两条规则。

问：如何移？最少要移动多少次？

2. Hanoi问题由来 #

传说
最早发明这个问题的人是法国数学家爱德华·卢卡斯。
传说越南河内某间寺院有三根银棒，上串 64 个金盘。寺院里的僧侣依照一个古老的预言，以上述规则移动这些盘子；预言说当这些盘子移动完毕，世界就会灭亡。这个传说叫做梵天寺之塔问题（Tower of Brahma puzzle）。但不知道是卢卡斯自创的这个传说，还是他受他人启发。
若传说属实，僧侣们需要 2^{64}-1 步才能完成这个任务；若他们每秒可完成一个盘子的移动，就需要 5849 亿年才能完成。整个宇宙现在也不过 137 亿年。
解答
在真实玩具中，一般 N=8；最少需移动 255 次。如果 N=10，最少需移动 1023 次。如果N=15，最少需移动32767次；这就是说，如果一个人从 3 岁到 99 岁，每天移动一块圆盘，他最多仅能移动 15 块。如果 N=20，最少需移动 1048575 次，即超过了一百万次。

3. 编程求解 #

算法介绍
假设h(n)为将N个盘子从A柱移动到C柱所需移动的次数，

• 当N = 1时，h(1)=1。
• 当N = 2时，先将A柱子上的小盘子移动到B柱上，然后将A柱上大盘子移动到C，再将B柱上的小盘移动到C，共计3次，h(2)=3。
• 如下图为N=3时，h(3)=7：

• 如下图为N=4时，h(4)=15：

以此类推，假设有 A、B、C 三个塔，A 塔有 N 块盘，目标是把这些盘全部移到 C 塔。那么先借助于C把 A 塔顶部的 N – 1块盘移动到 B 塔，再把 A 塔剩下的大盘移到 C。在借助于A，最后把 B 塔的N – 1块盘移到 C，总共移动了h(N)=h(N-1)+1+h(N-1)个盘次。
所以有h(n)=2h(n-1)+1，h(1)=1。
参考程序

#include < iostream >
using namespace std;
int main(){
    int x, y, n;
    cin >> n;
    if(n == 1){
        cout << 1 << endl;
        return 0;
    }
    x = 1;
    y = 0;
    for(int i = 1; i < n; ++i){
        y = 2 * x + 1;
        x = y;
    }
    cout << y << endl;
    return 0;