原题链接点这里。

对于有n个圆盘的汉诺塔问题，它的最优步骤是需要2^n - 1步，而且可以证明每一步都是固定的。参考这里。

即，对于有n个圆盘的汉诺塔问题，我们可以分为三个步骤：

​ ①把 前n-1个圆盘从A移动到B，需要 (2^(n-1) - 1) 步。

​ ②把 第n个圆盘从A移动到C，需要 1 步。

​ ③把 前n-1个圆盘从B移动到C，需要 (2^(n-1) - 1) 步。

例如：有4个圆盘的情况：

• 移动4个圆盘时需要用到移动3个圆盘的操作（即先把前3个圆盘从A移动到C，需要(2\^(3-1) - 1) + 1 + (2^(3-1) - 1) = 2^3-1步）;

• 移动3个圆盘时需要用到移动2个圆盘的操作（即先把前2个圆盘从A移动到C，需要(2\^(2-1) - 1) + 1 + (2^(2-1) - 1) = (1 + 1 + 1) = 2^2-1 步）;

• 移动2个圆盘时需要用到移动1个圆盘的操作（即先把前1圆盘从A移动到C，需要0 + 1 + 0 = 1步）;

• 移动1个圆盘只需要1步（2^1 - 1）。

以此类推，对于N个圆盘从A移动到C的问题，

我们只需要先把最上面的N-1个圆盘移动到B，

再把最后一个圆盘移动到C，

最后再把在B上暂存的N-1个圆盘移到C上就可以了。

至于N-1个圆盘怎样移动（从A移动到B），

只需要向前类推，

研究N-2个圆盘的情况，

再向前依次类推，最终推至1个圆盘的情况，

从而问题得到最终解决。

模拟汉诺塔问题的代码：

#include<bits/stdc++.h>

typedef long long LL;

using namespace std;
const LL N = 1e7 + 10, mod = 1e9;

LL cnt, num;
map<LL, char> mp;
stack<LL> arr[3];

void move(char x, char y)
{
    cnt++;
    LL t = arr[x - 'A'].top();
    arr[x - 'A'].pop();
    arr[y - 'A'].push(t);
    mp[t] = y;  
    bitset<32> b(cnt);
    for (int i = 7; i >= 0; i--) {
        cout << b[i];
    }

    printf("(%03lld)步状态", cnt);
    for (int i = num; i >= 1; i--) {
        cout << mp[i];
    }
    cout << endl;

}

void hanoi(LL num, char a, char b, char c) {
    if (num == 1) {
        move(a, c);
    }
    else {
        hanoi(num - 1, a, c, b);
        move(a, c);
        hanoi(num - 1, b, a, c);
    }

}

void solve()
{
    printf("请输入汉诺塔的层数：");
    scanf("%d", &num);
    for (int i = 1; i <= num; i++) {
        mp[i] = 'A'; 
        arr[0].push(i);
    }
    hanoi(num, 'A', 'B', 'C');
}


int main() {
    LL T = 1;
    //cin >> T;
    while (T--) {
        solve();
        //cout << endl;
    }


}