数据结构与算法（递归与循环） --javascript语言描述

斐波那契数列

大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项。
n<=39

递归解法：

function Fibonacci(n)
  {
    if(n<=0) {
      return 0;
    }
    if(n==1) {
      return 1;
    }
    return Fibonacci(n-1) + Fibonacci(n-2);
  }
  console.log(Fibonacci(10));

由于使用递归时，其执行步骤是：要得到后一个数之前必须先计算出之前的两个数，即在每个递归调用时都会触发另外两个递归调用，例如：要得到F(10)之前得先得到F(9)、F(8)，那么得到F(9)之前得先得到F(8)、F(7)......如此递归下去。这样的计算是以 2 的次方在增长的。除此之外，我们也可以看到，F(8)和F(7)的值都被多次计算，如果递归的深度越深，那么F(8)和F(7)的值会被计算更多次，但是这样计算的结果都是一样的，除了其中之一外，其余的都是浪费，可想而知，这样的开销是非常恐怖的！

所以，如果在时间复杂度和空间复杂度都有要求的话，我们可以用以下循环算法来实现：

function Fibonacci(n)
  {
    if (n == 0 || n == 1) {
        return n;
    }
    let num1 = 0;
    let num2 = 1;
    let numN = 0;
    for (let i = 2; i <= n; i++) {
      numN = num1 + num2;
      num1 = num2;
      num2 =  numN;
    }
    return numN;
  }
  console.log(Fibonacci(10));

时间复杂度为O(N)。

青蛙跳台阶问题

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

思路:登上n阶台阶问题可以转换成登上n-2个台阶方式加上登上n-1个台阶加上登上n-3个台阶....加到登上1个台阶方式之和再加上一次登上总台阶和的问题
即有公式 f(n)=f(n-1)+f(n-2) +f(n-3)+......+f(3)+f(2)+(1)+1 。

我们不难看出这实际上就是斐波那契数列了。

function jumpFloor(n)
  {
    if (n == 0 || n == 1) {
      return n;
    }
    if(n == 2) {
      return 2;
    }
    let num1 = 1;
    let num2 = 2;
    let numN = 0;
    for (let i = 3; i <= n; i++) {
      numN = num1 + num2;
      num1 = num2;
      num2 =  numN;
    }
    return numN;
  }
  console.log(jumpFloor(10))

变态跳台阶问题

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

用Fib(n)表示跳上n阶台阶的跳法数。
当n = 1 时， 只有一种跳法，即1阶跳：Fib(1) = 1;
当n = 2 时， 有两种跳的方式，一阶跳和二阶跳：Fib(2) = 2;
到这里为止，和普通跳台阶是一样的。
当n = 3 时，有三种跳的方式，第一次跳出一阶后，对应Fib(3-1)种跳法； 第一次跳出二阶后，对应Fib(3-2)种跳法；第一次跳出三阶后，只有这一种跳法。Fib(3) = Fib(2) + Fib(1)+ 1 = Fib(2) + Fib(1) + Fib(0) = 4;
当n = 4时，有四种方式：第一次跳出一阶，对应Fib(4-1)种跳法；第一次跳出二阶，对应Fib(4-2)种跳法；第一次跳出三阶，对应Fib(4-3)种跳法；第一次跳出四阶，只有这一种跳法。所以，Fib(4) = Fib(4-1) + Fib(4-2) + Fib(4-3) + 1 = Fib(4-1) + Fib(4-2) + Fib(4-3) + Fib(4-4) 种跳法。
当n = n 时，共有n种跳的方式，第一次跳出一阶后，后面还有Fib(n-1)中跳法； 第一次跳出二阶后，后面还有Fib(n-2)中跳法..........................第一次跳出n阶后，后面还有 Fib(n-n)中跳法。Fib(n) = Fib(n-1)+Fib(n-2)+Fib(n-3)+..........+Fib(n-n) = Fib(0)+Fib(1)+Fib(2)+.......+Fib(n-1)。
通过上述分析，我们就得到了通项公式：

Fib(n) =  Fib(0)+Fib(1)+Fib(2)+.......+ Fib(n-2) + Fib(n-1)

因此，有

Fib(n-1)=Fib(0)+Fib(1)+Fib(2)+.......+Fib(n-2)

两式相减得：

Fib(n)-Fib(n-1) = Fib(n-1)         =====》  Fib(n) = 2*Fib(n-1)     n >= 3

这就是我们需要的递推公式：Fib(n) = 2*Fib(n-1) n >= 3

function jumpFloorII(n)
  {
    if (n == 0 || n == 1) {
      return n;
    }
    if(n == 2) {
      return 2;
    }
    let num2 = 2;
    let numN = 0;
    for (let i = 3; i <= n; i++) {
      numN =  2 * num2;
      num2 = numN;
    }
    return numN;
  }
  console.log(jumpFloorII(10))