剑指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);