From Gossip@caterpillar

Algorithm Gossip: 費式數列

說明

Fibonacci為1200年代的歐洲數學家，在他的著作中曾經提到：「若有一隻免子每個月生一隻小免子，一個月後小免子也開始生產。起初只有一隻免子，一個月後就有兩隻免子，二個月後有三隻免子，三個月後有五隻免子（小免子投入生產）......」。

如果不太理解這個例子的話，舉個圖就知道了，注意新生的小免子需一個月成長期才會投入生產，類似的道理也可以用於植物的生長，這就是Fibonacci數列，一般習慣稱之為費氏數列，例如以下：
1、1 、2、3、5、8、13、21、34、55、89......

解法

依說明，我們可以將費氏數列定義為以下：

fn = fn-1 + fn-2　　 if n > 1
fn = n　　　　　　 if n = 0, 1

演算法

費氏陣列的解法很多，基本上可以使用遞迴解，演算法最簡單，如下：

Procedure FIB(N) [
    IF (N < 0)  
        PRINT ("輸入錯誤"); 

    IF (N = 0 OR N = 1) 
        RETURN (N); 
    ELSE 
        RETURN ( FIB(N-1) + FIB(N-2) ); 
]

簡單，但是不實用，因為太慢了，在求每一個費氏數時，都會發生嚴重的重覆計算，也就是遞迴該行 ( FIB(N-1) + FIB(N-2) )，最差的big-o可以到2的n/2次方，畫張遞迴的樹狀圖就可以知道重覆計算的數有多少了。

可以採取非遞迴的版本，可以將big(o)減至n，演算法如下：

Procedure FIB(N) 
    a = 1; 
    b = 1; 
    FOR i = 2 TO N [
        temp = b; 
        b = a + b; 
        a = temp; 
    ]
    RETURN b; 
]

若想要一次列出所有N之前的費氏數，則可以將for迴圈的部份改以陣列，也就是：

F(0) = 0; 
F(1) = 1; 
FOR i<-2 TO N [
    F(i) = F(i-1) + F(i-2); 
]

費氏陣列並不是使用遞迴來解一定不好，事實上單就執行次數上來說，有一個使用遞迴的演算法可以更快 (big(o)是以2為底的Logn值)，但是要使用到乘法運算，所以實際上要看所使用的機器而定。

Procedure FIB(N) 
    IF (n <= 1)
        RETURN(n); 

    IF (n = 2) 
        RETURN(1); 
    ELSE [ 
        i = n/2; 
        f1 = FIB(i+1); 
        f2 = FIB(i); 

        IF (n mod 2 = 0)
            RETURN( f2*(2*f1-f2) ); 
        ELSE 
            RETURN ( f1**2+f2**2 ); 
    ]
]

您可以實際使用費氏數列來印證演算法中的那兩條公式，其中f1**2表示f1的平方；若將遞迴的樹狀圖畫出來，就像這樣：

另外費氏數列還有公式解，導證方式就不提了：

您說，如果免子不只生一隻小免子的話怎麼辦？像這種問題，我們可以將費氏數列加以擴充，稱之為擴充費氏數列：

fn = X * fn-1 + Y * fn-2　　 if n > 1
fn = 1　　　　　　　　　 if n = 0, 1

當X、Y等於1時，自然就是一般的費氏數列了。

想瞭解費氏數列與自然界神奇的關係，可以造訪這個網頁。

實作

#include <stdio.h> 
#include <stdlib.h> 

#define N 20 

int main(void) { 
    int Fib[N] = {0}; 
    int i; 

    Fib[0] = 0; 
    Fib[1] = 1; 

    for(i = 2; i < N; i++) 
        Fib[i] = Fib[i-1] + Fib[i-2]; 

    for(i = 0; i < N; i++) 
        printf("%d ", Fib[i]); 
    printf("\n"); 

    return 0; 
}

Java

public class Fibonacci {
    public static void main(String[] args) {
        int[] fib = new int[20]; 

        fib[0] = 0; 
        fib[1] = 1; 

        for(int i = 2; i < fib.length; i++) 
            fib[i] = fib[i-1] + fib[i-2]; 

        for(int i = 0; i < fib.length; i++) 
            System.out.print(fib[i] + " "); 
        System.out.println();
    }
}