斐波那契數列與矩陣乘法的聯繫以及其python實現

2021-03-06 搬磚的哲學與藝術

 斐波那契數列    即     1、1、2、3、5、8、13、21、34、以此類推，在很多面試題中，面試官都會讓你手寫斐波那契數列的實現。對於一些有編程經驗的人來說，這很容易，他們可以很快寫出類似以下代碼：

設 n 為  大於0的正整數，求第n個斐波那契數（1為第一個，2為第二個...8為第五個）

def feb(n):    if n == 1 or n == 2:        return n    else:        return feb(n - 1) + feb(n - 2)    

但是這裡有個很嚴重的問題就是重複計算
 例如，在計算feb（5） 時，feb（1） 會調用多少次？feb（2）呢？
運行結果可見下圖
可以看到 feb（2）feb(1) 被多次調用
如何能避免這個問題呢？
避免重複 的關鍵在於 要實現檢查即將進行的計算是否已經經歷過。
有同學會想到使用列表，每計算一個feb（n），就將結果存儲到列表的下標n 處。
result=[1,,1,2,3,5,8]
feb(n)=result[n]
這看起來似乎是一個好方法，但因為斐波那契數列可以是無限長的，如果計算feb（10000）是否真的需要長度10000的列表？（況且在python中實際列表所佔地址空間會大於其可見長度。）所以這種方式顯然不是可取的方式。
但是在斐波那契數列數列需要經常進行運算且n較小的時候，直接採取已經定義好的列表看起來的確是個一勞永逸的方法。
但是如果面試官要求你不使用列表，即儘可能減少內存佔用呢？
這裡問題就可以簡化為只使用兩個變量。本身斐波那契數列 中 第n個就是 前兩個數相加的和。
只需要一直更新   feb（n-1）   和  feb(n-2)  的值即可。
現在我們可以使用for循環來實現：
def feb(n):    if n == 1 or n == 2:        return n    else:        n1,n2=1,2        for i in range(3, n):            n1,n2=n2,n1+n2        return n1 + n2
        

這樣做已經效果很好了，不需要藉助數組等大存儲 對象，時間複雜度也只是O（n）級別。
但是有沒有更好的解法？
學習高等數學、線性代數等課程時，可能有數學老師提到過斐波那契數列的另類解法--利用矩陣求解。
數列的遞推公式為：f(1)=1，f(2)=2，f(n)=f(n-1)+f(n-2)(n>=3)
　　 用矩陣表示為：
　　進一步，可以得出直接推導公式：
接下來，我們先思考，如何用python實現矩陣相乘？
如果接觸過numpy  庫的話，你也許會想到numpy中的  dot 方法。
利用這個方法可以直接計算兩個矩陣（列表）的乘積。但是如果讓你自己去實現呢？
先提醒大家，矩陣可以相乘是有前提的
設有矩陣A*B
矩陣只有當左邊矩陣A的列數等於右邊矩陣B的行數時,才可以相乘。乘積結果矩陣的行數等於左邊矩陣的行數,乘積矩陣的列數等於右邊矩陣的列數
矩陣的乘法是左行乘右列


def matrixMul(A, B):  res = [[0] * len(B[0]) for i in range(len(A))]     for i in range(len(A)):     for j in range(len(B[0])):       for k in range(len(B)):           res[i][j] += A[i][k] * B[k][j]  return res

上面的代碼是可用的，但是還有什麼可以優化的地方嗎？
注意到循環的層數足足三層，每一層都需要計算 len（）。
所以最完美的寫法是應該是先計算好長度再直接用長度值去遍歷。

def matrixMul(A, B):  line_A,line_B,column_B=len(A),len(B),len(B[0])   res = [[0] * column_B for i in range(line_A)]     for i in range(line_A):     for j in range(column_B):       for k in range(line_B):           res[i][j] += A[i][k] * B[k][j]  return res
現在，我們可以用 矩陣乘法來 實現 斐波那契數列了
def matrixMul(A, B):  line_A,line_B,column_B=len(A),len(B),len(B[0])   res = [[0] * column_B for i in range(line_A)]     for i in range(line_A):     for j in range(column_B):       for k in range(line_B):           res[i][j] += A[i][k] * B[k][j]  return res
def feb(n):    if n <= 1: return max(n, 0)    res = [[1, 1], [0, 1]]          A = [[1, 1], [1, 0]]      while n:        if n & 1: res = matrixMul(res, A)          A = matrixMul(A, A)          n >>= 1      return res[0][1]

