设n是正整数，a=(1+sqrt(5)/2,b=(1-sqrt(5)/2
那么第n个斐波那契数fn就等于：
fn = (1/sqrt(5)) * ( pow(a,n) - pow(b,n) )

C++ 代码

class Solution {
public:
    int Fibonacci(int n) {
        double N=1/sqrt(5);
        double a=(1+sqrt(5))/2;
        double b=(1-sqrt(5))/2;
        return N*(pow(a,n)-pow(b,n));
    }
};

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla