昨天發了一篇斐波那契數列的遞歸和非遞歸求法，結果大家紛紛詢問其他方法可不可以，詢問哪種方法更靠譜，我滴個神，其他方法當然可以，條條大路通羅馬嘛，況且代碼這個東西，本就靈活多變。
那今天，我乾脆直接把我所能想到的實現斐波那契數列的方法和代碼都貼在這，方便大家參考~~~
還有，千萬別問我這是不是小學生學的東西了，捂臉。這真的是編程入門級的算法，我遇到很多小學生編程超級厲害的hhh。
好了，閒言少敘，開始正題：
一：遞歸實現
在學校裡學習遞歸的時候，老師就喜歡舉斐波那契這個例子，看！多簡潔清晰。其實這個例子是非常不適合作為遞歸舉例的，原因就是效率太慢，除了最後一個數，每個數都被算了一遍又一遍，時間複雜度差不多是5n^2/3。
昨天有說過，遞歸實現，而且還討論了它的時間複雜度，那一長串表達式，如果能理解更好，不理解也沒關係，記得它的時間複雜度差不多是5n^2/3就好。
關鍵代碼如下：
方法一遞歸Fib1
二：數組實現
昨天也有小夥伴問數組可不可以，當然可以！
用數組實現，其空間複雜度和時間複雜度都是0(n)，效率一般，比遞歸來得快。
代碼如下：
方法二數組Fib2
三：vector實現
vector是一個動態的序列容器，相當於一個size可變的數組。
相比於數組，vector會消耗更多的內存以有效的動態增長。而相比於其他動態序列容器(deques, lists and forward_lists)，vector能更快的索引元素(就像數組一樣)，而且能相對高效的在尾部插入和刪除元素。如果不是在尾部插入和刪除元素，效率就沒有這些容器高。
使用這種方法空間複雜度是0(n)，時間複雜度是0(1)。
代碼如下：
方法三Fib3
四：queue
隊列比數組更適合實現斐波那契數列，時間複雜度和空間複雜度和vector
不過大部分初學者一開始是不會接觸到隊列的，講編程的時候，也不會這麼粗暴地直接就講隊列，所以一般來說，一開始大家不知道這種方法也是沒有辦法的，我這邊列出來，大家參考一下，知道有這種方法就好。
代碼如下：
Fib4 最合適的方式
五：迭代實現
迭代實現是最高效的，昨天有介紹了這個方法，不知道大家懂了沒有，時間複雜度是0(n)，空間複雜度是0(1)。
代碼如下：
Fib5 最簡單的方式
六：矩陣實現
昨天好多小夥伴也都說，矩陣實現最好最優雅了，來來來，我們瞭解一下矩陣實現的原理。
矩陣（matrix）定義
一個m*n的矩陣是一個由m行n列元素排成的矩形陣列，矩陣裡的元素可以是數字符號或者數學式。
一個最簡單的矩陣長這樣：
它是一個具體的數，並且結果等於ad-bc。
斐波那契數列矩陣
數斐波那契列的遞推公式為：f(1)=1，f(2)=2，f(n)=f(n-1)+f(n-2)(n>=3)
用矩陣表示為：
進一步，可以得出直接推導公式：
由於矩陣乘法滿足結合律，在程序中可以事先給定矩陣的64，32，16，8，4，2，1次方，加快程序的執行時間。（有些題目需要取模運算，也可以事先進行一下）。
哎呀，到此打住吧，矩陣實現代碼太長，就不截圖放上來了，想要的同學可以私信我。
七：公式實現
原來斐波那契數列有公式啊，那老師幹嘛不直接教我們公式呢，教我們公式，當然要告訴我們推導啊，這個推導過程，emmmmm，實在喪心病狂。
來看一眼這個公式：
斐波那契通項公式
而且利用公式的話，由於double類型的精度還不夠，所以程序算出來的結果有誤差，當然初期我們可能不care這個誤差，但是計算機是一個嚴謹的學科，ennn，算了，不說大道理了。
代碼如下：
Fib7
閱讀更多 日常程序媛 的文章
