你的位置:首页 > Java教程

[Java教程]递归算法及优化


 1 package interview; 2 //有一个斐波那契数列计算的函数,最前面的k个数为1,后面的没一位是前k位之和,例如k=4,该函数 3 //该函数返回值为1,1,1,1,4,7,13,25,49 4 public class RecursiveOptimize { 5   static int fib_k(int n,int k) { 6     if(n<k)  7       return 1; 8     int result = 0; 9     for(int i=0;i<k;i++){10       result += fib_k(n-i-1,k);11      }12     return result;13   }14   static int fib_k_optimize(int n,int k) {15     if(n<k)16       return 1;17     int[] fib = new int[n+1];18     for(int i=0;i<k;i++){19       fib[i]=1;20     }21     for(int i=k;i<=n;i++) {22       int result = 0;23       for(int j=0;j<k;j++){24         result += fib[i-j-1];25       }26       fib[i]=result;27     }28     return fib[n];29   }30   public static void main(String[] args) {31     long start = System.nanoTime();32     for(int i=0;i<20;i++){33       System.out.print(fib_k(i,4)+" ");34     }35     long end = System.nanoTime();36     System.out.println("\n"+(end-start));37     38     //===================================39     start = System.nanoTime();40     for(int i=0;i<20;i++){41       System.out.print(fib_k_optimize(i,4)+" ");42     }43     end = System.nanoTime();44     System.out.println("\n"+(end-start));45   }46   47 }