解题思路

汉诺塔问题要计算移动 n 个金片需要的最少次数。

可以这样想：

• 1 个金片：直接移动 1 次
• 2 个金片：先把小的移到 B（1次），大的移到 C（1次），小的再移到 C（1次），共 3 次
• 3 个金片：7 次

规律是：移动次数每次都翻倍再加 1，也就是 2^n - 1。

为什么是 2^n - 1？

• 移动 n 个金片 = 移动 n-1 个（借助 C 到 B）+ 移动最大那个（1次）+ 再移动 n-1 个（借助 A 到 C）
• 所以 f(n) = 2×f(n-1) + 1
• 从 f(1)=1 推下去，正好是 2^n - 1

n 最大 20，2^20 - 1 = 1048575，用 long long 存一定够。

参考代码

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;

    // n 个金片最少移动 2^n - 1 次
    long long ans = 1;
    for (int i = 0; i < n; i++) ans *= 2;
    cout << ans - 1 << endl;
    return 0;
}

复杂度分析

• 时间复杂度：O(N)，只需要乘 n 次 2
• 空间复杂度：O(1)