使用js实现斐波那契数列

alexnevsky 发布于2019-08-26 13:36 / 2030人阅读

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

前言

前几天面试被问到了斐波那契数列的实现以及优化的问题，当时现场卡了挺久的，现在进行一下总结（使用js实现）。

题目介绍

斐波那契数列又被称为黄金分割数列，指的是这样的一个数列：1,1,2,3,5,8,13,21,34....，它有如下递推的方法定义：F(1)=1,F(2)=1,F(n)=F(n-1)+F(n-2)(n>=2,n是正整数)，请使用js实现斐波那契函数。

方法1：递归实现

由题目中的递推受到启发，可以通过递归的方式去实现，代码如下：

function fibonacci(n){
        if(n < 0) throw new Error("输入的数字不能小于0");
        if(n==1 || n==2){
            return 1;
        }else{
            return fibonacci1(n-1) + fibonacci1(n-2);
        }
    }

优点：代码比较简洁易懂；
缺点：当数字太大时，会变得特别慢，原因是在计算F(9)时需要计算F(8)和F(7)，但是在计算F(8)时要计算F(7)和F(6)，这里面就会重复计算F(7)，每次都重复计算会造成不必要的浪费，所以这种方法并不是很好。

方法2：使用闭包保存每次的递归值

由方法1可知，使用普通的递归，会造成不必要的浪费，所以我们首先想到的应该是将每次产生的递归值保存下来，下次直接使用就行，代码如下：

function fibonacci(n){
        if(n < 0) throw new Error("输入的数字不能小于0");
        let arr = [0,1];//在外部函数中定义数组，内部函数给数组添加值
        function calc(n){
            if(n<2){
                return arr[n];
            }
            if(arr[n] != undefined){
                return arr[n];
            }
            let data = calc(n-1) + calc(n-2);//使用data将每次递归得到的值保存起来
            arr[n] = data;//将每次递归得到的值放到数组中保存
            return data;
        }
        return calc(n);
    }

方法3：直接使用数组实现（动态规划）

和方法2的思想类似，为了避免后续的重复计算，需要将计算过的值保存起来，我们可以直接使用数组进行保存。

function fibonacci(n){
        var a = [0,1,1];
        if(n < 0) throw new Error("输入的数字不能小于0");
        if(n >= 3){
            for(var i=3;i<=n;i++){
                a[i] = a[i-1]+a[i-2];
            }
        }
        return a[n];
    }

方法4：直接使用变量实现

相校于使用数组的方式去存放，使用变量的方式就不会那么浪费内存了，因为总共只会有3个变量，但是也有缺点，它只能保存最后计算的值以及前两个值，以前的值会被替换掉。

function fibonacci(n){
        var pre = 0;//表示前一个值
        var cur = 1;//表示后一个值
        var data;//表示当前值

        if(n < 0) throw new Error("请输入大于0的值！");
        if(n == 0) return 0;
        if(n == 1) return 1;
        if(n > 2){
            for(var i=2;i<=n;i++){
                data = pre + cur;
                pre = cur;
                cur = data;
            }
        }
        return data;
    }

总结

其实大部分人在求斐波那契数列时想到的都是递归的方法，但是就其事件复杂度来看，不是一个好的方法，那么我们的优化思路可能就是使用空间换换时间了，就是将递归产生的值保存下来，以免下次还要重复计算。

超融合服务器私有云波那契数列解斐波递减数列数列

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

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

太原面经分享：如何用js实现返回斐波那契数列的第n个值的函数

摘要：那其实这个问题还可以换个问法实现一个函数，输入一个数字能返回斐波那契数列的第个值。文章预告更多的前端面试分享我都会第一时间更新在我的公众号闰土大叔里面，欢迎关注面试攒经验，lets go！值此高考来临之际，闲不住的我又双叒叕出发去面试攒经验了，去了公司交待一番流程后，面试官甩给了我一张A4纸，上面写着一道js算法笔试题（一开始我并不知道这是在考察js算法），上面写着1、1、2、3、...

Galence 2019-08-26 12:01 评论0 收藏0
js实现斐波那契数列

摘要：实现斐波那契数列斐波那契数列最大数斐波那契数列由和开始之后的斐波那契数列系数就由之前的两数相加。换个写法，用箭头函数最大数斐波那契数列由和开始 js实现斐波那契数列 // 斐波那契数列 let max=10000; // 最大数 let arr=[0,1]; // 斐波那契数列由 0 和 1 开始 // 之后的斐波那契数列系数就由之前的两数相加。 ...

notebin 2019-08-23 15:42 评论0 收藏0
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
算法记录 >> 斐波那契数列

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

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