javascript 实现斐波那契数列的不同姿势

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

快过年了，公司人基本上都走光了，只有共和国最优秀的人才，各部门最重要的岗位才会坚守在各自的转椅上，毕竟每个人的能力有限，与其让他们继续工作，不如放他们回家过年。这觉悟很高，这领悟很痛~

闲着没事做（其实我有事情做，但是我不想做，做为社会主义的接班人，我想我有权利这么任性！），想起了一个挺有意思的兔子问题：一般而言，兔子在出生两个月后，就有繁殖能力，一对兔子每个月能生出一对小兔子来。如果所有兔都不死，那么一年以后可以繁殖多少对兔子？

首先明确题意，是求每个月兔子的总对数。将兔子分成三种，兔子出生第一个月为小兔子，第二个月为中兔子，第三个月为大兔子（可以繁殖小兔子了），所以第一个月兔子的对数为：1、0、0；第二个月兔子的总对数为0、1、0；第三个月兔子的对数为1、0、1;第四个月的兔子对数为：1、1、1；第五个月兔子的对数为：2、1、2；第六个月：3、2、3；第七个月：5、3、5；第七个月：8、5、8....由此可知每个月对应的兔子对数是：1、1、2、3、5、8、13... 仔细观察每个月兔子的对数，从第三个月开始，每个月兔子的对数是前连个月的兔子对数和。这样就好办了。我们用先用队列的方式来实现一下：创建一个数组，记录前两个月兔子，同时可以用数组的push()、shift（）方法来模拟队列的一些特性，记住，吃多了拉就是队列，吃多了吐就是栈。

  function fibonacci (len) {

            //首先创建一个fibonacci数组，记录兔子的对数，因为前两个月兔子的对数是确定，所以我们要设置fibonacci内前两个月值。
             const fibonacci = [1, 1];

              //复制这个数组用于兔子的队列操作
             const arr = Array.from(fibonacci);

            //循环计算出第len个月兔子的总对数
             for(let i = 0; i < len-2; i++) {

               //fibonacci 每次添加前两个月的兔子对数的和
                 fibonacci.push(arr.reduce((sum, value) =>{
                     return sum + value;
                 }, 0));

                //将当前月的兔子总数进入队列，为了计算下个月的兔子总数
                 arr.push(arr.reduce((sum, value) =>{
                     return sum + value;
                 }, 0));

                //当前月的兔子已经计算出来了，所以我们不再需要知道上上个月的兔子对数了，所以把它踢出队列
                 arr.shift();
             }

           //fibonacci数组中保存的是每个月兔子的对数，只要返回len-1个月就可以了
             return fibonacci[len-1];
         }

然后我们再用用另一种方法来实现，就通过变量循环赋值来计算就可以，这个比较简单。

function fibonacci_2 (len) {
            let a = 1, // 上上个月
                b = 1, //上一个月
                c = null,  //当前月
                arr = [1, 1];

                for(var i = 0; i< len-2; i++) {
                    c = a+b;
                    arr.push(c);
                    a = b;
                    b = c;
                }
            return arr[len-1];
      }

还有一种就是比较常见的递归方法：

const firbonacci = (function() {

          //创建一个数组，保存前两个月的兔子
          const arr = [0, 1];
            return function fn (n){

                      if(n < 0) return ;
                        
                      //如果是前两个月，直接返回数组对应的项
                      if(n < 2) return arr[n];

                      if(arr[n]) return arr[n];

        　　　　　　　　//递归执行函数
                      return fn(n-1) + fn(n-2);
            }

}());

实现斐波那契数列还有很多的方法，用数据结构来解决问题我觉得是很有意思的事情，以上的实现方式不考虑时间复杂度、空间复杂度什么的，哥写代码就一句话：撸起袖子，操起键盘，一顿Ctrl+c 和Ctrl+v，就是干！