斐波那契数列 青蛙跳台阶

题目一：求斐波那契数列的第n项。
写一个函数，输入n，求斐波那契（Fibonacci）数列的第n 项。斐波那契数列的定义如下：

image.png

1. 递归。时间效率很低，不推荐。

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

2. 循环。把递归的算法用循环实现，极大地提高了时间效率。时间复杂度是O(n)，推荐。

long long Fibonacci(unsigned int n) {
    int result[2] = {0, 1};
    if (n < 2) {
        return result[n];
    }
    
    long long fibNMinusOne = 1;
    long long fibNMinusTwo = 0;
    long long fibN = 0;
    
    for (unsigned int i = 2; i <= n; ++i) {
        fibN = fibNMinusOne + fibNMinusTwo;
        fibNMinusTwo = fibNMinusOne;
        fibNMinusOne = fibN;
    }
    
    return fibN;
}

3. 基于矩阵乘法

struct Matrix2By2
{
    Matrix2By2
    (
     long long m00 = 0,
     long long m01 = 0,
     long long m10 = 0,
     long long m11 = 0
     )
    :m_00(m00), m_01(m01), m_10(m10), m_11(m11)
    {
    }
    
    long long m_00;
    long long m_01;
    long long m_10;
    long long m_11;
};

Matrix2By2 MatrixMultiply
 (
  const Matrix2By2& matrix1,
  const Matrix2By2& matrix2
  )
{
    return Matrix2By2(
                      matrix1.m_00 * matrix2.m_00 + matrix1.m_01 * matrix2.m_10,
                      matrix1.m_00 * matrix2.m_01 + matrix1.m_01 * matrix2.m_11,
                      matrix1.m_10 * matrix2.m_00 + matrix1.m_11 * matrix2.m_10,
                      matrix1.m_10 * matrix2.m_01 + matrix1.m_11 * matrix2.m_11);
}

Matrix2By2 MatrixPower(unsigned int n)
{
    assert(n > 0);
    
    Matrix2By2 matrix;
    if(n == 1)
    {
        matrix = Matrix2By2(1, 1, 1, 0);
    }
    else if(n % 2 == 0)
    {
        matrix = MatrixPower(n / 2);
        matrix = MatrixMultiply(matrix, matrix);
    }
    else if(n % 2 == 1)
    {
        matrix = MatrixPower((n - 1) / 2);
        matrix = MatrixMultiply(matrix, matrix);
        matrix = MatrixMultiply(matrix, Matrix2By2(1, 1, 1, 0));
    }
    
    return matrix;
}

long long Fibonacci_Solution3(unsigned int n)
{
    int result[2] = {0, 1};
    if(n < 2)
        return result[n];
    
    Matrix2By2 PowerNMinus2 = MatrixPower(n - 1);
    return PowerNMinus2.m_00;
}

题目二：青蛙跳台阶问题。
一只青蛙一次可以跳上 1级台阶，也可以跳上2级台阶。求该青蛙跳上一个n级的台阶总共有多少种跳法。

image.png

long long Fibonacci(unsigned int n) {
    if (n <= 2) {
        return n;
    }
    
    long long fibNMinusOne = 2;
    long long fibNMinusTwo = 1;
    long long fibN = 0;
    
    for (unsigned int i = 3; i <= n; ++i) {
        fibN = fibNMinusOne + fibNMinusTwo;
        fibNMinusTwo = fibNMinusOne;
        fibNMinusOne = fibN;
    }
    
    return fibN;
}

摘抄资料：《剑指offer》