JavaScript解斐波那契(Fibonacci)数列的实用解法

zhongmeizhi 发布于2019-08-20 14:50 / 1444人阅读

摘要：下面是一个可以处理很多类型递归函数的函数其中第一个参数为原有函数，第二个参数为缓存对象，是可选参数因为并不是所有递归函数都包含初始信息。首先将缓存对象的类型从数组转换为对象，这样就可以适用于那些不是返回整数的递归函数。

JavaScript解斐波那契(Fibonacci)数列的实用解法

我们经常会在面试题中看到如下题目：输入n，求斐波那契数列的第n项，斐波那契数列的定义如下：

F(0)=0, F(1)=1, n>1时，F(n)=F(n-1)+F(n-2)。

一种效率很低的解法

当遇到这种函数时，我们很容易的想到递归函数，解法如下：

function fibonacci(n) {
  if(n <= 1) {return n};
  else {
    return fibonacci(n-1) + fibonacci(n-2);
  }
}

这个方法确实能解决这道题目，但递归的解法并不适合这道题目，用递归解法将会有很严重的效率问题，我们以f(10)为例分析一下原因：

由上述图片我们可以看出，要想求得f(10),需要先求得f(8)和f(9)，同样，要想求得f(9)，也要求得f(7)和f(8)。不难看出，树结构当中很多结点是重复的，而且重复的节点数会随着n的增大而急剧增大，这意味着计算量将会随着n的增大而急剧增大。事实上，递归所需的时间复杂度是以n的指数方式递增的，由此我们可以试试当n为100时需要耗费的时间会有多长，这是难以接受的。

动态规划解法

造成效率低下的主要原因就是重复计算太多，我们只要想个办法避免重复计算即可，这里有个很容易的算法：

var fib = 0,
    fib1 = 0,
    fib2 = 1;
function fibonacci(n) {
  if(n <= 1){
    return n;
  } else {
    for(var i =1; i < n; ++i) {
      fib = fib1 + fib2;
      fib1 = fib2;
      fib2 = fib;
    }
    return fib;
  }
}

理解这种方法很简单，我们只是从下往上计算，首先根据f(0)和f(1)算出f(2),再根据f(1)和f(2)算出f(3)，依次类推我们就可以算出第n项了，而这种算法的时间复杂度仅为O(n)，比递归函数的写法效率要大大增强。

Memoization

我们还可以将已经得到的数列中间项保存起来，若下次计算的时候我们先查找一下，若前面已经出现过则不用再重复计算了。

在JavaScript中，递归是拖慢脚本运行速度的罪魁祸首之一，太多的递归会让浏览器越来越慢乃至奔溃，这是需要我们解决的性能问题。

我们可以使用memoization技术来替代函数中太多的递归调用，memoization是一种可以缓存之前运算结果的一种技术，当在执行运算操作时，我们先从缓存对象中读取看看是否有我们需要读取的值，若有则直接从缓存对象中读取，若没有则进行计算，并将缓存结果存入缓存对象中。

下面是一个可以处理很多类型递归函数的memoizer()函数：

`function memoizer(fun, cache) {
 cache = cache || {};
 var shell = function(arg) {
   if( ! (arg in cache)) {
     cache[arg] = fun(shell, arg);
   }
   return cache[arg];
 } ;
 return shell;
}`

其中第一个参数为原有函数，第二个参数为缓存对象，是可选参数（因为并不是所有递归函数都包含初始信息）。首先将缓存对象的类型从数组转换为对象，这样就可以适用于那些不是返回整数的递归函数。使用in操作符判断参数是否已经包含在了缓存里，会比测试cache[arg]更安全些，因为undefined是一个有效的返回值(这里其实我也不太明白，弄清楚后会补上)。

接下来我们就可以调用memoizer来解这个这个问题:

var fibonacci = memoizer(function(fibon, n) {
  return fibon(n - 1) + fibon(n - 2);
}, {"0" : 0, "1" : 1});

这时我们就可以通过fibonacci(100)来执行函数，同样运用此种方法复杂度为O(n)，大大优化了执行效率。

后记

个人更喜欢memoizer的解法，因为我觉得这种解法更加的优雅，运用了JavaScript函数式编程的特性，非常值得借鉴。

在我看来，函数的执行效率很重要，勿以事小而不为，平时多积累一些优秀的解法，从平时的小知识点出发，慢慢进步，假以时日终将也可以写出优雅高效率的方法

云服务器 GPU云服务器波那契数列解斐波 fibonacci数列 javascript实用

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/81959.html

js 实现斐波那契数列(数组缓存、动态规划、尾调用优化)

摘要：根据该规则，返回第个斐波那契数。尾递归函数调用自身，称为递归。一个前端眼中的斐波那契数列解斐波那契数列的实用解法调用栈尾递归和手动优化尾调用优化译我从用写斐波那契生成器中学到的令人惊讶的件事斐波那契数列是以下一系列数字： 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, ... 在种子数字 0 和 1 ...

赵连江 2019-08-23 11:38 评论0 收藏0
斐波那契数列求和的js方案以及优化

摘要：在上做了一道斐波那契数列求和的题目，做完之后做了一些简单的优化和用另一种方法实现。动态规划解决方案斐波那契数列求和除了可以用递归的方法解决，还可以用动态规划的方法解决。在codewars上做了一道斐波那契数列求和的题目，做完之后做了一些简单的优化和用另一种方法实现。题目 function fibonacci(n) { if(n==0 || n == 1) r...

xinhaip 2019-08-20 11:35 评论0 收藏0
斐波那契数列（求fibonacci的第N项的值）

摘要：今天在公司实习，实在没啥活是我能干的，就想着写一写算法打发时间，正好看到了斐波那契数列，搞起。这是斐波那契数列的通项公式以前用递归写过，今天看的时候书上说递归虽然简单，但其实内部做了很多重复的计算，而且尾递归都是可以用循环解决的。今天在公司实习，实在没啥活是我能干的，就想着写一写算法打发时间，正好看到了斐波那契数列，搞起。这是斐波那契数列的通项公式：showImg(https://...

Fundebug 2019-08-16 12:35 评论0 收藏0
使用js实现斐波那契数列

摘要：前言前几天面试被问到了斐波那契数列的实现以及优化的问题，当时现场卡了挺久的，现在进行一下总结使用实现。题目介绍斐波那契数列又被称为黄金分割数列，指的是这样的一个数列，它有如下递推的方法定义是正整数，请使用实现斐波那契函数。前言前几天面试被问到了斐波那契数列的实现以及优化的问题，当时现场卡了挺久的，现在进行一下总结（使用js实现）。题目介绍斐波那契数列又被称为黄金分割数列，指...

alexnevsky 2019-08-26 13:36 评论0 收藏0
算法记录 >> 斐波那契数列

摘要：今天去面试笔试题斐波那契数列实现，虽然很简单。回来想想既然算法这么重要那就从这个开始来记录自己的算法库吧。在数学上，斐波纳契数列以如下被以递归的方法定义，，。斐波拉契算法规律很简单，，观察下数列值就很容易总结出来了。一、写在前面算法这块对于大多数程序员（包括我）来说可能都是一个薄弱的地方，如何弥补尼？每个人都知道那就是学习、特别是算法没有任何捷径可走。在这记录平时自己工作和生...

robin 2019-08-16 17:52 评论0 收藏0