文档章节

斐波那契数列

万城
 万城
发布于 2017/07/26 10:17
字数 598
阅读 9
收藏 0

1、递归

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

2、数组缓存

function fbnqsl() {
    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];     //前后两位相加,传递到数组后面的项
                //console.log(cache);       //打印一下直接明了
            }
        }
        return cache[n - 1];
    }
}
//console.log(fbnqsl()(10));

3、直接使用加法

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; 
}

 

对比:

如果只使用一次运算,第三种方法速度最快;

如果多次使用,第二种方法明显优于其它两种;

在n较大的情况下不推荐使用第一种;n为10*10000的时候递归就已经报内存溢出了

function test(fn, n) {
    var date = +new Date();
    fn(n);
    console.log("newdate:" + new Date().getTime() + "\n" + "date:" + date);
    return new Date().getTime() - date;     //计算运算时间,结束时间减去开始时间,计算次数的话可以用一个变量来保存
}
var IterMemoFib = 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];
    }
}();
var num = 10000*100;
console.log(test(IterMemoFib, num));

//计算运行时间
function jssjadd(){
    var sum = 0 ;
    for(var i = 0;i<10000000;i++){
        sum += i;
    }
    return sum;
}
function jssj(func){
    var start = new Date().getTime();//起始时间
    func();//执行待测函数
    var end = new Date().getTime();//接受时间
    return (end - start)+"ms";//返回函数执行需要时间
}
var time = jssj(jssjadd);
console.log(time);

 

返回斐波那契数列里的奇数

//返回斐波那契数列里的奇数
function sumFibs(num) {
    var arr=get(num);  //获取数列
    var res=arr.filter(function(a){   //筛选出奇数
        return a%2!==0;
    }).reduce(function(a,b){   //返回奇数之和
        return a+b;
    });
    return res;
}
function get(num){  //返回一个斐波纳契数列,最后一位小于等于num
    var arr=[1];
    var sum=1;
    var before=0;
    var after=1;
    while( sum<=num ){      //看log里会比较清晰一点,具体的是before是第一位,after是第二位,sum是第三位,第三位等于前两位相加,然后循环依次下去,下面两行的意思相当于第一位等于第二位,第二位等于第三位,所以再增加的那一位就是前两位相加的和了。用唯一来理解思路会比较清晰
        arr.push(sum);
        before=after;
        after=sum;
        sum=before+after;
        //console.log("sum:" + sum + "\n" + "before:" + before + "\n" + "after:" + after + "\n" + "arr:" + arr + "\n" );
    }
    return arr;
}
sumFibs(10);

© 著作权归作者所有

万城
粉丝 2
博文 50
码字总数 99199
作品 0
青岛
前端工程师
私信 提问

暂无文章

Taro ScrollView 组件的 scrollTop 属性是个坑

官方issue:ScrollView设置scrollTop没效果 同样的,设置 scrollTop=0 并不能实现置顶,官方回复早就修复了,我的 Taro 版本已经是最新的,然而并未修复。 万能的评论区,给出了失效的原因。...

dkvirus
30分钟前
3
0
Qt那些事0.0.21

这次还是关于PRO文件中QMAKE_POST_LINK的故事。 平时都是使用VS2015作为编译器,恰巧想用MinGW编一版程序,结果偏偏出现了错误。话说测试的这个项目可是在Linux下(fodera 20)可以正确编译通...

Ev4n
40分钟前
0
0
OSChina 周六乱弹 —— 抖音外放 亲妈下葬。

Osc乱弹歌单(2019)请戳(这里) 【今日歌曲】 @巴拉迪维 :一直没想明白黎明是怎么混进「四大天王」的,直到最近网易云音乐心动模式开启之后 #今日歌曲推荐# 《那有一天不想你》- 黎明 手机...

小小编辑
今天
362
8
Linux使用源码包安装软件

前言: 最近整理一些以前的学习笔记。 过去都是存储在本地,此次传到网络留待备用。 源码包 Linux软件多数免费、开源,是开发人员编写的,具有很强可读性的一组相关代码文本。 源码包 --> 编...

迷失De挣扎
今天
6
0
IPv4如何转换为IPv6?

ipv6已经逐渐在应用,现在已经有很多的运营商支持ipv6,前天我们也发布了如何让电脑使用ipv6地址?有很多朋友在问?ipv6有什么作用,它的表示方式是什么,今天我们来一起来详细了解下ipv6相关计...

xiangyunyan
今天
6
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部