編程之美之斐波那契數列

【背景】

【思路1-遞歸】

int Fibonacci(int n){
        if(n <= 2){
            return n;
        }
        return Fibonacci(n - 1) + Fibonacci(n - 2);
    }

進一步優化：

當n增大到一定數值，Fibonacci數列值會溢出，並且花費時間很長。

long long Fibonacci(int n){
        if(n <= 2){
            return n;
        }
        return Fibonacci(n - 1) + Fibonacci(n - 2);
    }

【思路2-遞推關係式的優化】

long long Fibonacci(int n){
        long long* Fibonacci = (long long*)malloc(sizeof(long long)*(n+1));
        Fibonacci[0] = 0;
        Fibonacci[1] = 1;
        for(int i = 2;i <= n;i++){
            Fibonacci[i] = Fibonacci[i-1] + Fibonacci[i-2];
        }
        return Fibonacci[n];
    }

該思路的另一種實現方法：

long long  Fibonacci(int n){
        int i;
        long long fibonacciA = 0;
        long long fibonacciB = 1;
        long long fibonacciC;
        if(n == 0){
            return 0;
        }
        else if(n == 1){
            return 1;
        }
        for(i = 2;i <= n;i++){
            fibonacciC = fibonacciA + fibonacciB;
            fibonacciA = fibonacciB;
            fibonacciB = fibonacciC;
        }
        return fibonacciC;
    }

【思路3-求解通項公式】

int Fibonacci(int n) {
        double s = sqrt(5);
        // floor 返回小於或者等於指定表達式的最大整數
        return floor((pow((1+s)/2, n) - pow((1-s)/2, n))/s + 0.5);
    }

當n增大到一定數值，Fibonacci數列值會溢出。因為floor返回小於或者等於指定表達式的最大整數

【思路4-分支策略】

#include <iostream>
#include <malloc.h>
#include <stdio.h>
using namespace std;
//矩陣乘法
void MatrixMulti(long long matrix[2][2],long long matrix2[2][2]){
    long long a = matrix[0][0] * matrix2[0][0] +  matrix[0][1] * matrix2[1][0];
    long long b = matrix[0][0] * matrix2[0][1] +  matrix[0][1] * matrix2[1][1];
    long long c = matrix[1][0] * matrix2[0][0] +  matrix[1][1] * matrix2[1][0];
    long long d = matrix[1][0] * matrix2[0][1] +  matrix[1][1] * matrix2[1][1];
    matrix[0][0] = a;
    matrix[0][1] = b;
    matrix[1][0] = c;
    matrix[1][1] = d;
}
//Fibonacci數列
long long Fibonacci(int value){
    if(value == 0){
        return 0;
    }
    long long A[2][2] = {1,1,1,0};
    //初試為單位矩陣
    long long Matrix[2][2] = {1,0,1,0};
    int n = value - 1;
    for(; n ;n >>= 1){
        //奇偶
        if(n&1){
            MatrixMulti(Matrix,A);
        }//if
        MatrixMulti(A,A);
    }//for
    return Matrix[0][0];
}

int main() {
    int i,n,height;
    while(scanf("%d",&n) != EOF){
        long long result;
        for(i = 0;i <= n;i++){
            result = Fibonacci(i);
            printf("%lld\n",result);
        }//for
    }//while
    return 0;
}

該思路另一種解析：