斐波那契数列

题目：
    You are climbing a stair case. It takes n steps to reach to the top.
    Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

解析：
    上面的题目其实很简单，首先推出递推公式为：
    
    这篇文章就是想总结下求解斐波那契数列的方法，有自己知道的，也有参考的其他的。主要目的还是学习。

解法一：递归
    相信遇到这个问题时，很多人都会首先想到的是递归方法，因为我们有递归方程，也有结束条件，很顺其自然的想到该方法。

//递归方法
int Fibonacci(int n)
{
    if(n == 0)
    {
        return 0;
    }
    else if(n == 1)
    {
        return 1;
    }
    else
    {
        return Fibonacci(n - 1) + Fibonacci(n - 2);
    }
}

    这种方法当n值比较小的时候，时间效率还行，但是，当n值很大时，效率非常低。

解法二：迭代
    根据解法一的递归，可以将其改写成迭代的方法。

//迭代方法
int Fibonacci(int n)
{
    int left = 1;    //n = 1
    int right = 0; //n = 0
    int sum = 0;

    if(n == 0)
    {
        return right;
    }
    if(n == 1)
    {
        return left;
    }

    for(int i = 2; i <= n; i++)
    {
        sum = left + right;
        right = left;
        left = sum;
    }

    return left;
}

解法三：求解递推公式
    如果我们知道一个数列的递推公式，使用公式来计算会更加容易。能不能把这个函数的递归公式求解出来？
    
    通过公式，我们可以在O(1)的时间内得到F(n)。但公式中引入了无理数，所以不能保证结果的精度。

解法四：分治策略
    注意到斐波那契数列是二阶递推数列，所以存在一个2*2的矩阵A，使得：
    
    我们注意到：
    
    
    主要代码如下所示。

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;
    }

    return result;
}

int Fibonacci(int n)
{
    Matrix an = MatrixPow(A, n - 1);    //A的值就是上面求解出来的
    return F1 * an(0,0) + F0(1, 0));
}

    上面的公式太难打了，所以，最后截了两张编程之美上的图。


    引自：解法三和解法四出自《编程之美》