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

· · 题解

思路：

这题分享 C++ 里很简单的字符串做法。

首先，我们可以算出递推式 n = 2(2^{n+1} - 1)。

那么，如果按照这个递推式，你能拿到不错的 50 分。

#include <bits/stdc++.h>
using namespace std;

int n;

int main() {
    cin >> n;
    n--;
    printf("%d\n", 2 * ((int)pow(2, n + 1) - 1));
    return 0;
}

作为第四题能拿到这样的成绩其实也不错了，但是想拿满分也很简单。

只要用到 C++ 里的字符串库就可以了。

s << fixed << pow(2.0L, n + 1)

这一句，是根据递推式 n = 2(2^{n+1} - 1) 来写的。

a = s.str()

这一句，是将算出的 s 存进 a 中，才得输出。

a[a.length() - 1] -= 2;

这一句是把相对应的汉诺塔个数的那一个，减掉多余的 2，这样才能对应我们的递推式。

code：

#include <bits/stdc++.h>
using namespace std;

int n;
string a;
stringstream s; 

int main() {
    cin >> n;
    s.precision(0);
    s << fixed << pow(2.0L, n + 1);
    a = s.str();
    a[a.length() - 1] -= 2;
    cout << a << endl;
    return 0;
}