Sum All Odd Fibonacci Numbers

FCC第289题：

要点一：用递归实现斐波那契数列时要注意，如果数值过大，函数嵌套过深，会导致内存溢出，浏览器会崩溃。递归实现斐波那契数列，代码如下所示：

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

如果此时调用fib(1000000)，那么在函数内部会同时调用fib(999999)和fib(999998)，而fib(999999)和fib(999998)又会接着调用另外的函数，这样函数互相嵌套，会占用相当大的内存，导致内存溢出。

所以若要安全地使用此函数，函数内部最好先做一个判断，如果n大于某个数值时就直接退出。

要点二：实现斐波那契数列的三种方式。递归，数组缓存，直接加法。递归前面已经讲过了，接下来讲讲数组和加法。

数组缓存：

var Fib = function() { 
    var cache = [1, 1]; 
    return function (n) { 
        if (n >= cache.length) { 
            for (var i = cache.length; i < n ; i++ ) { 
                cache[i] = cache[i - 2] + cache[i - 1]; 
            } 
        } 
        return cache[n - 1]; 
    } 
}();

这个函数用了一个for循环来生成斐波那契数列，并将数列保存在数组中，然后返回该数组的最后一个值。如果你想返回所有奇数的和，可以把最后一条return语句改动一下即可。不过有一个问题就是为什么这里面要有两条return语句呢？如果有两条return语句，遇到第一条return语句不就直接跳出当前函数了吗？为什么还会执行下一条return语句？

数组缓存方法适用于需多次使用的场景。

加法：

function fib(n) {
    if (n < 2) {
        return 1;
    }
    var a = 1, b = 1;
    for (var i = 2; i < n - 1 ;i++ ) {
        b = a + b;
        a = b - a;
    }
    return a + b;
}

这个for循环的原理其实是先将前两个数相加得到的第3个值赋给b，再用第3个数减掉第1个数得到第2个数并赋给a，这样就相当于a和b各往前推了一位。将最终得到的ab相加就得到了最后一项的值。这个没有得到整个婓波那契数列，但改装一下也是可以做到的，将每次计算出的a和b的值都用arr装上，arr.push(a,b)，就得到了斐波那契数列。

加法在只使用一次的情况非常合适。

最终解决FCC的这个算法问题的代码如下：

var sumFibs = function() {
    var cache = [1, 1];
    return function (n) {
        if (n >= cache.length) {
            for (var i = cache.length; i < n ; i++ ) {
                cache[i] = cache[i - 2] + cache[i - 1];
            }
        };
        var arr=cache.filter(function(val){
           return val%2!==0&&val<=n;
         });
        return arr.reduce(function(pre,next){
          return pre+next;
        });
    };
}();

优质内容筛选与推荐>>
1、后台添加tdk Option Type
2、线性表的链式存储实现（带头结点）
3、计算机组成相关
4、[原创]sqlServer2005-将删除的记录写到另一个表中
5、解决：IDEA springmvc maven 项目搭建完后没有生成 webcontent 目录

0 │ 收藏 │ 举报

朋友将在看一看看到

分享想法到看一看