斐波那契数列(Javascript)

116 阅读 0 评论 77 点赞

我是靠谱客的博主闪闪蜡烛，最近开发中收集的这篇文章主要介绍斐波那契数列(Javascript)，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

斐波那契数列 - 动态规划基础

斐波那契数，通常用 F(n) 表示，形成的序列称为斐波那契数列。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是： F(0) = 0，F(1) = 1 F(n) = F(n - 1) + F(n - 2)，其中 n > 1 给你n ，请计算 F(n) 。

1.dp数组保存结果；
2.确定递推公式: dp[i] = dp[i - 1] + dp[i - 2];
3 dp数组初始化： dp[0] = 0; dp[1] = 1;
1. 确认遍历顺序：由递推公式可以看出：dp[i] 是依赖于dp[i - 1] 和dp[i - 2]的，则遍历的顺序是从前到后遍历；
5.举例推导出dp数组：按照公式，则手推导出：0 1 1 2 3 5 8…

1. for循环遍历

let number = 10;
let res = [];
res.push(0);
res.push(1);
// 遍历长度，从最小的开始算起 0 1 1 2 3 5 8 ......
for (let i = 2; i <= number; i++) { 
  const newNumber = res[i - 1] + res[i - 2];
  res.push(newNumber);
}
console.log('res: ', res);// res:  [ 0, 1,  1,  2,  3,5, 8, 13, 21, 34, 55]

2.递归

根据：

（1）公式；
（2）初始条件；也可以叫递归的出口？

console.time('fib0')
function fib0(n) {
  if (n < 2) {
      return n;
  }
  return fib0(n - 2)+ fib0(n - 1);
}
console.log('fib0(20): ', fib0(20));//fib0(20):  6765
console.timeEnd('fib0');//fib0: 1.907ms

3.递归优化

从2可以看出，计算fib(n)的时候，其他会被计算多次，则可以利用缓存的思想，用空间换速度（n越大，计算的次数是成指数倍增长的，则用空间换速度是完全是情理之中的）。
利用一个cache对象，缓存已经计算的结果。
当n = 30时:
fib0: 9.991ms
fib1: 0.186ms

console.time('fib1')
const cache = {};
function fib(n) {
  if (n < 2) {
      return n;
  }
  // 【注意】：先进行0 1 1 2 的计算，如果在缓存中，则直接进行返回，否则，则进行存储；
  if (cache[n] === undefined) {
    cache[n] = fib(n - 2) + fib(n - 1);
  }
  return cache[n]
}
fib(20);
console.timeEnd('fib1');//fib1: 0.103ms - 可见该优化很有必要。