暑期培訓筆記：64位整數、斐波那契遞歸與動態規劃優化

140725 暑期培訓重點筆記

1. C++ 中 64 位整數的定義與輸出

• 類型：__int64（MSVC）或 long long（標準 C++11）
• 輸出格式：%I64d（Windows/MSVC）或 %lld（Linux/GCC）

2. 斐波那契數列的遞歸實現

int F(int n) {
    if (n == 1 || n == 2) return 1;
    return F(n-1) + F(n-2);
}

遞歸兩要素：邊界條件（n=1,2）與遞歸方程（F(n)=F(n-1)+F(n-2)）。但純遞歸指數級複雜度，實際不可用。

3. 動態規劃優化：預計算 + O(1) 查詢

利用數組預存前 50 項，避免重複計算：

#include <stdio.h>
int main() {
    int n, m, i;
    int s[50];
    s[0] = 0; s[1] = 1;
    for (i = 2; i < 50; ++i) s[i] = s[i-1] + s[i-2];
    scanf("%d", &n);
    while (n--) {
        scanf("%d", &m);
        printf("%d\n", s[m]);
    }
    return 0;
}

核心思想：將遞歸轉為迭代，利用空間換時間，預計算所有可能查詢值，單次查詢 O(1)。適用於多次查詢、數據範圍固定的場景。

總結

1. 遞歸需找準邊界與遞推關係，但注意效率。
2. 動態規劃/預計算是解決重疊子問題的標準手段。
3. 64 位整數跨平台輸出需注意格式符差異。