算法:变态跳台阶的js的实现

时间:2022-09-21 19:18:58

题目描述

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

也许这个题你没见过,但是下边这个你应该知道:

2.一只青蛙一次可以跳上1级台阶,也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法(先后次序不同算不同的结果)。

关于第二道题其实就是斐波那契数列:青蛙的第一跳有两种情况,跳一阶和跳二阶。如果跳一阶,则剩下n-1阶就是f(n-1)中跳法;如果挑两阶,则剩下n-2阶就是f(n-2)种情况。所以总情况就是f(n)=f(n-1)+f(n-2);这里不推荐递归,建议用循环或者数组

第二道题解法:

function jumpFloor(number)
{
    if(number===0){
        return 0;
    }
    else if(number===1){
        return 1;
    }
    else if(number===2){
        return 2;
    }
    else{
        var pre = 1;
        var cur = 2;
        for(var i = 2;i<number;i++){
            cur+=pre;
            pre = cur-pre;
        }
        return cur;
    }
}

那第一道呢?两道题很像,思路也有些相似

/*因为n级台阶,第一步有n种跳法:跳1级、跳2级、到跳n级
跳1级,剩下n-1级,则剩下跳法是f(n-1)
跳2级,剩下n-2级,则剩下跳法是f(n-2)
所以f(n)=f(n-1)+f(n-2)+...+f(1)
那么f(n-1)=f(n-2)+f(n-3)+...+f(1)

然后就可以把划线部分换成f(n-1)
所以f(n)=2*f(n-1)*/

所以第二道解法:
function jumpFloorII(number){
    return 1<<(number-1);
}

就这么一行代码,2^(n-1)用移位操作进行效率更高