首页 > web前端 > js教程 > 正文

js实现斐波那契数列

黄舟
发布: 2017-02-10 09:49:18
原创
2224 人浏览过

输入n,求Fibonacci数列的第n项

function fibonacci(n) {
  if (n < 0) {
throw new Error('输入的数字不能小于0');
  }
  if (n == 0) {
return 0;
  } 
  if (n == 1) {
return 1;
  }
  return fibonacci(n-1) + fibonacci(n-2);
}
登录后复制

这其实并不是很好的方法
比如求fibonacci(10)的时候,分解成了fibonacci(9)和fibonacci(8),但是fibonacci(9)又会分解成fibonacci(8)和fibonacci(7),其中就重复计算了fibonacci(8),以此类推,重复的计算非常多,最简单的办法就是记录下已经计算过的值:

function fibonacci2(n) {
  if (n < 0) throw new Error('输入的数字不能小于0');
  let arr = [0, 1];
  function calc(n) {
  if (n<2) {
      return arr[n];
  }
  if (arr[n] != undefined) {
      return arr[n];
  }
  let data = calc(n-1) + calc(n-2);
  arr[n] = data;
  return data;
  }
  return calc(n);
}

function fibonacciFunc() {
  let arr = [0, 1];
  function calc(n) {
    if (n < 0) throw new Error('输入的数字不能小于0');
    if (n<2) return arr[n];
    if (arr[n] != undefined) {
      return arr[n];
    }
    let data = calc(n-1) + calc(n-2);
    arr[n] = data;
    return data;
  }

  return calc;
}   
let fibonacci3 = fibonacciFunc();
登录后复制

上面两种方法用到了闭包

fibonacci3的坏处是只要fibonacci3不被释放, 内存中arr数组会一直存在。尤其当计算过比较大的数字后;但是当需要大量的计算fibonacci数时,fibonacci3会比较有优势,但是要记住最后释放fibonacci3,即:

fibonacci3 = null;
登录后复制

还有一种方法就是不用递归,直接循环

function fibonacci4 (n) {
  if (n < 0) throw new Error('输入的数字不能小于0');
  let dataMinusTwo= 0,
    dataMinusOne = 1,
    data;
  if (n == 0) return dataMinusTwo;
  if (n == 1) return dataMinusOne;
  for (var i=2;i<=n;i++) {
    data = dataMinusOne + dataMinusTwo;

    dataMinusTwo = dataMinusOne;
    dataMinusOne = data;
  }
  return data;
}
登录后复制

以上就是js实现斐波那契数列的内容,更多相关内容请关注PHP中文网(www.php.cn)!


相关标签:
来源:php.cn
本站声明
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn
热门教程
更多>
最新下载
更多>
网站特效
网站源码
网站素材
前端模板
关于我们 免责声明 Sitemap
PHP中文网:公益在线PHP培训,帮助PHP学习者快速成长!