第 3 题：多种方式实现斐波那契数列

[lgwebdream]

欢迎在下方发表您的优质见解

[Genzhen]

参考实现

数学上是以递归的方法来定义

F(0) = 0;
F(1) = 1;
F(n) = F(n - 1) + F(n - 2);

• 公式版：递归

function fib(n) {
  if(n < 0) throw new Error('输入的数字不能小于0');
  if (n < 2) {
    return n;
  }
  return fib(n - 1) + fib(n - 2);
}

正常递归版本是一个既简单又直接的逻辑，但是这个版本有个问题就是存在大量重复计算。如：当 n 为 5 的时候要计算fib(4) + fib(3)当 n 为 4 的要计算fib(3) + fib(2) ，这时fib(3)就是重复计算了。运行 fib(50) 等半天才会出结果。

• 迭代:for 循环

function fib(n) {
  if(n < 0) throw new Error('输入的数字不能小于0');
  let f0 = 0,
    f1 = 1,
    curFib = f0;
  if (n < 2) {
    return n;
  }
  for (let i = 1; i < n; i++) {
    curFib = f0 + f1;
    f0 = f1;
    f1 = curFib;
  }
  return curFib;
}

这个版本没有重复计算问题，速度也明显快了很多。这并不代表循环比递归好。循环的问题在于状态变量太多，为了实现 fib 这里使用了 4 个状态变量(f0,f1,curFib,i) 而状态变量 在写、修改、删除的过程中需要格外小心。状态变量多了阅读起来也不那么优美了。

• 去除重复计算的递归版本

function fib(n) {
  if(n < 0) throw new Error('输入的数字不能小于0');
  if (n < 2) return n;
  function _fib(n, a, b) {
    if (n === 0) return a;
    return _fib(n - 1, b, a + b);
  }
  return _fib(n, 0, 1);
}

把前两位数字做成参数巧妙的避免了重复计算，性能也有明显的提升。n 做递减运算，前两位数字做递增（斐波那契数列的递增）,这段代码一个减，一个增。

• 基于 ES6 Generator 实现

function* fib(n) {
  if(n < 0) throw new Error('输入的数字不能小于0');
  let f0 = 1,
    f1 = 1,
    count = 0;
  while (count < n) {
    yield f0;
    [f0, f1] = [f1, f0 + f1];
    count++;
  }
}

• 数组方法

function fib(n) {
  if(n < 0) throw new Error('输入的数字不能小于0');
  if (n < 2) {
    return n;
  }
  let list = [];
  list[0] = 0;
  list[1] = 1;
  for (let i = 1; i < n; i++) {
    list[i + 1] = list[i] + list[i - 1];
  }
  return list[n];
}

[metal88888]

function fibonacci(n, map = {}) { if (n == 1 || n == 2) return n; if (map[n]) return map[n]; let data = fibonacci(n - 1, map) + fibonacci(n - 2, map) map[n] = data return data }

[luobolin]

export const fibonacci = (n: number): number => {
    const base = Math.sqrt(5)
    return (((1 + base) / 2) ** n - ((1 - base) / 2) ** n) / base
}
console.log(fibonacci(8))

[thinkfish]

function fibonacci (n) {
    if (!n) {
       return 0
    }
    if(n===1 || n === 2) {
       return 1
    }
    let num1 = 1
    let num2 = 1
    let num3 = 0
    for (let i = 2; i <  n; i++){
          num3 = num1 + num2
          num1 = num2
          num2 = num3
   }
  return num3
}

时间复杂度 O(n)

[thunderstromcd]

使用generator

const createAry = function(args){
  
    let handler = {
        get: function(target,propKey,reciever){
            return Reflect.get(target,propKey<0 ? (+propKey + target.length) : propKey,reciever)
        },
        set :function (target,propKey,value,reciever){
            return Reflect.set(target,propKey<0 ? (+propKey + target.length) : propKey,value,reciever)
        }
    }
    return new Proxy(args,handler)
}

var ary= createAry([1,2,3,4])

console.log(ary[-1]);

ary[-1]='a'
console.log(ary[-1]);

[123456zzz]

