Algorithm Gossip: 費式數(shù)列

Fibonacci為1200年代的歐洲數(shù)學(xué)家，在他的著作中曾經(jīng)提到：「若有一只免子每個月生一只小免子，一個月后小免子也開始生產(chǎn)。起初只有一只免子，一個月后就有兩只免子，二個月后有三只免子，三個月后有五只免子（小免子投入生產(chǎn)）......。

如果不太理解這個例子的話，舉個圖就知道了，注意新生的小免子需一個月成長期才會投入生

產(chǎn)，類似的道理也可以用于植物的生長，這就是Fibonacci數(shù)列，一般習(xí)慣稱之為費氏數(shù)列，例

如以下： 1、1 、2、3、5、8、13、21、34、55、89......

解法

依說明，我們可以將費氏數(shù)列定義為以下：、

• f（n）=n (n =0, 1)

• f（n）= f（n-1） +f（n-2） (n > 1)

數(shù)組實現(xiàn)

運行結(jié)果

0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181

請按任意鍵繼續(xù). . .

遞歸實現(xiàn)

運行結(jié)果

0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181

請按任意鍵繼續(xù). . .