什麼是費氏數列?
費氏數列(Fibonacci sequence)是一串整數,其中每個數字都是前兩個數字的總和,由 0 和 1 開始:0、1、1、2、3、5、8、13、21、34、55⋯⋯依此類推。它廣泛出現在數學與大自然之中,從螺旋貝殼、向日葵的種子排列到黃金比例都看得到它的身影。這個計算機可以回傳任意索引 \(n\) 的單一費波那契數 \(F_n\),也能產生起始索引到結束索引之間的整段數列。
如何使用這個計算機
請在產生方式下拉選單中選擇模式。選擇單一數字並輸入索引 \(n\),即可取得單一數值 \(F_n\) 以及它的遞迴運算步驟。選擇數列並輸入起始 \(n\) 與結束 \(n\),便會列出該範圍(含兩端)內的所有費波那契數。索引可以是正數或負數,支援範圍為 -200 到 200。
公式解析
費氏數列的定義規則是遞迴關係
$$F_n = F_{n-1} + F_{n-2}, \quad F_0 = 0, \; F_1 = 1$$其中 \(F_0 = 0\)、\(F_1 = 1\)。為了在 \(n\) 很大時仍能得到精確結果,本工具採用任意精度整數進行迭代運算,而非使用 Binet 公式的浮點計算——後者在 \(n\) 大約超過 71 之後便會喪失精確度。負索引則遵循 negafibonacci 規則 \(F_{-n} = (-1)^{n+1} F_n\),因此 \(F_{-1} = 1\)、\(F_{-2} = -1\)、\(F_{-3} = 2\)、\(F_{-4} = -3\),依此類推。
實際範例
若要求出 \(F_{15}\),可將數列迭代到索引 15:0、1、1、2、3、5、8、13、21、34、55、89、144、233、377、610。因此
$$F_{15} = 610 = F_{14} + F_{13} = 377 + 233 = 610$$費波那契數列參考表(F0 至 F30 及負指數)
費波那契數列定義為 \(F_0 = 0\)、\(F_1 = 1\),且 \(F_n = F_{n-1} + F_{n-2}\)。下表列出前 31 項。
| n | Fn | n | Fn | n | Fn |
|---|---|---|---|---|---|
| 0 | 0 | 11 | 89 | 22 | 17711 |
| 1 | 1 | 12 | 144 | 23 | 28657 |
| 2 | 1 | 13 | 233 | 24 | 46368 |
| 3 | 2 | 14 | 377 | 25 | 75025 |
| 4 | 3 | 15 | 610 | 26 | 121393 |
| 5 | 5 | 16 | 987 | 27 | 196418 |
| 6 | 8 | 17 | 1597 | 28 | 317811 |
| 7 | 13 | 18 | 2584 | 29 | 514229 |
| 8 | 21 | 19 | 4181 | 30 | 832040 |
| 9 | 34 | 20 | 6765 | ||
| 10 | 55 | 21 | 10946 |
負指數
數列可向後延伸,使用 \(F_{-m} = (-1)^{m+1} F_m\)。奇數 \(m\) 給出正值,偶數 \(m\) 給出負值。
| n | Fn | 符號規則 (-1)m+1,m = |n| |
|---|---|---|
| -1 | 1 | m = 1,符號 + |
| -2 | -1 | m = 2,符號 − |
| -3 | 2 | m = 3,符號 + |
| -4 | -3 | m = 4,符號 − |
| -5 | 5 | m = 5,符號 + |
| -6 | -8 | m = 6,符號 − |
| -7 | 13 | m = 7,符號 + |
| -8 | -21 | m = 8,符號 − |
| -9 | 34 | m = 9,符號 + |
| -10 | -55 | m = 10,符號 − |
如何手動計算費波那契數
- 從兩個初始值開始:\(F_0 = 0\) 與 \(F_1 = 1\)。
- 將前兩項相加得到下一項:\(F_2 = F_1 + F_0 = 1\)、\(F_3 = F_2 + F_1 = 2\)、\(F_4 = 3\)、\(F_5 = 5\),依此類推。
- 重複此步驟直到達到指標 n。當 \(n = 10\) 時:0、1、1、2、3、5、8、13、21、34、55,因此 \(F_{10} = 34 + 21 =\) 55。
- 對於負指標,先計算 \(m = |n|\),求出 \(F_m\),再套用符號 \((-1)^{m+1}\)。例如:\(F_{-7} = (-1)^{8} F_7 = (+1)(13) =\) 13。另一例:\(F_{-6} = (-1)^{7} F_6 = -8\)。
- 以黃金比例進行驗算:\(F_n \approx \varphi^n/\sqrt{5}\)。當 \(n = 10\) 時,\(\varphi^{10} \approx 122.99\),且 \(122.99 / 2.23607 \approx 55.0\),與結果相符。此外,對於較大的 n,\(F_{n+1}/F_n\) 應接近 1.618。
- 對於非常大的 n,可使用快速倍增法,而非逐項相加:\(F_{2k} = F_k\,(2F_{k+1} - F_k)\),且 \(F_{2k+1} = F_k^2 + F_{k+1}^2\)。以 \(k = 5\) 檢驗:\(F_{10} = F_5(2F_6 - F_5) = 5 \times (16 - 5) = 55\)。
數值增長非常快:\(F_{100}\) 已有 21 位數,因此對於大的 n 需要精確的整數運算(本計算器支援 n 從 −200 至 200)。
常見問題
支援負索引嗎?支援。本工具採用 negafibonacci 擴充規則,會產生正負交替的結果,例如 \(F_{-6} = -8\)。
n 最大可以多少?支援範圍為 -200 到 200。\(F_{200}\) 共有 42 位數,並透過任意精度整數精確計算得出。
為什麼不直接用 Binet 公式?Binet 的閉合式 \(F_n = \frac{\varphi^n - \psi^n}{\sqrt{5}}\) 在展示上相當優雅,但雙精度浮點的捨入誤差使它在 \(n\) 很大時並不可靠,因此最終答案改採精確的整數迭代計算。