面试题9-斐波那契数列
2017-09-03 本文已影响65人
小庄bb
题目要求
求斐波那契数列的第n项。
题目解析
思路一：
- 分析
斐波那契数列的第n项的计算过程是一个标准的递归 。
- 代码段
public static int getValue(int n) throws Exception {
if(n < 0) {
throw new Exception("输入参数小于0 ，不合法的输入") ;
}
if(n <= 1) {
return (n==1) ? 1: 0 ;
}
return getValue( n-1 ) + getValue( n-2 ) ;
}
思路二：
- 分析
斐波那契数列的第n项的计算过程是一个标准的递归 ， 但是由于递归对内存的需求非常大，所以我们要进行以下优化。新建一个数组对计算结果进行存储，下次计算式，先在数组中进行查询，若不存在再进行计算。
- 代码段
public static int getValue1(int n) throws Exception {
if(n < 0) {
throw new Exception("输入参数小于0 ，不合法的输入") ;
}
if(n <= 1) {
return (n==1) ? 1: 0 ;
}
if(result.get(n)!=null) {
return result.get(n) ;
}else {
result.put(n, getValue( n-1 ) + getValue( n-2 )) ;
}
return result.get(n) ;
}
测试代码
public static void main(String[] args) {
try {
System.out.println("未优化");
long curTime = System.nanoTime() ;
System.out.println(getValue(5));
System.out.println(System.nanoTime() - curTime);
System.out.println("-----------------------------------");
System.out.println("优化");
curTime = System.nanoTime() ;
System.out.println(getValue1(5));
System.out.println(System.nanoTime() - curTime);
System.out.println("-----------------------------------");
System.out.println("未优化");
curTime = System.nanoTime() ;
System.out.println(getValue(30));
System.out.println(System.nanoTime() - curTime);
System.out.println("-----------------------------------");
System.out.println("优化");
curTime = System.nanoTime() ;
System.out.println(getValue1(30));
System.out.println(System.nanoTime() - curTime);
System.out.println(getValue1(-1));
} catch (Exception e) {
e.printStackTrace();
}
}
运行结果
未优化
5
51786
优化
5
176816
未优化
832040
10688252
优化
832040
8065874
java.lang.Exception: 输入参数小于0 ，不合法的输入
at 斐波那契数列.Demo.getValue1(Demo.java:41)
at 斐波那契数列.Demo.main(Demo.java:91)
题目扩展：
青蛙跳台阶问题：
- 题目要求：
一只青蛙一次可以跳一个台阶，也可以跳两个台阶，求该青蛙要跳上n跳台阶有多少种方法。 - 题目分析：
首先我们考虑最简单的情况，当只有一阶台阶时，只有一种情况，有两阶台阶时，有两种情况，第一次跳一阶，第二次跳一阶。或者一次跳两阶。然后我们来看当有n阶台阶时，假设一共有f(n)种情况，那么第一次跳有两种选择，跳一阶，那么剩下的台阶的情况数量则为f(n-1)种。如果第一次跳两阶，那么剩下的阶数的情况就是f(n-2)。这个时候我们就可以简单的看出它就是一个斐波那契数列问题。
摆方块儿问题
有一个28的大方框和一个21的小方框，同样的我们可以吧第一次放的条件分类。如果把第一块横着放，那么下面的那个也必须横着放，也就是不确定的是剩下的26，如果第一块竖着放，那么我们不能确定的就是剩下的27。并且当只有21的方格时只有一种方法，只有22方格时，只有两种方法。那我们可以将问题转化为斐波那契数列，解决问题。
青蛙跳台阶问题再扩展
- 题目要求：
一只青蛙一次可以跳1-n个台阶。求该青蛙要跳上n跳台阶有多少种方法。 - 题目分析：
已知：当如上题条件。那么f(n) = f(1) + f(2) + ...... + f(n-1) + 1;
且：
f(n) = f(1) + f(2) + ...... + f(n-1) + 1 ;
f(n - 1 ) = f(1) + f(2) + ...... + f(n-2) + 1 ;
f(n) = 2 f(n-1) ;
那么可以得出f(n) = 2^(n-1)
