C語言實作費波納契數列：非遞歸迭代解法詳解

費波納契數列是程式設計入門的經典範例，採用非遞歸的迭代方式實作不僅效率高，更能避免遞歸帶來的堆疊溢位風險。本文將詳細解析如何使用 C 語言透過迴圈結構高效計算費波納契數列的第 n 項。

演算法核心邏輯

費波納契數列定義為：F(1)=1、F(2)=1、F(n)=F(n-1)+F(n-2) (n≥3)。非遞歸解法的核心在於只需維護三個變數：前兩項的值與當前計算結果。透過迴圈逐步推進，將舊值不斷向前移位，即可在 O(n) 時間複雜度與 O(1) 空間複雜度下完成計算。

完整程式碼實作

#include <stdio.h>

int main() {
    int i, n;
    int a = 1, b = 1, c = 1;  // 初始化前兩項與結果變數

    printf("請輸入項數 n: ");
    scanf("%d", &n);

    // 處理 n=1、2 的基本情況
    if (n == 1 || n == 2) {
        printf("第 %d 項結果: %d\n", n, 1);
        return 0;
    }

    // 從第 3 項開始迭代計算
    for (i = 3; i <= n; i++) {
        c = a + b;  // 當前項 = 前兩項之和
        a = b;      // 向前移位：a 取代為原 b
        b = c;      // b 取代為當前計算結果
    }

    printf("第 %d 項結果: %d\n", n, c);
    return 0;
}

關鍵技術細節解析

變數初始化策略

將 a、b 同時初始化為 1，對應數列前兩項。c 同樣初始化為 1，確保 n=1、2 時直接輸出正確結果，無需額外判斷邏輯。

迴圈邊界條件

迴圈從 i=3 開始，條件 i<=n 確保精確執行 n-2 次迭代。每次迭代完成三步操作：計算新值、更新前項、更新當前項，邏輯緊湊高效。

記憶體效率優勢

相較遞歸解法的 O(n) 堆疊空間，迭代僅需 3 個整數變數，空間複雜度為 O(1)。對於大數值 n（如 n=1000000），遞歸會導致堆疊溢位，而迭代仍能穩定運行。

進階優化方向

• 矩陣快速冪：利用矩陣乘法特性，將時間複雜度降至 O(log n)
• 通項公式：使用黃金分割比公式直接計算，但需注意浮點數精度問題
• 大整數處理：配合陣列或字串模擬大數運算，突破 int/long long 範圍限制

常見錯誤與除錯建議

1. 未處理 n≤0：輸入驗證應包含邊界檢查
2. 變數更新順序錯誤：必須先計算 c=a+b，再依序更新 a、b
3. 整數溢位：n>46 時 int 會溢位，建議改用 unsigned long long 或大數庫

掌握非遞歸費波納契實作，不僅是演算法基礎訓練，更能培養對空間複雜度優化的敏銳度。實務開發中，針對線性遞歸關係優先考慮迭代改寫，是提升程式效能的關鍵技巧之一。