大家都知道斐波那契数列,现在要求输入一个整数n,请你输出斐波那契数列的第n项(从0开始,第0项为0)。
n<=39
何为斐波那契额数列呢??
例如:0 1 1 2 3 5 8 13 说的通透些就是前两个数的和是后面那个数。
通项公式:F(n) = F(n-1)+F(n-2)
大家结合这张图和通式理一下思路,相信其实不难。就是一个简单的递归调用,最后调用到F(0)和F(1)截止。
代码如下所示:
function test(n){
if(n==0){
return 0;
}else if(n==1){
return 1;
}else if(n>1){
var number = test(n-1)+test(n-2);
return number ;
}else{
return null;
}
}
这道题还没有完。因为由此可以看到这个算法的复杂度是2的N次方。(因为看图他每层都是以2的次幂进行增长的)所有他的时间复杂度极高。这个算法如果数极大的话是不合理的。
那么如何简化算法呢?
提示:倒推运算,利用已得的结论去运算下一次的方法。
其实也很简单,就是利用比如前两个数相加的和等于第三个数,第四个数等于 第三个数据(也就是前两个数的和)加上前两个数中最大的那一个。按照此规律,即可优化本题算法。
function testnew(n){
var a = 1;
var b = 0;
var num = null;
if(n>1){
for(let i=0;i<n-1;i++){
num = a+b;
b=a;
a= num;
}
return num;
}
}