POJ 1953 World Cup Noise：斐波那契遞推計算無連續1二進制串數量

問題描述

求長度為 n (≤ 50) 的二進制字符串中，不包含連續 1 的字符串個數。多測試用例，輸出格式 Scenario #k:。

遞推關係

設 f[n] 為長度 n 合法串數。
考慮首位：
- 首位為 0：剩餘 n-1 位任意合法 → f[n-1]
- 首位為 1：第二位必為 0，剩餘 n-2 位任意合法 → f[n-2]
故 f[n] = f[n-1] + f[n-2]。
初值：f[1]=2 (0,1)，f[2]=3 (00,01,10)。
即斐波那契數列平移：f[n] = Fib(n+2)。

代碼實現

#include 
using namespace std;
int main() {
    long long f[51];
    f[1] = 2; f[2] = 3;
    for (int i = 3; i <= 50; i++) f[i] = f[i-1] + f[i-2];
    int T; cin >> T;
    for (int tc = 1; tc <= T; tc++) {
        int n; cin >> n;
        cout << "Scenario #" << tc << ":\n" << f[n] << "\n\n";
    }
    return 0;
}

複雜度

• 預計算：O(50)
• 查詢：O(1)
• 空間：O(50)

總結

POJ 1953 是斐波那契遞推的入門例題。建模「無連續 1 二進制串」→ 首位分類 → 遞推 f[n]=f[n-1]+f[n-2]。預計算斐波那契數組，O(1) 回答查詢。注意輸出格式的空行。