1.问题描述:
给一个正整数num,返回小于或等于num的斐波纳契奇数之和。
斐波纳契数列中的前几个数字是 1、1、2、3、5 和 8,随后的每一个数字都是前两个数字之和。
例如,sumFibs(4)应该返回 5,因为斐波纳契数列中所有小于4的奇数是 1、1、3;
2.思路:先实现一个斐波那契数列的函数(不要使用递归方法实现,会造成函数调用栈溢出),可用数组的方式;由于斐波那契数列的前两项比较特殊都为1,可提取a =1,b = 1,具体实现如下:
function Fibs(num) {
var a = 1,b = 1;
var arr = [1,1],i = 2;//arr用来保存斐波那契数组,i设置为2跳过前两个1
while(i < num){
a = [b,b = a + b][0];//根据运算符优先级,先执行b = a + b,然后数组索引a得到了b的值
//可用es6中的解构赋值运算[a,b] = [b,a]来实现
arr.push(b);
i++;
}
return arr;
}
Fibs(10)l//得到[1, 1, 2, 3, 5, 8, 13, 21, 34, 55];
然后就简单了,遍历得到的数组,把小于num的奇数相加;
function sumFibs(num){
var cur = 0,total = 0;
var arr = Fibs(num);
for(var j = 0,len = arr.length;j<len;j++ ){
cur = arr[j];
if(cur > num ) break;
if(cur % 2 == 1) total += cur;
}
return total;
}
sumFibs(4);// 5
3.函数优化:
function sumFibs(num) {
var total = 1,i = 0,
a = 0,b = 1;
while(i < num){
a = [b,b = a + b][0];
if(b <= num && b % 2 == 1) total += b;
i++;
}
return total;
}