著名的費氏數列命名源自於研究兔子繁殖的問題，義大利商人之子費波那契自此名垂千古。時至今日，我們仍然可以在許許多多數學應用和程式演算法中發現費波那契的名字，有專門討論費氏數列的季刊，有同名的搖滾樂團，甚至有人以他的名字命名了一顆小行星（6765費波那契）。在這一章我們就來研究著名的費氏數列，以不同的演算法實做費氏數列，再比較一下各種演算法的速度快慢。
數學關鍵字： 費氏數列。
數學家：費波那契。
Scratch程式：
費波那契的兔子繁殖問題
費波那契生在十二世紀末的義大利，青少年時期開始就隨著他的父親在北非做生意，因此有機會學會數學和阿拉伯數字系統。之後他將所學寫成「計算之書」（Liber Abaci），用阿拉伯數字系統縯示了商業簿記、度量衡轉換、利率計算等等非常實用的應用。當時羅馬流行的數字系統是源自古埃及的一種計算方法，使用珠算當成計算輔助工具。費波那契在他的書裡展示了阿拉伯數字在商業計算上的快速和方便性，在他的引介下歐洲開始使用阿拉伯數字，為日後的歐洲的銀行和會計發展奠定了基礎。
在「計算之書」裡，費波那契提出了一個兔子繁殖問題。他假設有一對一公一母的幼兔二個月可以長為成兔，之後每個月都可以繁殖產下另一對一公一母的幼兔。每對新產下幼兔經歷相同的兩個月成長過程後，每個月再繁殖生下一對幼兔。假設所有的兔子都會存活，經歷如此生生不息的繁殖，一年後兔子的數量有多少對？
歸納一下兔子繁殖的過程，可以列舉出每個月兔子在數量上的變化，
- 第一個月底的時候只有一對幼兔。
- 第二個月底的時候這對幼兔長為成兔。
- 第三個月底的時候第一對成兔生下幼兔，變為兩對兔子。
- 第四個月底的時候第一對成兔再生下幼兔，上個月的幼兔長為成兔，總共有三對兔子。
費波那契在「計算之書」提出了這個問題的解答，他列出了每一個月兔子數量的增長，得到像下面的數列，
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, …
這就是著名的費氏數列，它的特性是除了起始項以外，每一個數字都是前兩個數字的加總。在現代的應用我們通常還會在最前面加上一個起始項0,
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, …
以數學符號表示，費氏數列裡的任一個數Fn可以寫成下面的遞迴關係式，
Fn = Fn-1 + F n-2
起始值設為，
F0 = 0, F1 = 1.
動手做7–1 用迴圈求解費波那契數列
[程式設計需求規格]
費氏數列最顯著的特徵就是後項數字等於前兩項數字的總和。下表列出了前21項費氏數列，讓我們任意選取幾項數字檢驗看看有沒有合乎費氏數列的規則。
我們挑選F15和F16做檢查，驗證它們的確符合費氏數列的規則，各自都是前兩項數字的加總。
610 = 377 + 233 →F15 = F14 + F13
987 = 610 + 377 → F16 = F15 + F14
在動手做7–1裡我們要嘗試將下列[費氏數列演算法 1]化為Scratch的程式。
[費氏數列演算法 1]Fn = Fn-1 + F n-2， 起始值設為F0 = 0, F1 = 1
[程式設計角色和舞台]
由於舞台只會顯示變數和清單，可由範例庫任意選取一個角色造形後隱藏。舞台維持空白即可。
[程式設計解決方案]
[程式檢視]
程式［Cat 7–1.2］裡要製做四個變數：n，費氏數1，費氏數2，費氏數3。勾選變數讓變數的數值可以顯示在舞台。
變數＂n＂表示計算到費氏數的第n項，注意到程式裡並沒有直接設定n的值，而是讓n顯示在舞台上，讓使用者直接在舞台上輸入n的數值。
另外三個變數就代表了演算法1裡的費氏數：
Fn→費氏數3
Fn-1→費氏數2
Fn-2→費氏數1
程式一開始就將費氏數1設為0，費氏數2設為1，以轉換演算法1裡的起始設定：F0 = 0, F1 = 1 。之後執行（n-2）次迴圈，將費氏數3的值設為費氏數1和費氏數2的和，以轉換演算法1裡的式子：Fn = Fn-1 + F n-2。
當第一次執行迴圈時變數的運算如下，在這裡的 ＂=＂並不是等號，而是「指定」的意思。計算後的結果會存入「費氏數重複迴圈」清單。「費氏數重複迴圈[1]」則代表清單的第一項資料。
費氏數3 = 費氏數1 + 費氏數2 = 1 + 2 = 3
費氏數1 = 費氏數2 = 2
費氏數2 = 費氏數3 = 3
費氏數重複迴圈[1] = 費氏數3 = 3
第二次執行迴圈變數的運算則會變成，
費氏數3 = 費氏數1 + 費氏數2 = 2 +3 =5
費氏數1 = 費氏數2 = 3
費氏數2 = 費氏數3 = 5
費氏數重複迴圈[2] = 費氏數3 = 5
首先我們將舞台顯示的變數n設定好，表示我們要計算到費氏數列的第n項。在底下的範例中我們設定n為50。按下小綠旗執行，舞台畫面顯示的變數和清單數字就開始變化。
幾乎是在一瞬間電腦就算出了前50項的費氏數。觀察時間記錄，每一次計算新的費氏數只花費非常少的時間。
延伸閱讀：
Scratch & Math: 天花板上的蜘蛛（一） 天花板上的蜘蛛（二）
Scratch & Math: 直線裡的宇宙觀（一） 直線裡的宇宙觀（二）
Scratch & Math: 不能說的祕密（一） 不能說的祕密（二）
Scratch & Math: 無理的道理（一） 無理的道理（二） 無理的道理（三）
Scratch & Math: 歡樂派（一） 歡樂派（二） 歡樂派（三） 歡樂派（四）
Scratch & Math: 隱藏在花朶裡的祕密（一） 隱藏在花朶裡的祕密（二）
Scratch & Math: 兔子繁殖是一個好問題 (一) 兔子繁殖是一個好問題 (二) 兔子繁殖是一個好問題 (三)
