C 語言迭代法求費波納契數列：為什麼 i=0、i=num+i、num=i-num？思維逆向工程

面對一段能跑通但「想不出來」的代碼，如何逆向推導作者的設計思路？本文以費波納契數列迭代實現為例，演示從數學定義到變量遞推的完整建模過程，教你掌握「變量狀態機」思維。

原始代碼（已修正語法）

int m, n, i = 0, num = 0;
scanf("%d %d", &m, &n);  // 假設輸入 m=上限, n=項數?
for (i = 0; i <= n; ) {
    if (i < 2) {         // 前兩項特殊處理
        num = 1;
        i++;
    } else {
        i = num + i;     // 關鍵遞推
        num = i - num;   // 關鍵遞推
    }
    if (i > m) {
        printf("%d ", num);
    }
}

數學建模：費波納契遞推關係

定義：F(0)=0, F(1)=1, F(k)=F(k-1)+F(k-2) (k≥2)

目標：輸出不超過 m 的費波納契數。

變量語義重構

遞推邏輯推導

階段 1：初始化前兩項 (i=0,1)

if (i < 2) {
    num = 1;  // F(0)=1? 這裡有bug，應為 F(0)=0, F(1)=1
    i++;
}

注意： 原代碼邏輯有瑕疵（F(0) 算成 1），但核心遞推思想值得學習。

階段 2：通項遞推 (i≥2)

我們需要：F(i) = F(i-1) + F(i-2)

若當前狀態：

• i = 當前索引
• num = F(i-1)（上一項）

則下一項 F(i) = F(i-1) + F(i-2)。

但我們手裡只有 num（F(i-1)），沒有 F(i-2)。

巧妙的狀態壓縮：用 i 暫存 F(i-2)

i = num + i;   // 新 i = F(i-1) + 舊 i
num = i - num; // 新 num = 新 i - F(i-1) = 舊 i = F(i-2)

這是一個原地交換+累加技巧：

• 舊 i 實際存儲的是 F(i-2)（前前項）。
• 第一步：i 更新為 F(i-1)+F(i-2)=F(i)（當前項）。
• 第二步：num 更新為 F(i) - F(i-1) = F(i-2)（供下輪作為前前項）。

狀態機演示表

標準寫法對比（更易讀、無 Bug）

int a = 0, b = 1, next;
while (a <= m) {
    printf("%d ", a);
    next = a + b;
    a = b;
    b = next;
}

• 兩變量 a,b 分別持有 F(k-2), F(k-1)，語義清晰。
• 無需複用循環變量，無邊界 Bug。

如何練就「想得到這種方法」的能力？

1. 手寫狀態表： 寫出前 10 步變量值，觀察規律。
2. 命名語義化： 拒絕 i,num，用 prev, curr, next。
3. 學習經典技巧： 交換變量 a=a+b; b=a-b; a=a-b;、斐波拉契矩陣快速冪、狀態壓縮 DP。
4. 閱讀優秀庫代碼： Linux 內核、STL 實現、Redis 源碼中的位運算、指針算術。

「想不出來」是正常的——這類技巧是前人總結的「模式」，不是靈光一現。多總結變量狀態遷移圖，多重寫經典算法，你也能寫出既巧妙又正確的代碼。