相關焦點

  • Python實現斐波那契數列的幾種方法
    斐波那契數列（Fibonacci sequence），又稱黃金分割數列、因數學家列昂納多·斐波那契（Leonardoda Fibonacci）以兔子繁殖為例子而引入，故又稱為「兔子數列」，指的是這樣一個數列：1、1、2、3、5、8、13、21、34、……在數學上，斐波納契數列以如下被以遞推的方法定義
  • 斐波那契數列的四種實現
    斐波那契數列的輸出，怎樣實現？」我想，討飯一樣的人，也配考我麼？便回過臉去，不再理會。孔乙己等了許久，很懇切的說道，「不能寫罷？……我教給你，記著！這些代碼應該記著。將來做 Leader 的時候，開發項目要用。」我暗想我和 Leader 的等級還很遠呢，而且我們 Leader 也從不在項目裡寫斐波那契；又好笑，又不耐煩，懶懶的答他道，「誰要你教，不是遞歸麼？」
  • python邏輯控制總結——斐波那契數列
    PyCharm工欲善其事，必先利其器。今天，我們先介紹一款python利器，PyCharm。要測評一款IDE（Integrated Development Environment，集成開發環境）工具，是比較複製的。這裡，我們不試圖灌輸PyCharm比其它IDE更優秀的觀點。事實上，工具這種東西，基本功能都是一樣的，比如項目組織，代碼高亮，代碼提示，運行環境等。
  • 斐波那契數列為什麼那麼重要,所有關於數學的書幾乎都會提到?
    本文轉自知乎，作者為王希（數學話題下的優秀回答者）一句話先回答問題：因為斐波那契數列在數學和生活以及自然界中都非常有用。
  • Python中斐波那契數列
    所以本節就講講如何用遞歸實現斐波那契數列。斐波那契數列的發明者，是義大利數學家列昂納多*斐波那契(Leomuado Fibonacci)。當年這個數列是由兔子交配的故事開始講起的：假如說兔子在出生兩個月後，就有了繁殖能力，此後這對兔子在接下來的每個月都能生出一對可愛的小兔子。假設所有兔子都不會老去，就這麼一直折騰下去，那麼一年以後可以繁殖多少對免子出來呢？
  • 矩陣乘法的純Python實現 | 離開Python庫!!
    在《這篇文章》中，我們有簡單提到「矩陣乘法」的相關知識，如果你不記得了，可以複習一下這張圖片。想起來了沒？本篇文章將深入探討在沒有機器學習庫的情況下如何從零實現矩陣乘法！你有沒有想過在沒有任何複雜的機器學習庫的情況下處理機器學習問題？
  • 非常奇妙:黃金分割率、斐波那契數列、楊輝三角與易經河洛的關係
    這個時候，我們來看看斐波那契數列與矩形面積的生成相關，由此可以導出一個斐波那契數列的一個性質。斐波那契數列前幾項的平方和可以看做不同大小的正方形，由於斐波那契的遞推公式，它們可以拼成一個大的矩形。這樣所有小正方形的面積之和等於大矩形的面積。
  • 神奇的斐波那契數列 ——自然界中的斐波那契數列
    而對這些自然、社會以及生活中的許多現象的解釋，最後往往都能歸結到斐波那契數列上來。斐波那契數列在數學理論上有許多有趣的性質。不可思議的是在自然界中也存在著這個性質，似乎完全沒有秩序的植物彼此相隔的距離或葉子的生長，都被斐波那契數列支持著。例如，樹木的生長，由於新生的枝條，往往需要一段「休息」時間，供自身生長，而後才能萌發新枝。
  • 送你一份Python算法的打怪升級路線圖 | 用 Python 實現各種常用算法
    主要包含數學上幾個基本問題，算術分析方法，斐波那契數列問題，以及最大公約數問題。知識點數學幾個基本問題算術分析方法斐波那契數列問題最大公約數問題數學上幾個基本問題在編程界，有這麼幾個經典的數學問題，這裡給大家簡單介紹下。
  • 斐波那契數列
    比薩的李奧納多，又稱斐波那契，中世紀義大利數學家發現了裴波那契數列1、1、2、3、5、8……【即後一數字為前面兩個數字之和】斐波那契螺線：1+1=21+2=32+3=5……34+55=89斐波那契數與黃金數是密切聯繫：相鄰兩個斐波那契數的比近似等於黃金數,數目越大,則越接近,當無窮大時,其比就等於黃金分割數。
  • Fibonacci 斐波那契數列的幾種寫法、時間複雜度對比
    我看在家修煉編程技術是不錯的選擇，「用Python實現斐波那契數列」是我們在知識星球中每周給大家安排的一道題，你也可以先思考一下有哪些實現方法，說不定哪天面試就能派上用場，終有一日當上CTO贏取白富美從此走上人生巔峰。
  • blender python處理矩陣乘法變更符號
    如果對矩陣對象執行任何乘法，要注意一件事情，Python 的最新版本（當然還有包含Blender內置Python版本）為適當的矩陣乘法實現了新的表示方法。用blender腳本編寫器編寫任何矩陣乘法，乘法* 語法仍然有效，這個只能作為 2.8 中嘗試普通乘法，而不是 2.7 中的矩陣乘法。如果你用在矩陣乘法會報出有趣的錯誤，因為這並不一定會拋出一個錯誤，a * ba @ b想要支持 2.7 和 2.8 的相同矩陣乘法樣式？
  • 奇妙的斐波那契數列
    義大利的數學家列昂那多·斐波那契在1202年研究兔子產崽問題時發現了此數列。斐波那契在《計算之書》中提出了一個有趣的兔子問題：假設一對初生兔子要一個月才到成熟期，而一對成熟兔子每月會生一對兔子，那麼，由一對小兔子開始，12個月後會有多少對兔子呢？兔子繁殖的過程可以通過一棵「家族樹」來表示，如圖所示。
  • 神奇的斐波那契數列
    斐波那契數列斐波那契（也叫做比薩的李奧納多）是一個義大利數學家，年少時隨著父親在北非做生意，學習了阿拉伯數字。1200年，斐波那契回到了義大利，1202年寫成了著作《計算之術》，這本書對歐洲的數學界產生了很大的影響。
  • 黃金分割比——斐波那契數列
    斐波那契數列（Fibonacci sequence），又稱黃金分割數列。
  • 斐波那契數列與自然
    斐波那契數列與自然 　　斐波那契數列在自然界中的出現是如此地頻繁，人們深信這不是偶然的． 　　a)細察下列各種花，它們的花瓣的數目具有斐波那契數：延齡草、野玫瑰、南美血根草、大波斯菊、金鳳花、耬鬥菜、百合花、蝴蝶花．
  • 九九乘法表難嗎?用一行python代碼輕鬆解決,沒想到它這麼強
    而一行python代碼可以做到哪些事情呢？下面羽憶教程為你展示。用一行python代碼列印九九乘法表當你身邊沒有計算器，又需要九九乘法表時，可以通過以下一行簡單的python代碼獲得九九乘法表。上代碼：print('\n'.join([' '.join(["%2s x%2s = %2s"%(j,i,i*j) for j in range(1,i+1)]) for i in range(1,10)]))以下是其輸出的九九乘法表：
  • 淺談斐波那契數列-兔子數列-黃金分割數列
    斐波那契數列這個數列是由義大利數學家斐波那契(fěi bō nà qì)提出的，所以叫斐波那契數列。又因這一數列是斐波那契通過兔子繁殖規律例子而引入的，所以又叫兔子數列。斐波那契數列1.斐波那契數列與兔子繁殖問題一般而言，兔子在出生兩個月後就算長大成年了，就有了繁殖能力，一對成年兔子每個月能生出一對小兔子來。我們假設所有兔子都不死，每次都是只生1對兔子。那麼一年以後可以繁殖多少對兔子？
  • 淺談斐波那契數列-兔子數列-黃金分割數列
    斐波那契數列 這個數列是由義大利數學家斐波那契(fěi bō nà qì)提出的，所以叫斐波那契數列。又因這一數列是斐波那契通過兔子繁殖規律例子而引入的，所以又叫兔子數列。另外非常有趣的是這個數列隨著項數的不斷增加，前一項與後一項的比值越來越接近黃金分割比，所以又稱為黃金分割數列。
  • 斐波那契數列:歐洲文藝復興時期的斐波那契和他的《算經》
    文藝復興的前哨義大利，由於其特殊地理位置與貿易聯繫而成為東西方文化的熔爐。義大利學者早在12~13世紀就可以翻譯.介紹希臘與阿拉伯數學文獻。歐洲黑暗時代以後第一位有影響到額數學家斐波那契（約1170~1250），其拉丁文代表著作《算經》，《幾何實踐》等也是根據阿拉伯文與希臘文材料編譯而成的。