[Intermediate Algorithm] - Sum All Odd Fibonacci Numbers

题目

给一个正整数num，返回小于或等于num的斐波纳契奇数之和。

斐波纳契数列中的前几个数字是 1、1、2、3、5 和 8，随后的每一个数字都是前两个数字之和。

例如，sumFibs(4)应该返回 5，因为斐波纳契数列中所有小于4的奇数是 1、1、3。

提示

此题不能用递归来实现斐波纳契数列。因为当num较大时，内存会溢出，推荐用数组来实现。

参考文档：博客园，Issue 
Remainder

测试用例

• sumFibs(1) 应该返回一个数字。
• sumFibs(1000) 应该返回 1785。
• sumFibs(4000000) 应该返回 4613732。
• sumFibs(4) 应该返回 5。
• sumFibs(75024) 应该返回 60696。
• sumFibs(75025) 应该返回 135721。

分析思路

斐波那契数第一个和第二个为 1 是固定的，所以初始数组可以设置为： 
var fibsArray = [1, 1]; 
然后根据最后一个数等于前两数之和设置下一个数组元素，这样就组成了需要的斐波那契数组。对于奇数直接计算提出就行。

代码

1.function sumFibs(num) {

2.  var fibsArray = [1, 1];

3.  var retVal = 1;

4.

5.  while (fibsArray[fibsArray.length - 1] <= num) {

6.    if (fibsArray[fibsArray.length - 1] % 2) {

7.      retVal += fibsArray[fibsArray.length - 1];

8.    }

9.    fibsArray.push(fibsArray[fibsArray.length - 2] + fibsArray[fibsArray.length - 1]);

10.  }

11.  fibsArray.pop(); /* 去除最后一个大于 num 的数 */

12.

13.  return retVal;

14.}

15.

16.sumFibs(4);

另一个不用到数组的方法，该方法主要是针对该题的

1.function sumFibs(num) {

2.  var fibo = [1, 1];

3.  var oddSum = 2;

4.

5.  while(true){

6.    var item = fibo[0] + fibo[1];

7.    if(num < item){

8.      return oddSum;

9.    }

10.    if(item % 2){

11.      oddSum += item;

12.    }

13.    fibo[0] = fibo[1];

14.    fibo[1] = item;

15.  }

16.}

17.

18.sumFibs(4);