题解：P1096 [NOIP2007 普及组] Hanoi 双塔问题

【原题】

主要题意

本题就是一般汉诺塔的翻倍版本（所有圆盘变为 $2$ 个）。其中，每次只能移动一个圆盘，圆盘要保持下面的比上面的大。

题目分析

不难发现，两个相同大小的圆盘应一起移动，才能使总次数尽可能小。

我们可以用递推算法解决本题，递推需要初始条件和递推式。题目提示我们可以设法建立 $A_n$ 与 $A_{n-1}$ 的递推关系式。所以初始条件应为 $A_1$。很明显，$A_1 = 2$，也就是把两个圆盘从 A 移到 C。

而 $n = 2$ 时，我们可以： 1. 先把两个小的圆盘从 A 移到 B，花费 $A_1$ 步； 2. 再把下面两个最大的圆盘从 A 移到 C，花费 $2$ 步； 3. 最后把两个小的圆盘从 B 移到 C，花费 $A_1$ 步；

共计 $2 \times A_1 + 2$ 步。因此，$A_n = 2 \times A_{n-1} + 2$。

代码实现

我们可以用以上思路编写出以下程序：

#include<bits/stdc++.h>
using namespace std;
long long n, a[222];
int main(){
    cin >> n;
    a[1] = 2;
    for(int i = 2; i <= n; i++){
        a[i] = a[i-1] * 2 + 2; // 递推式
    }
    cout << a[n];
}

（此代码 $70$ 分）

但是，如果我们分析一下数据范围，$2^{200}$ 很大（本题中 $1 \le n \le 200$），而 long long 最大只有 $2^{63} - 1$。因此需要使用高精度，大概可以把数组开到 $100$ 项。

代码：

#include<bits/stdc++.h>
using namespace std;
int n, a[222][100], len[222] = {0};
int main(){
    cin >> n;
    a[1][0] = 2; len[1] = 1;               // 设置递推初始条件
    for(int i = 2; i <= n; i++){
        a[i][0] += 2;                      // 先给个位加 2
        len[i] = len[i-1];                 // 继承上一个数的位数
        for(int j = 0; j < len[i-1]; j++){ // 高精度，反着存数
            a[i][j] += 2 * a[i-1][j];
            if(j == len[i] - 1 && a[i][j] >= 10){
                len[i]++;                  // 进位可能导致位数增加，需要判断
            }                              // 本题只是乘 2 再加 2，无需多次进位，因此只判断一次
            a[i][j+1] += a[i][j] / 10;
            a[i][j] %= 10;                 // 进位处理
        }
    }
    for(int i = len[n] - 1; i >= 0; i--){
        cout << a[n][i];
    }
}

（此代码 $100$ 分。）