剑指Offer-斐波那契数列
题目描述:
大家都知道斐波那契数列,现在要求输入一个整数n,请你输出斐波那契数列的第n项(从0开始,第0项为0)。n<=39
效率很低的解法:
很多C语言教科书在讲递归函数的时候,都会用Fibonacci作为例子,很多人看到这道题会心生窃喜,因为递归方法很简单:
public int Fibonacci(int n) {
if (n <= 0) {
return 0;
}
if (n == 1) {
return 1;
}
return Fibonacci(n-1) + Fibonacci(n-2);
}
上述递归解法有严重的效率问题。我们以求解f(10)为例来分析递归求解过程。想求得f(10),需要先得到f(9)和f(8)。同样,想求得f(9),需要先求f(8)和f(7),用树形结构来表示依赖关系,如图:
这棵树很多节点是重复的,而且重复结点数会随着n的增大而急剧增加,意味着计算量会随着n的增大而急剧增大。
实用解法:
其实改进方法并不复杂。只需要想办法避免重复计算就OK了。我们可以把已经得到的数列中间项保存下来,下次需要计算的时候先查找一下。
更简单的方法是从下往上计算,根据f(0)和f(1)计算f(2),再根据f(1)计算f(2)计算f(3),以此类推 就可以得到第n项了。时间复杂度为O(n).
代码实现:
public int Fibonacci(int n) {
if (n <= 0) {
return 0;
}
if (n == 1) {
return 1;
}
//第一个数
int first = 0;
//第二个数
int second = 1;
//第n项的和
int Sum = 0;
for (int i = 2; i <= n; i++) {
Sum = first + second;
first = second;
second = Sum;
}
return Sum;
}
除了直接要求编程实现斐波那契数列之外,还有不少题可以看成是斐波那契数列的应用,如:
题目描述:
一只青蛙一次可以跳上1级台阶,也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法(先后次序不同算不同的结果)。
解题思路:
如果只有一个台阶,显然只有一种跳法。如果有2个台阶,那就有两种跳法了:一种是分两次跳,每次跳一级,另一种就是一次跳两级。
接下来再讨论一般情况。我们把n级台阶时的跳法看成是n的函数,即为f(n).当n>2时,第一次跳的时候就有两种不同的选择:一是第一次只跳1级,此时跳法数目等于后面剩下的n-1级台阶的跳法数目,即为f(n-1);另一种是选择第一次跳2级,此时跳法数目等于后面剩下的n-2级台阶的跳法数目,即为f(n-2)。因此n级台阶的不同跳法的总数f(n)=f(n-1)+f(n-2)。所以又是斐波那契数列。
代码实现:
public int JumpFloor(int target) {
if (target == 0) {
return 0;
}
if (target == 1) {
return 1;
}
if(target == 2){
return 2;
}
int first = 1;
int second = 2;
int Sum = 0;
for (int i = 3; i <= target; i++) {
Sum = first + second;
first = second;
second = Sum;
}
return Sum;
}
题目变形:
一只青蛙一次可以跳上1级台阶,也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
解题思路:
延续上一题的思路,现在可以一次跳1阶,一次跳2阶…一次跳n阶。由于每次可以跳1-n的任意阶数,因此无论有多少阶,都可以一次跳完,为了表示方便,我们将一次性跳完的情况设为F(0),当n=1时,只能有一种情况,F(1) = 1。当n=2时,可以每次跳1阶,也可以一次跳两阶,则F(2) = 2。
假设现在又n阶,可以跳完n阶的情况分别是:一次跳完F(0);先跳一步F(1),后面还有F(n-1)种跳法;或者先跳两步F(2),后面还有F(n-2)种跳法。依次类推,第一次跳出n阶后,后面还有 F(n-n)中跳法。可以得出:
F(n) = F(n-1)+F(n-2)+F(n-3)+…+F(0)
代码实现:
public int JumpFloorII(int target) {
if(target==0||target==1)
return 1;
if(target==2)
return 2;
int sum = 0;
for(int i=0;i<target;i++){
sum += JumpFloorII(i);
}
return sum;
}