题目描述
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)用移位操作进行效率更高