const fibonacci = (n: number) => {
  let pre = 1,
    cur = 1;
  if (n === 1 || n === 2) {
    return 1;
  }
  for (let i = 3; i <= n; i++) {
    [pre, cur] = [cur, pre + cur];
  }
  return cur;
};

console.assert(fibonacci(1) === 1);

console.assert(fibonacci(2) === 1);

console.assert(fibonacci(3) === 2);

console.assert(fibonacci(4) === 3);

[523451928]

function fibonacci(n) { if (n <= 1) { return n } return fibonacci(n - 1) + fibonacci(n - 2) } fibonacci(5)

[cool-518]

@Genzhen 写的明显有问题还那么多人点赞，笑死

[Genzhen]

@Genzhen 写的明显有问题还那么多人点赞，笑死

@cool-518 是基于ES6 Generator实现这个？输出是没有问题的

function* fib(n) {
  if (n < 0) throw new Error("输入的数字不能小于0");
  let f0 = 1,
    f1 = 1,
    count = 0;
  while (count < n) {
    yield f0;
    [f0, f1] = [f1, f0 + f1];
    count++;
  }
}
for(let n of fib(10)){
  console.log(n);
}
// 1 1 2 3 5 8 13 21 34 55

[yaooooooooo]

function fabonacci(i , i1 = 1 , i2 = 1){ if(i<= 1) return i2; return fabonacci(i -1, i2, i1 + i2) }

[GolderBrother]

