• 在面试中咱们可能会遇到青蛙跳的问题：一只青蛙一次能够跳上一级台阶，或者跳上二级台阶。那么如果总共有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;}