闲来无事，研究了一下斐波那契数列的不同解法，借鉴了网上的一些思路，比如通项公式和矩阵法，并用JavaScript将其实现：

第一种，递归法：

1
2
3
4
const fibs = n => {
  if (n === 1 || n === 2) return 1;
  else return fibs(n - 1) + fibs(n - 2);
};

第二种，递归+备忘录

1
2
3
4
5
6
7
8
9
10
const dict = {};
const fibs = (n) => {
  if (n === 1 || n === 2) {
    return 1;
  }
  if (!dict[n]) {
    dict[n] = fibs(n - 1) + fibs(n - 2);
  }
  return dict[n];
};

第三种，动态规划数组法：

1
2
3
4
5
6
7
8
9
10
const fibs = n => {
  const dp = [1, 1];
  if (n === 1 || n === 2) {
    return 1;
  }
  for (let i = 2; i < n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2];
  }
  return dp[n - 1];
};

第四种，中间值法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
const fibs = n => {
  if (n === 1 || n === 2) {
    return 1;
  }
  let ppre = 1;
  let pre = 1;
  let tmp;
  for (let i = 2; i < n; i++) {
    tmp = ppre + pre;
    ppre = pre;
    pre = tmp;
  }
  return tmp;
};

第五种，尾递归

1
2
3
4
5
6
7
8
const fibs = n => fibsTailRecursion(1, 1, n);

const fibsTailRecursion = (ppre, pre, n) => {
  if (n === 1) {
    return ppre;
  }
  return fibsTailRecursion(pre, pre + ppre, n - 1);
};

第六种，通项公式：

1
2
3
4
5
6
const fibs = n =>
  Math.round(
    (Math.sqrt(5) / 5) *
      (Math.pow((1 + Math.sqrt(5)) / 2, n) -
        Math.pow((1 - Math.sqrt(5)) / 2, n))
  );

第七种，矩阵乘法：

[[0,1],[0,0]] * [[0,1],[1,1]]^n-1 = [[F(n-1),F(n)],[0,0]]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
// 矩阵乘法 m*n n*k = m*k
const matrixMultiply = (arr1, arr2) => {
  let result = [];
  for (let i = 0; i < arr1.length; i++) {
    let current = [];
    for (k = 0; k < arr1.length; k++) {
      // 累加
      let sum = 0;
      for (let j = 0; j < arr1[i].length; j++) {
        sum = sum + arr1[i][j] * arr2[j][k];
      }
      current.push(sum);
    }
    result.push(current);
  }
  return result;
};

const fibs = n => {
  let result = [
    [0, 1],
    [0, 0]
  ];
  const arr = [
    [0, 1],
    [1, 1]
  ];
  for (let i = 0; i < n - 1; i++) {
    result = matrixMultiply(result, arr);
  }
  return result[0][1];
};