/**

• 求斐波那契数列第n项的值
• @param {*} n 第n项
• @param {*} map 第n项的值，缓存计算结果，防止重复计算 */ function fibonacci(n, map = {}) { if (n === 1 || n === 2) return n; if (map[n]) return map[n]; // fn(n) = fn(n - 1) + fn(n - 2); const result = fibonacii(n - 1, map) + fibonacii(n - 2, map); map[n] = result; return result; }

/**

• 求斐波那契数列第n项的值
• @param {*} n 第n项 */ function fibonacci(n) { let pre = 1, cur = 1, data; if (n === 1 || n === 2) return n; for (let i = 3; i <= n; i++) { data = pre + cur; pre = cur; cur = data; } return data; }

/**

• 求斐波那契数列第0-n项的集合
• @param {*} n */ function fibonacci(n) { let a = 1, b = 1, sum; let arr = [1, 1]; for (let i = 3; i <= n; i++) { sum = a + b; a = b; b = sum; arr.push(sum); } return arr; }

[Z6T]

function fn (n){
    if(n==0) return 0
    if(n==1) return 1
    return fn(n-2)+fn(n-1)
}

const fn = (n)=>{
    let pre = 1;
    let cur = 1;
    let data ;
    for(var i = 3;i<=n;i++){
// 和变成当前项cur,而当前项cur会变成pre
        data = pre + cur;
        pre = cur 
        cur = data
    }
    return data
}
console.log(fn(2))

[chun1hao]

function (n) { if(n<2) return n let a = 0,b = 1 for(let i=2;i<=n;i++){ [a, b] = [b, a+b] } return b }

[JJL-SH]

// 0,1,1,2,3,5,8,13,21
const fbnq = (num) =>
  Array.from(new Array(num)).reduce((cacheArr, it, index) => {
    if (index > 1) {
      cacheArr.push(cacheArr[index - 2] + cacheArr[index - 1]);
    } else {
      cacheArr.push(index);
    }

    return cacheArr;
  }, []);

console.log(fbnq(9));

[huzedong2015]

性能最低到50就会卡死

function fibonacci(n) {
    if (n < 3) {
        return 1;
    }

    return fibonacci(n - 2) + fibonacci(n - 1);
}

console.time("fibonacci1");
console.log(fibonacci(40));
console.timeEnd("fibonacci1");

性能大幅提升

function fibonacci2(n) {
    const arr = [1, 1, 2];
    const arrLen = arr.length;

    if (n <= arrLen) {
        return arr[n];
    }

    for (let i = arrLen; i < n; i++) {
        arr.push(arr[i - 1] + arr[ i - 2]);
    }

    return arr[arr.length - 1];
}

console.time("fibonacci2");
console.log(fibonacci2(10000));
console.timeEnd("fibonacci2");

性能进一步提升

function fibonacci3(n) {
    let pre1 = 1;
    let pre2 = 1;
    let current = 2;

    if (n <= 2) {
        return current;
    }

    for (let i = 2; i < n; i++) {
        pre1 = pre2;
        pre2 = current;
        current = pre1 + pre2;
    }

    return current;
}

console.time("fibonacci2");
console.log(fibonacci3(10000));
console.timeEnd("fibonacci2");

[RainyNight9]

function fabonacci(n) {
  let arr = [0, 1];
  for (let i = 2; i <= n; i++) {
      arr.push(arr[i-2] + arr[i-1]);
  }
  return arr;
}

[ghost]

function fabonacci(n, n_1, n_2) { if(n==1) return n_1; return fabonacci(n-1, n_1+n_2, n_1); }

[carbrokers]

function fabonacci(max) {
  if (max === 1 || max === 2) {
    return 1;
  }
  return fabonacci(max - 1) + fabonacci(max - 2);
}

[NameWjp]

function fibonacci(n) {
  if (n === 1) {
    return 1
  } else if (n === 2) {
    return 1
  } else {
    return fibonacci(n -1) + fibonacci(n - 2)
  }
}

[ruandao]

const fibonacci = (n) => {
    if(n < 3) {
        return 1
    }
    const arr = [1, 1];
    for(let x=3;x<=n;x++) {
        arr.push(arr[x-2] + arr[x-3])
   }
   return arr[n-1];
}

[chengazhen]

  function fun(length = 10, a = 0, b = 1) {
      let arr = []
      do {
        if (arr.length < 2) {
          arr.push(a)
          arr.push(b)
        } else {
          arr.push(arr[arr.length - 2] + arr[arr.length - 1])
        }
      } while (arr.length < length);
      return arr
    }
    
    console.log(fun(20));
// [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181]

[markduan]

function fibonacci(n) {
  if (n < 2) return n

  let a = BigInt(0), b = BigInt(1)

  for (let i = 2; i <= n; i++) {
    [a, b] = [b, a + b]
  }

  return b
}

[Jam-Chu]

    // =============无备忘录===================
    function fibonacci(n) {
      if (n === 1 || n === 2) { return 1 };
      return fibonacci(n - 1) + fibonacci(n - 2);
    }
    console.log(fibonacci(30))


    // =============有备忘录===================
    function fibonacci_memo(n, memo = {}) {
      if (n === 1 || n === 2) return 1;
      if (memo[n]) return memo[n];
      let data = fibonacci_memo(n - 1, memo) + fibonacci_memo(n - 2, memo);
      memo[n] = data;
      return data;
    }
    console.log(fibonacci_memo(30))
    // =============for迭代===================
    function fibonacci_for(n) {
      if (n === 1 || n === 2) return 1;
      let total = 0, cur = 1, pre = 1;
      for (let i = 3; i <= n; i++) {
        total = (pre + cur);
        pre = cur;
        cur = total;
      }
      return total;
    }
    console.log(fibonacci_for(30))
    // =============generater步进===================
    function fibonacci_gen(n) {
      function* gen() {
        let total = 0, cur = 1, pre = 1
        while (1) {
          total = cur + pre;
          yield total;
          [cur, pre] = [total, cur];
        }
      }
      let iterator = gen();
      let data = 0;
      if (n === 1 || n === 2) data = 1;
      else {
        for (i = 3; i <= n-1; i++) {
          iterator.next();
        }
        data = iterator.next().value
      }
      return data;
    }
    console.log(fibonacci_gen(30))

[Jam-Chu]

    // =============无备忘录===================
    function fibonacci(n) {
      if (n === 1 || n === 2) { return 1 };
      return fibonacci(n - 1) + fibonacci(n - 2);
    }
    console.log(fibonacci(30))


    // =============有备忘录===================
    function fibonacci_memo(n, memo = {}) {
      if (n === 1 || n === 2) return 1;
      if (memo[n]) return memo[n];
      let data = fibonacci_memo(n - 1, memo) + fibonacci_memo(n - 2, memo);
      memo[n] = data;
      return data;
    }
    console.log(fibonacci_memo(30))
    // =============for迭代===================
    function fibonacci_for(n) {
      if (n === 1 || n === 2) return 1;
      let total = 0, cur = 1, pre = 1;
      for (let i = 3; i <= n; i++) {
        total = (pre + cur);
        pre = cur;
        cur = total;
      }
      return total;
    }
    console.log(fibonacci_for(30))
    // =============generater步进===================
    function fibonacci_gen(n) {
      function* gen() {
        let total = 0, cur = 1, pre = 1
        while (1) {
          total = cur + pre;
          yield total;
          [cur, pre] = [total, cur];
        }
      }
      let iterator = gen();
      let data = 0;
      if (n === 1 || n === 2) data = 1;
      else {
        for (i = 3; i <= n-1; i++) {
          iterator.next();
        }
        data = iterator.next().value
      }
      return data;
    }
    console.log(fibonacci_gen(30))

[chessyu]

function fibonacci(num){
 var arr = [];
 for(var i = 0; i<num; i++){
     if(i<2){
        arr.push(1);
     }else{
        arr.push(arr[i-2] + arr[i-1])
     }
 }   
 return arr;
}
fibonacci(10)
//[1, 1, 2, 3, 5, 8, 13, 21, 34, 55]

[DakerHub]

使用generator

const createAry = function(args){
  
    let handler = {
        get: function(target,propKey,reciever){
            return Reflect.get(target,propKey<0 ? (+propKey + target.length) : propKey,reciever)
        },
        set :function (target,propKey,value,reciever){
            return Reflect.set(target,propKey<0 ? (+propKey + target.length) : propKey,value,reciever)
        }
    }
    return new Proxy(args,handler)
}

var ary= createAry([1,2,3,4])

console.log(ary[-1]);

ary[-1]='a'
console.log(ary[-1]);

答错题了兄弟

[qq820137708]

// 尾递归
function Fibonacci(n, a= 1, b= 1) {
    if(n <= 1) {return b};
    return Fibonacci(n - 1, b, a + b);
}
console.log(Fibonacci(10))

[MR-YangXu]

欢迎在世界发表您的优质观点 // 这是输出对应的索引值 function flat(n) { if (n < 0) throw new Error('输入的数字不能小于0'); return Array.from({length: n + 1}).reduce((t, v, i) => (i > 1 && t.push(t[i - 1] + t[i - 2]), t), [0, 1])[n] } // 这是输出对应长度的数组 function flat(len = 2) { return Array.from({length: len}).reduce((t, v, i) => (i > 1 && t.push(t[i - 1] + t[i - 2]), t), [0, 1]) }

[Luoyuda]

    var fib = (n) => {
        if(n <= 1) return n
        return fib(n - 1) + fib(n - 2)
    }
    console.time('fib-1')
    console.log(fib(20))
    console.timeEnd('fib-1')
    var fib = (n) => {
        if(n <= 1) return n
        fib.cache = fib.cache || {}
        if(fib.cache[n]) return fib.cache[n]
        fib.cache[n] = fib(n - 1) + fib(n - 2)
        return fib.cache[n]
    }
    console.time('fib-2')
    console.log(fib(20))
    console.timeEnd('fib-2')
    var fib = (n) => {
        if(n <= 1) return n
        let one = 0
        let two = 1
        for(let i = 2; i <= n; i++){
            let o = one + two
            one = two
            two = o
        }
        return two
    }
    console.time('fib-3')
    console.log(fib(20))
    console.timeEnd('fib-3')

[geekftz]

// 记录fib(n - 1)和fib(n-2) 避免重复计算 从下标2开始向上计算 function fib1(n) { if (n < 0) throw new Error('输入的数字不能小于0');

if (n < 2) { return n; }

let f0 = 0; let f1 = 1; let fn = f0;

// 从下标为2开始 let i = 2;

while (i <= n) { fn = f0 + f1; f0 = f1; f1 = fn; i++; }

return fn; }

var n = 3; var res1 = fib1(n); console.log('%c res1 = %s', 'color: #007300', res1);