剑指offer面试题9-斐波那契数列问题

发表于 | 分类于 ，

问题描述

写一个函数，输入n，求斐波那契（Fibonacci）数列第n项。
斐波那契数列定义为：f(n) = f(n-1) + f(n-2) (n>1) ,其中f(0)=0, f(1)=1。

递归解法

斐波那契数列是一个典型的递归解法，代码如下：

1
2
3
4
5
6
7
8
9
10
public int Fibonacci(int n) {
	if (n == 0) {
		return 0;
	}

	if (n == 1) {
		return 1;
	}
	return Fibonacci(n - 1) + Fibonacci(n - 2);
}

以上代码虽然可以计算出第n项，但存在两个问题：

  1. 计算f(n)时需要递归计算f(n-1)和f(n-2)，而计算f(n-1)时又要递归计算f(n-2)，f(n-2)重复递归计算，同理f(n-3)…f(2)也要重复递归计算，大大浪费了时间和空间。
  2. 当n太大时，递归层次太深，耗时较长且易导致stackoverflow。

算法优化

上面代码存在的问题是每次都进行了大量的重复递归计算，那就想办法减少这部分计算。

方法一

可以通过将中间计算结果保存到数组，每次计算时都从数组中查找结果即可。例如，将中间结果保存到数组array[]中，array[n]表示第n项。那么，在计算f(n）时，首先递归计算f(n-1),在计算过程中就可以把中间结果保存到数组中，那么计算f(n-2)时，可以直接从数据中取出对应的值，不需要重复递归调用了。

方法二

另外一种方法是从小到大的方式计算。首先根据f(0)、f(1)计算f(2), 再根据f(1)、f(2)计算f(3)，再根据f(2)、f(3)计算f(4)，依次类推，直到计算出f(n)。

也就是说在每次计算中，需要保存上次计算的结果，代码如下：

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
public int Fibonacci(int n) {
	if (n < 0) {
		return -1;
	}
	int f1 = 0;
	int f2 = 1;
	int f3 = 1;

	if (n == 0) {
		return f1;
	}

	if (n == 1) {
		return f2;
	}

	while (n>=2) {
		f3 = f1 + f2;
		f1 = f2;
		f2 = f3;
		n--;
	}

	//用两个变量的方法，返回值需返回f2
//	while(n>=2) {
//		f2 = f2 + f1;
//		f1 = f2 - f1;
//		n--;
//	}
	
	return f3;
}

问题扩展：跳台阶

问题描述

一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

解法

首先从最简单的场景考虑，对于一级台阶来说，有一种跳法；对于一个二级台阶来说，有两种跳法，先跳一级在跳一级或者直接跳两级。

对于一个n级台阶来说，第一跳有两种选择，先跳一个台阶或者两个台阶。若先跳一个台阶，跳法数则等于剩下n-1个台阶的跳法；若先跳两个台阶，跳法数则等于剩下n-2个台阶的跳法数。 因此，n台阶跳法数等于n-1台阶跳法数与n-2台阶跳法数之和。

以此类推，n-1台阶跳法数等于n-2台阶跳法数与n-3台阶跳法数之和，n-2台阶跳法数等于n-3台阶跳法数与n-4台阶跳法数之和，…，3台阶跳法数等于2台阶跳法数与1台阶跳法数之和。

因此，一个n级台阶的跳法数也可以看作是一个斐波那契数列。

假设f(n)表示n级台阶的跳法，则有f(n) = f(n-1) + f(n-2) (n>2)（其中，f(1)=1, f(2)=2）。

代码

代码和求斐波那契数列第n项大体相同，不同之处在于前两项初始值不同。

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
public int Fibonacci(int n) {
	if (n <= 0) {
		return -1;
	}
	int f1 = 1;
	int f2 = 2;
	int f3 = 1;

	if (n == 1) {
		return f1;
	}

	if (n == 2) {
		return f2;
	}

	while (n>=3) {
		f3 = f1 + f2;
		f1 = f2;
		f2 = f3;
		n--;
	}
	
	return f3;
}

问题扩展：变态跳台阶

问题描述

一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

解法

记f(n)为n级台阶跳法总数，对于一个n级台阶来说，第一跳有n种跳法。

当第一跳跳1个台阶时，跳法数则为n-1级台阶跳法数即f(n-1);
当第一跳跳2个台阶时，跳法数则为n-2级台阶跳法数即f(n-2)；
当第一跳跳3个台阶时，跳法数则为n-2级台阶跳法数即f(n-3)。

依此类推，则有如下公式：

  • f(n) = f(n-1) + f(n-2) + f(n-3) + …. + 1。
  • f(n-1) = f(n-2) + f(n-3) + …. + 1。

两个公式相减可得：f(n) = 2*f(n-1)。

代码

根据公式，可有如下代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public int JumpFloorII(int n) {
	if (n < 1) {
		return 0;
	}

	if (n == 1) {
		return 1;
	}

	// f(n)=2*f(n-1)
	int f1 = 1;
	int f2 = 0;
	while (n >= 2) {
		f2 = 2 * f1;
		f1 = f2;
		n--;
	}
	return f2;
}

根据数学归纳法可得：f(n) = 2^(n-1)。 代码可以减少为一行：return 1 << (n - 1);