编程之美之斐波那契数列

【背景】

【思路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;
}

该思路另一种解析：

【相关题目】

剑指Offer之斐波那契数列

剑指Offer之跳台阶

剑指Offer之矩形覆盖

LeetCode之Climbing Stairs