关于面试:青蛙跳问题为什么是斐波那契数列

• 在面试中咱们可能会遇到青蛙跳的问题：一只青蛙一次能够跳上一级台阶，或者跳上二级台阶。那么如果总共有 N 级台阶，问这只青蛙总共有多少种跳法？
• 首先，咱们思考最简略的状况，如果只有一级台阶，那显然青蛙只有一种跳法。如果只有二级台阶，那么青蛙就有两种跳法，一种是每次跳一级，总共跳二次，另一种就是间接跳二级。
• 接下来，再来看 N 级的（N 大于 2）的状况。咱们先把 N 级台阶的跳法看做一个 N 的函数，记为 f(N)。思考 N >2 时，第一次跳就有两种跳法，一种是第一次只跳一级，此时跳法数就是前面剩下的 N - 1 级台阶的跳法数，即为 f(N-1)；另一种则是第一次跳二级，那么此时的跳法数就是前面剩下的 N - 2 级台阶的跳法数，即为 f(N-2)。所以，N 级台阶的跳法总数就是 f(N)=f(N-1)+f(N-2)。显然这就是一个 N >0 的斐波那契数列。
• C++ 实现递归解法

#include<iostream> 
using namespace std; 

long long RecursiveFibonacci(unsigned int n)
{if(n == 1 || n == 2)
        return n;

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

int main() 
{cout << "RecursiveFibonacci(1)=" << RecursiveFibonacci(1) << endl;
    cout << "RecursiveFibonacci(2)=" << RecursiveFibonacci(2) << endl;
    cout << "RecursiveFibonacci(3)=" << RecursiveFibonacci(3) << endl;
    cout << "RecursiveFibonacci(5)=" << RecursiveFibonacci(5) << endl;
    cout << "RecursiveFibonacci(10)=" << RecursiveFibonacci(10) << endl;
    cout << "RecursiveFibonacci(50)=" << RecursiveFibonacci(50) << endl;
    cout << "RecursiveFibonacci(100)=" << RecursiveFibonacci(100) << endl;
}

• 很显然，递归实现效率是非常低的，其工夫复杂度是 n 的指数级。因为递归存在着大量的反复计算，大家也能够本人跑代码试试，递归去计算 n =50 就十分慢了。
• 所以，优化思路就是从前往后计算，先依据 f(1) 和 f(2) 算 f(3)，在依据 f(2) 和 f(3) 算 f(4)，以此类推算出 f(N)。其工夫复杂度是 O(n)。
• C++ 实现非递归解法

#include<iostream> 
using namespace std; 

long long NonRecursiveFibonacci(unsigned int n)
{if(n == 1 || n == 2)
        return n;

    long long n1 = 1;
    long long n2 = 2;
    long long result = 0;
    for (unsigned int i = 3; i <= n; i++)
    {   
        result = n1 + n2;
        n1 = n2;
        n2 = result;
    }
    return result;
}

int main() 
{cout << "NonRecursiveFibonacci(1)=" << NonRecursiveFibonacci(1) << endl;
    cout << "NonRecursiveFibonacci(2)=" << NonRecursiveFibonacci(2) << endl;
    cout << "NonRecursiveFibonacci(3)=" << NonRecursiveFibonacci(3) << endl;
    cout << "NonRecursiveFibonacci(5)=" << NonRecursiveFibonacci(5) << endl;
    cout << "NonRecursiveFibonacci(10)=" << NonRecursiveFibonacci(10) << endl;
    cout << "NonRecursiveFibonacci(50)=" << NonRecursiveFibonacci(50) << endl;
    cout << "NonRecursiveFibonacci(100)=" << NonRecursiveFibonacci(100) << endl;
}