思路与算法

双塔的最少移动满足A_n=2A_(n-1)+2，十进制数位数组逐次乘2加2；区别于普通汉诺塔输出具体移动和GESP单向移动。

正确性说明

先把较小的全部双盘移到辅助柱，两个最大同尺寸盘各移动一次，再搬回较小双盘，构造2A_(n-1)+2。任何方案移动最大盘前都必须清空其上小盘，最后也必须把小盘移到目标，因此此下界恰可达到。

复杂度

O(n²)数位时间、O(n)数位空间；答案十进制位数O(n)，含初始化与输出。

易错点

n=200已超过64位，初值A0=0；两个相同大小盘仍每次只能移动一个。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n;
    cin >> n;
    vector<int> a(1);
    while (n--) {
        int carry = 2;
        for (int &x : a) {
            int v = 2 * x + carry;
            x = v % 10;
            carry = v / 10;
        }
        while (carry) {
            a.push_back(carry % 10);
            carry /= 10;
        }
    }
    for (int i = a.size() - 1; i >= 0; i--)
        cout << a[i];
    cout << "\n";
}