用Java实现斐波那契数列

斐波那契数列

如下数列：0、1、1、2、3、5、8、13、21、34......从第三个数开始，每个数都等于前两个数字的和。

今天又看到了斐波那契数列，心想实现这个数列的算法应该是十分简单的，于是随手写了个程序，跑了一下，boom～出现了意想不到的情况，主要是打印前100个斐波那契数的时候，出现负数，而且计算时间过长。先贴个控制台：

分析：斐波那契数超过了数据类型的阈值，算法性能不好。

改进：切换成精度更高的数据类型，并限制打印的数字的范围大小，改进算法。

贴个满足需求的源码：

package math; import org.junit.Test; /** * 斐波那契数列 * @author jsyuger * 如下数列：0、1、1、2、3、5、8、13、21、34...... */ public class FbnqArray { //斐波那契数列具体实现 public long fbnq(int i){ if(i<1 || i>92) return 0 ; //n最大为92，否则超出 Long.MAX_VALUE if(i==1) return 0 ; if(i==2) return 1 ; return fbnq(i-1) + fbnq(i-2); } @Test public void test(){ //打印前10个斐波那契数列的元素 for(int i = 1 ;i<=10 ; i++) System.out.println(fbnq(i)); System.out.print(Long.MAX_VALUE); //Long类型的最大值 } }

以上这个算法采用的是递归的实现方式，该算法计算的时候是非常消耗CPU的，而且需要跑很久。每次计算都需要往回递推到第一个和第二个斐波那契数，于是看了一下网上的其他实现方法，确实有更好的解决方案，以下采用数组缓存的方法，该方法要比原始的递归性能上要好很多：

static long[] l = new long[93]; //定义边界 static { l[1] = 1; //初始化l[1],这时数组非0即1 } //带有数组缓存的方法，比普通递归方法性能好很多 public static long fibArray(int num) { if(num < 1 || num > 92) return 0; if(l[num] == 0) l[num] = l[num-1] + l[num-2] ; return l[num]; }