標題:

甚麼是Fibonacci number?

發問:

 

此文章來自奇摩知識+如有不便請留言告知

甚麼是Fibonacci number?Thx

最佳解答:

斐波那契數列 圖片參考：http://upload.wikimedia.org/wikipedia/commons/thumb/8/83/FibonacciBlocks.png/180px-FibonacciBlocks.png 圖片參考：http://zh.wikipedia.org/skins-1.5/common/images/magnify-clip.png 以斐波那契數為邊的正方形拼成的長方形 斐波那契數列（Fibonacci numbers），台灣譯為費伯納西數列。 在數學上，斐波那契數列是以遞歸的方法來定義： F0 = 0 F1 = 1 Fn = Fn - 1 + Fn - 2 用文字來說，就是斐波那契數列由0和1開始，之後的斐波那契數就由之前的兩數相加。首幾個斐波那契數是（OEIS A000045）： 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946 目錄 1 源起 2 表達式 2.1 線性代數解法 2.2 近似值 2.3 用電腦求解 3 和黃金分割的關係 4 恆等式 5 相關的數列 5.1 和盧卡斯數列的關係 5.2 反斐波那契數列 5.3 巴都萬數列 6 應用 7 參考 8 參見 9 外部連結 源起 根據高德納的《計算機程序設計藝術》，1150年印度數學家Gopala和Hemachandra在研究箱子包裝物件長闊剛好為1和2的可行方法數目時，首先描述這個數列。在西方，最先研究這個數列的人是比薩的李奧納多（又名斐波那契），他描述兔子生長的數目時用上了這數列。 第一個月有一對剛誕生的兔子 第兩個月之後牠們可以生育 每月每對可生育的兔子會誕生下一對新兔子 兔子永不死去 假設在n月有新生及可生育的兔子總共a對，n+1月就總共有b對。在n+2月必定總共有a+b對：因為在n+2月的時候，所有在n月就已存在的a對兔子皆已可以生育並誕下a對後代；同時在前一月(n+1月)之b對兔子中，在當月屬於新誕生的兔子尚不能生育。 表達式 為求得斐波那契數列的一般表達式，可以藉助線性代數的方法。 線性代數解法 1 首先構建一個矩陣方程 設Jn為第n個月新出生的兔子數量，An為這一月份的兔子數量。 圖片參考：http://upload.wikimedia.org/math/6/f/a/6fac5c2122b590c76aed21fe4c4e0448.png 上式表達了兩個月之間，兔子數目之間的關係。而要求的是，An+1的表達式。 2 求矩陣的特徵值: λ 行列式：-λ*(1-λ)-1*1=λ2-λ-1 當行列式的值為0，解得λ1= 圖片參考：http://upload.wikimedia.org/math/e/4/f/e4f0faec2cb628809cda8748421fe65e.png 3 特徵向量 將兩個特徵值代入 圖片參考：http://upload.wikimedia.org/math/7/e/e/7ee632f53f33f7b5eced0cf66d97ea91.png }- 求特徵向量 圖片參考：http://upload.wikimedia.org/math/3/2/f/32fdc49edf74bbace2a97623f586a6fb.png 得 圖片參考：http://upload.wikimedia.org/math/a/b/3/ab32bc432cfec40195ce184f9a2a11cd.png 圖片參考：http://upload.wikimedia.org/math/3/a/6/3a6359bee1479878921cc23e97e370cb.png 4 分解首向量 第一個月的情況是兔子一對，新生0對。 圖片參考：http://upload.wikimedia.org/math/5/d/2/5d26f0b7c7f54dd45ad4d726fe76e92d.png 將它分解為用特徵向量表示。 圖片參考：http://upload.wikimedia.org/math/c/c/8/cc80f5820e71659345e5132c3ef11525.png }- （4） 5 用數學歸納法證明 從 圖片參考：http://upload.wikimedia.org/math/b/1/3/b13715e6c661a962a873288fa7f0fd29.png 可得 圖片參考：http://upload.wikimedia.org/math/f/f/a/ffa30051b9a7e058fd17a5409bf07a0a.png （5） 6 化簡矩陣方程 將（4） 代入 （5） 圖片參考：http://upload.wikimedia.org/math/6/a/0/6a08087a30d1e00382906c2e829ad4e6.png }- 根據 3 圖片參考：http://upload.wikimedia.org/math/4/8/6/4864fe499ff7ad460b6149a5b749930b.png }- 7 求A的表達式 現在在6的基礎上，可以很快求出An+1 的表達式,將兩個特徵值代入 6 中 圖片參考：http://upload.wikimedia.org/math/a/0/f/a0f6d931bc7df7e8bfa0b06410ebea43.png 圖片參考：http://upload.wikimedia.org/math/6/c/2/6c2a1f4ba4569b69c9277fb393616190.png 圖片參考：http://upload.wikimedia.org/math/c/9/3/c9394f393bab2168b0a5fa696783026d.png (7) (7)即為An+1 的表達式 近似值 圖片參考：http://upload.wikimedia.org/math/9/b/0/9b08722bd58742ce44a6486344176866.png 用電腦求解 可通過編程觀察斐波那契數列。分為兩類問題，一種已知數列中的某一項，求序數。第二種是已知序數，求該項的值。 可通過遞歸的演算法解決此兩個問題。 和黃金分割的關係 開普勒發現兩個斐波那契數的比會趨近黃金分割： 圖片參考：http://upload.wikimedia.org/math/c/1/c/c1cb19039081e752164d4a822c933d86.png 斐波那契數亦可以用連分數來表示： 圖片參考：http://upload.wikimedia.org/math/5/e/c/5ec9e81a45182c04df3560660b6a9449.png 圖片參考：http://upload.wikimedia.org/math/5/3/d/53dbfe657cc258b3519951e19dce8fb2.png 而黃金分割數亦可以用無限連分數表示： 圖片參考：http://upload.wikimedia.org/math/5/8/1/5813a55fb904495f226e1c4c6ad8df82.png 恆等式 證明以下的恆等式有很多方法。以下會用組合論述來證明。Fn可以表示成用多個1和多個2相加令其和等於n - 1的方法的數目。例如F0 = 0，表示沒有方法可以加到0。在這裡加的過程中，先後次序不同但使用1和使用2的數目一樣的兩個方法視為不同。例如 1+1+2 和 2+1+1 是兩個不同的方法。 Fn + 1 = Fn + Fn ? 1 不失一般性，我們假設n ≥ 1。Fn + 1是計算了將1和2加到n的方法的數目。若第一個被加數是1，有Fn種方法來完成對n-1的計算；若第一個被加數是2，有F(n-1)來完成對n-2的計算。因此，共有Fn + Fn - 1種方法來計算n的值。 F1 + F2 + F3 + ... + Fn = Fn + 2 - 1 計算用多個1和多個2相加令其和等於n+1的方法的數目，同時最後一個加數是2的情況。 如前所述，當n ≥ 0，有Fn + 2種這樣的方法。因為當中只有一種方法不用使用2，就即 1 + 1 + ... + 1（n+1項），於是我們從Fn + 2減去1。 若第1個被加數是2，有Fn個方法來計算加至n-1的方法的數目； 若第2個被加數是2、第1個被加數是1，有Fn - 1個方法來計算加至n ? 2的方法的數目。 重複以上動作。 若第n + 1個被加數為2，它之前的被加數均為1，就有F(0)個方法來計算加至0的數目。 若該數式包含2為被加數，2的首次出現位置必然在第1和n+1的被加數之間。2在不同位置的情況都考慮到後，得出Fn + Fn - 1 + ... + F0為要求的數目。 F1 + 2F2 + 3F3 + ... + nFn = nFn + 2 - Fn + 3 + 2 F1 + F3 + F5 + ... + F2n - 1 = F2n F2 + F4 + F6 + ... + F2n = F2n + 1 - 1 圖片參考：http://upload.wikimedia.org/math/9/d/e/9de260182cad362fcdebbac5e4dd2028.png 圖片參考：http://upload.wikimedia.org/math/d/7/4/d74f4f0e323bab81047d942fb26b9f84.png 相關的數列 斐波那契數列是盧卡斯數列的特殊情況。或是斐波那契n步數列步數為2的情形。 和盧卡斯數列的關係 反斐波那契數列 反斐波那契數列的遞歸公式如下： Gn + 2 = Gn ? Gn + 1 如果它以1,-1，之後的數是：1,-1,2,-3,5,-8, ... 即是F_{2n+1} = G_{2n+1}，F_{2n} = - G_{2n}。 反斐波那契數列兩項之間的比會趨近 圖片參考：http://upload.wikimedia.org/math/5/d/c/5dc21b00610b5fb4665262dacbb7ce0f.png 。 巴都萬數列 斐波那契數列可以用一個接一個的正方形來表現，巴都萬數列則是用一個接一個的等邊三角形來表現，它有Pn + 2 = Pn ? 2 + Pn ? 3的關係。 應用 1970年，Yuri Matiyasevich 指出了偶角標的斐波那契函數 y = F2x 正是滿足 Julia Robison 假設的丟番圖函數，因而證明了希爾伯特第十問題是不可解的。 參考 Donald E. Knuth: THE ART OF COMPUTER PROGRAMMING Volume 1/Fundamental Algorithms. 第一章第 1.2.8 節《斐波那契數》。 本頁的英語、德語和日語版本 參見 齊肯多夫定理

其他解答:

本身想copy晒成段野俾你睇.. 但可惜,太多圖片...copy唔到黎依度...俾個網址你慢慢睇>.< http://en.wikipedia.org/wiki/Fibonacci_number 希望你明啦^^唔明再問我..0D7DAC4E6DF60DFA
arrow
arrow
    文章標籤
    向量 次序 普勒 公式 必然
    全站熱搜

    lgzrelv 發表在 痞客邦 留言(0) 人氣()

    E-mail轉寄