前端算法之斐波那契数列初探

在codepen社区看到了这个demo

于是浅显的学习了下斐波那契:

何谓斐波那契:

斐波那契的解释中有这样一段话:是这样一个数列:1、1、2、3、5、8、13、21、34、……在数学上,斐波纳契数列以如下被以递归的方法定义:F(0)=1,F(1)=1, F(n)=F(n-1)+F(n-2)(n>=2,n∈N*)
2gDJd.png

n = 1,2 时,fibonacci(n) = 1
n > 2 时,fibonacci(n) = fibonacci(n-2) + fibonacci(n-1)

基础的斐波那契写法:
function fibonacci(n){
	if(n <= 0){
		return 0;
	}
	if(n == 1){
		return 1;
	}
	return fibonacci(n - 1) + fibonacci(n - 2 )
}
console.log(fibonacci(6))

但是这种写法运行起来存在大量重复计算,计算时间特别长。而且很容易因此造成浏览器卡死。 (亲测)
2g0fJ.png

解决方法一 https://21cm.github.io/2018/05/27/fibonacci/
function fibonacci(n) {
    if (n <= 0) {
        return 0;
    }
    if (n == 1) {
        return 1;
    }
    var n1 = 0, n2 = 1, result;
    for (var i = 2; i <= n; i++) {
        result = n1 + n2;
        n1 = n2;
        n2 = result;
    }
    return result;
   }
console.log(fibonacci(200));

2gdJ6.md.png

三元表达式:

function fibonacci(n) { 
    return n < 2 ? n : (fibonacci(n - 1) + fibonacci(n - 2)); 
}
fibonacci(200)

存在问题是计算时间过长
2gJf2.png

解决方法二 :迭代法
function fibonacci(n) {
  if(n>1){
  var a=1,b=1;
  n--;
  a = n & 1; //位运算
  n /= 2;
  while (n-->0) {  
       a += b;  
       b += a;  
    } 
    return b;  
    }  
    return n;  
  }
console.log(fibonacci(100));

这种方法是从兽哥哪里get到的,可以计算出无穷大的值。
2gyIS.png

js斐波那契数列求和

递归算法 :

function fibonacci(n) {
 if (n < 2) {
   return n;
 }
 else {
   return fibonacci(n-1) + fibonacci(n-2);
 }
}
console.log(fibonacci(10));//55

迭代法

function fibonacci(n){
 var last=1;
 var nextlast=1;
 var result=1;
 for(var i=2;i<n;++i){
   result=last+nextlast;
   nextlast=last;
   last=result;
 }
 return result;
}
console.log(fibonacci(10));//55

相关链接:
斐波那契螺旋
JS输出斐波那契数列
斐波那契数列js解法之性能对比