斐波那契(Fibonacci)数列

递归算法求斐波那契数列的第n项

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

有没有更好的算法？

递推关系式的优化：

用一个数组存储所有已经计算过的项

求解通项公式：

公式引入无理数，不能保证结果的精度

分治

class Matrix; 

Matrix MatrixPow( const Matrix& m, int n)
{
    Matrix result = Matrix::Identity;
    Matrix tmp = m;
    for(; n; n >>= 1)
    {
        if(n & 1)
            result  *= tmp;
            tmp *= tmp;
    }
}

int Fibonacci (int n){
    Matrix an = MatrixPow(A, n-1);
    return F1 * an(0,0) + F0 * an(1,0);
}