数据结构之斐波那切数列

发表于 更新于 分类于
学习笔记

英文: Fibonacci Number
数列规则: 0 1 1 2 3 5 8 13 21 …

f(n)=f(n-1)+f(n+1)
f(1)=1
f(0)=0

1
2
3
4
5
6
7
8
9
private int f(int n) {
  if (n == 0) {
    return 0;
  }
  if (n == 1) {
    return 1;
  }
  return f(n - 1) + f(n - 2);
}

由上述公式可得:


该图中可以看出, f(4)会计算1次, f(3)会计算2次, f(2)会计算3次, f(1)会计算2次;
实际上, 一个值已经计算过了, 我们就可以不需要重复计算多次了, 因此优化之后的结果如下:(以空间换时间)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
private Integer f(Integer n, Map<Integer, Integer> maps) {
  // 首先传入一个空Map, key是计算的位数, value是当前位数的实际值
  for (Integer i : maps.keySet()) {
    if (Objects.equals(n, i)) {
      return maps.get(n);
    }
  }
  if (n == 0) {
    return 0;
  }
  if (n == 1) {
    return 1;
  }
  Integer ans = f(n - 1, maps) + f(n - 2, maps);
  maps.put(n, ans);
  return ans;
}

最终方法: 迭代(for/while), 有点耗时短, 效率高;可以避免递归方法计算的数字过大, f()嵌套过度导致爆栈的问题

1
2
3
4
5
6
7
8
9
private int f(int n) {
  int a = 0;
  int b = 1;
  for (int i = 0; i <= n; i++) {
    b = a + b;
    a = b - a;
  }
  return a;
}

公式图解(红色:移动, 绿色:相加)