斐波那契数列 -- java
题目一
题目描述
求斐波那契数列数列的第n项。
写入一个函数,输入n,求斐波那契(Fibonacci)数列的第n项。斐波那契数列的定义如下:
f(n) = 0; n=0
f(n) = 1; n=1
f(n) = f(n-1) + f(n-2); n>1
解题思路
最简单的利用递归
大家都能想到,但是没有考虑时间复杂度
改进的循环
由于上面的方面很慢,是因为重复的计算太多(例如,计算 f(10) 需要计算 f(9) 和 f(8),计算 f(9) 需要计算 f(8) 和 f(7),可以看到 f(8) 被重复计算了。),所以我们要避免重复计算,我们可以把已经计算得到的中间项保存起来,在下次需要计算的时候先查找一下,这样就可以避免重复计算了。
代码
递归
public class Fibonacci {
// 递归方式
public static long fibonacci(int n) {
if (n == 0) {
return 0;
}
if (n == 1) {
return 1;
}
return fibonacci(n-1) + fibonacci(n-2);
}
// 测试
public static void main(String[] args) {
System.out.println(fibonacci(10));
}
}
循环
public class Fibonacci {
// 循环方式
public static long fibonacci(int n) {
if (n < 2) {
return n;
}
long pre1 = 1L;
long pre2 = 0L;
long fib = 0L;
for (int i = 2; i <= n; i++) {
fib = pre1 + pre2;
pre2 = pre1;
pre1 = fib;
}
return fib;
}
// 测试
public static void main(String[] args) {
System.out.println(fibonacci(10));
}
}
题目二
题目描述
一只青蛙一次可以跳上1级台阶,也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法(先后次序不同算不同的结果)。
解题思路
与斐波那契数列相同,但是还是需要分析一下:
先分析最简单的情况。如果只有1级台阶,那显然只有一种跳法。如果有2级台阶,那就有两种跳法,分为每次跳1级,和一次跳两级。
再讨论一般情况,我们把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)。
我们马上就可以看出这就是斐波那契数列了。
代码
首先根据f(1)和f(2)算出f(3),再根据f(2)和f(3)算出f(4)……以此类推就可以算出第n项了。
public class Fibonacci {
// 循环方式
public static long fibonacci(int n) {
if (n <= 2) {
return n;
}
long pre1 = 2L;
long pre2 = 1L;
long fib = 0L;
for (int i = 3; i <= n; i++) {
fib = pre1 + pre2;
pre2 = pre1;
pre1 = fib;
}
return fib;
}
// 测试
public static void main(String[] args) {
System.out.println(fibonacci(3));
}
}
补充
通常基于递归实现的代码比基于循环实现的代码要简洁很多,更加容易实现。如果面试官没有特殊要求,则应聘者可以采用递归的方法编程,但是我们还是应该以时间复杂度为首要考虑。
来自:
《剑指Offer》
Coding-Interviews/斐波那契数列.md at master · todorex/Coding-Interviews