剑指offer笔记面试题10----斐波那契数列

佚名 5年前 (2019-10-17) 算法 898人围观抢沙发百度已收录

题目：求斐波那契数列的第n项。写一个函数，输入n，求斐波那契数列的第n项。斐波那契数列的定义如下：f(0) = 0, f(1) = 1,f(n) = f(n - 1) + f(n - 2)。

测试用例：

功能测试（如输入3、5、10等）。
边界值测试（如输入0、1、2）。
性能测试（输入较大的数字，如40、50、100等）。

测试代码：

void test(int n, int expected){
    if(fibonacci_solution1(n) == expected)
        printf("test for %d in solution1 passed.\n", n);
    else
        printf("test for %d in solution1 failed.\n", n);
    if(fibonacci_solution2(n) == expected)
        printf("test for %d in solution2 passed.\n", n);
    else
        printf("test for %d in solution2 failed.\n", n);
    if(fibonacci_solution3(n) == expected)
        printf("test for %d in solution3 passed.\n", n);
    else
        printf("test for %d in solution3 failed.\n", n);
}

本题考点：

考查应聘者对递归、循环的理解及编码能力。
考查应聘者对时间复杂度的分析能力。
如果面试官采用的是青蛙跳台阶的问题，那么同时还在考查应聘者的数学建模能力。

代码实现：

#include <cstdio>
#include <cassert>

//=================方法一：递归==================
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);
} 

//=================方法二：循环==================
long long fibonacci_solution2(unsigned n){
    int result[2] = {0, 1};
    if(n < 2)
        return result[n];
    long long fibMinusOne = 1;
    long long fibMinusTwo = 0;
    long long fibN = 0;
    for(unsigned int i = 2; i <= n; ++i){
        fibN = fibMinusOne + fibMinusTwo;
        fibMinusTwo = fibMinusOne;
        fibMinusOne = fibN;
    }
    return fibN;
} 

//=================方法三：基于矩阵乘法============= 
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, m_01, m_10, 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;
}
int main(){
    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);
    test(100, 3736710778780434371);
    return 0;
}