《剑指offer》第十题：斐波那契数列

// 面试题10：斐波那契数列
// 题目：写一个函数，输入n，求斐波那契（Fibonacci）数列的第n项。

#include <cstdio>

// ====================方法1：递归====================
//存在函数调用导致栈溢出的可能, 效率低, 时间复杂度指数递增
long long Fibonacci_Solution1(unsigned int n)
{
    if (n <= 0)
        return 0;
    if (n == 1)
        return 1;

    return Fibonacci_Solution1(n - 1) + Fibonacci_Solution1(n - 2);
}

// ====================方法2：循环====================
//时间复杂度O(n)
long long Fibonacci_Solution2(unsigned 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：基于矩阵乘法====================
//时间复杂度O(logn)
#include <cassert>

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) //n为偶数, 递归求 a^(n/2), 然后平方
    {
        matrix = MatrixPower(n / 2);
        matrix = MatrixMultiply(matrix, matrix);
    }
    else if (n % 2 == 1) //n为奇数, 递归求 a^((n-1)/2), 平方后乘a
    {
        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;
}

// ====================测试代码====================
void Test(int n, int expected)
{
    if (Fibonacci_Solution1(n) == expected)
        printf("Test for %d in solution1 passed.
", n);
    else
        printf("Test for %d in solution1 failed.
", n);

    if (Fibonacci_Solution2(n) == expected)
        printf("Test for %d in solution2 passed.
", n);
    else
        printf("Test for %d in solution2 failed.
", n);

    if (Fibonacci_Solution3(n) == expected)
        printf("Test for %d in solution3 passed.
", n);
    else
        printf("Test for %d in solution3 failed.
", n);
}

int main(int argc, char* argv[])
{
    Test(0, 0);
    Test(1, 1);
    Test(2, 1);
    Test(3, 2);
    Test(4, 3);
    Test(5, 5);
    Test(6, 8);
    Test(7, 13);
    Test(8, 21);
    Test(9, 34);
    Test(10, 55);

    Test(40, 102334155);

    return 0;
}

分析：分解问题为多个子问题，自下而上解决。

class Solution {
public:
    int Fibonacci(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 (int i = 2; i <= n; ++i)
        {
            fibN = fibNMinusOne + fibNMinusTwo;
            
            fibNMinusTwo = fibNMinusOne;
            fibNMinusOne = fibN;
        }
        return fibN;
    }
};

class Solution {
public:
    int jumpFloor(int number) {
        
        int result[3] = {0, 1, 2};
        if (number < 3)
            return result[number];
        
        long long fibNMinusOne = 2;
        long long fibNMinusTwo = 1;
        long long fibN = 0;
        for (int i = 3; i <= number; ++i)
        {
            fibN = fibNMinusOne + fibNMinusTwo;
            
            fibNMinusTwo = fibNMinusOne;
            fibNMinusOne = fibN;
        }
        return fibN;javascript:void(0);
    }
};

class Solution {
public:
    int jumpFloorII(int number) {
        
        //方法1：f(n) = 2^(n - 1), n >= 0
        //写法1：pow()函数
        if (number <= 0)
            return -1;
        else
        {
            int n = pow(2, number - 1);
            return n;
        }
        
        //写法2：位运算
        //if (number <= 0)
        //    return -1;
        //else
        //{
        //    int a = 1;
        //    return a << (number-1);
        //}
    }
};

class Solution {
public:
    int jumpFloorII(int number) {
        
        //方法2: f(n) = 1, n = 0
        //             1, n = 1
        //    2 f(n - 1), n >= 2
        
        if (number <= 0)
            return -1;
        else if (number == 1)
            return 1;
        else
            return 2 * jumpFloorII(number - 1);
    }
};