剑指offer系列之斐波那契数列
代码
package com.study;
/*
* 求斐波那契数列第n个数字
* */
public class suanfa7 {
/*最原始的递归版,思路简洁,但是如果输入参数较大,会造成栈的深度太深,运行会很慢*/
public static int Fibonacci1(int num) {
if(num <= 1)
return num;
else
return Fibonacci1(num - 1) + Fibonacci1(num - 2);
}
/*第二种方法,算法复杂度为O(n),利用一种迭代的思路,避免了递归的入栈等操作,提高了时间效率
* 但是如果数字超过了30可能就需要把返回类型改成long了*/
public static int Fibonacci2(int num) {
if(num <= 1)
return num;
else {
int sum = 1;
int preNum = 1;
int prepreNum = 0;
int i = 2;
while(i < num) {
prepreNum = preNum;
preNum = sum;
sum = prepreNum + preNum;
i++;
}
return sum;
}
}
public static void main(String[] args) {
System.out.println(Fibonacci2(10));
}
}
<pre>
备注:
1.斐波那契数列虽然看似简单,但是要考虑清楚实际的情况,要不断优化算法的复杂度。
2.另外,对于迭代这种思路,以前很没有感觉,就觉得没有一种属于自己的快速的方法,可以看出迭代量。突然想到,调试的时候,观察变量的时候,经常用列表的方法去看值,直观对比,那么写程序的时候不妨也列表试试,果然相当有效果,迭代量是什么一目了然。
之后只要顺着思路写程序即可。
3.斐波那契数列的应用场景很多:
典型的比如:青蛙跳台阶问题,矩形覆盖问题等。解决这种问题的思路关键在于看能否找到一种递归关系
f(n) = f(n-1) + f(n - 2)
如果找到这种递推关系,则很容易想到是斐波那契数列。
以后遇到数列题,一般首先应该想到是斐波那契数列 。