C語言的學習要從基礎開始，這裡是C語言的100個經典的算法（一）。
斐波那契數列：
題目：古典問題：有一對兔子，從出生後第3個月起每個月都生一對兔子，小兔
子長到第三個月後每個月又生一對兔子，假如兔子都不死，問每個月的兔子總數
為多少？
斐波那契數在自然界
題目分析：
不難看出，每個月兔子的數量以1,1,2,3,5，8,13,21.......的規律增加。
看出了這裡，接下來的事情就是根據規律求第n月的兔子數了。
代碼編寫
由於代碼直接複製來顯示不太美觀，故我就直接放截圖啦，同時也是為了避免大家直接複製代碼運行，對於初學者，我還是畢竟建議大家自己敲一遍代碼的，這樣印象會更加深刻。
不過如果有小可愛需要代碼，可以私信我要喲~
方法一：遞歸法
以上這種方法是最常見也是我們容易理解的方法，直接利用了斐波那契數列的數學公式：f(n)=f(n-1)+f(n-2)。
但是，它常見可不代表這種方法好喲，我們來分析一下它的時間複雜度：
設f(n)為參數為n時的時間複雜度，很明顯：f(n)=f(n-1)+f(n-2)
這就轉化為了數學上的二階常係數差分方程，並且為其次方程。
即轉化為了求f(n)的值，f(n)=f(n-1)+f(n-2)且f(0)=0; f(1)=1;
特徵方程為：x^2-x-1=0
得 x=(1±√5)/2
因而f(n)的通解為：
最終可得，遞歸方法的時間複雜度為：
到這裡，初學者應該已經懵了，代碼編寫好，能輸出結果就可以了嘛，“時間複雜度”是什麼鬼？為什麼我們還要討論“時間複雜度”這個東西呢？
這就是算法裡需要討論的問題了，很多時候【初學C語言】，我們的程序只要求準確性就好了，只要能輸出正確結果，我們就滿足了，但是，在更多時候，我們要求我們的代碼不僅能正確輸出結果，還要在規定的時間內輸出結果，這個時候，時間複雜度太大的程序就不可行了。
你想想，如果我編寫了一個程序，輸出一個結果要用整整一天甚至一個月，一年，想起來是不是不可接受？所以，我們要對時間複雜度特別大的代碼進行優化，讓代碼在我們能接受的時間範圍內輸出正確的結果。
反正，你只要記住，上面的遞歸方法求斐波那契數列是一個時間複雜度為指數級別的程序，這個複雜度是一個相對來說很大的複雜度，當n很大的時候，其實不用很大，n=1000甚至n=100,50的時候，就能很明顯地感受到這個方法輸出結果特別慢。因為它要重複計算很多已經計算過的式子。
方法二：非遞歸方法
這個方法也很好理解，循環暴力把前兩個數加起來賦值給第三個，這種方法只for循環一次，故時間複雜度為O(n)，比起前面的遞歸來說實在好太多了。
所以你看吶，初學者一般會以為遞歸的方法比暴力求解的方法更好，事實上並不完全如此，所有的方法都有它的好處和缺點，尤其是在計算機領域，到目前還沒有找到一種方法任何一個地方都好。
閱讀更多 日常程序媛 的文章
