JavaScript实现青蛙跳台阶问题（斐波那契数列）

红太狼 2022-05-24 07:26 186阅读 0赞

**问题一：**一只青蛙一次可以跳上一阶台阶，也可以跳上二阶台阶，请这只可怜的青蛙跳上N阶台阶有几种方法？

分析：当N=1时有一种跳法，当N=2时有两种跳法，当N=3时有三种跳法，当N=4有五种跳法，当N=5时有八种跳法，当N=6时有十三种跳法....... 这个规律符合斐波那契数列：

![20180523105137756][]

关于斐波那契数列的原理不多说，网上有很多，下面是 js实现跳青蛙问题的代码：

function jumpFloor(n) {
    
            if(n<=0)return 0;
            if(n == 1) return 1;
            if(n==2) return 2;
            return jumpFloor(n-1) + jumpFloor(n-2)
      }
    
      console.log(jumpFloor(30)) // 输出 1346269

上面用递归实现的效率很低，当 N=50 的时候在chrome里就跑不动了，chrome会出现卡死。下面用迭代的方式效率会高出很多

function jumpFloor2(n) {
            var target = 0, number1 = 1, number2 = 2;
    
            if(n<=0)return 0;
            if(n == 1) return 1;
            if(n==2) return 2;
            for(var i=3;i<=n;++i) {
                target = number1 + number2;
                number1 = number2;
                number2 = target;
            }
            return target;
        }
    
        console.log(jumpFloor2(100)) // 输出 573147844013817200000
        console.log(jumpFloor2(1000)) // 输出 7.0330367711422765e+208
        console.log(jumpFloor2(10000)) // 输出 Infinity

通过上面的输出可以看到当N=10000时就就已经越界了，会输出 Infinity。但浏览器不会卡死，值还是会瞬间输出

**问题二：假设一只青蛙一次可以跳一个台阶，一次也可以跳N个台阶，请问**

[20180523105137756]: /images/20220524/32f9cc2dd8c4453685ce746d16daf472.png