利用数组快速实现斐波那契数
?
? ? ?斐波那契数一般都是采用递归来予以实现的，但是这存在一个严重的问题——即使在相对较快的计算机上，计算F40需要大约一分钟的时间，就运行时间而言，这是很荒谬的，因为基本运算只需要39次加法。
? ? ?根本问题是：递归历程执行了冗余计算，为了计算fib（n） ，我们递归的计算fib（n-1）。当递归使用另一个递归调用，我们计算fib（n-2）。不过，在计算fib（n-1）的过程中，我们早已计算了 fib（n-2），所以调用fib（n-2）是一种浪费，是冗余计算。对于N=40，F40=102334155，但是递归调用的总次数超过了300 000 000次！！！
? ? 这里我采用数组实现斐波那契，速度相当的快，代码如下：相互运算时间的比较代码我就不具体贴出来了，很简单。有兴趣的可以用递归的方法与我的方法进行比较，结果一目了然。
?
/** * 使用数组利用循环快速实现斐波那契数 * @author jw * */public class Ftest { public static long fib(int n){ if(n<2){ System.out.println("必须输入大于2的数字"); return 0; } else{ int[] a=new int[n+1]; a[0]=0; a[1]=1; for(int i=2;i<=n;i++){ a[i]=a[i-1]+a[i-2]; } return a[n]; } } public static void main(String[] args){ System.out.println(fib(40)) ; System.out.println(fib(1)) ; System.out.println(fib(2)) ; System.out.println(fib(10)) ; System.out.println(fib(1000)) ; }}