回朔法(Backtracking)求所有數字的排列

public class NumberPermutation {

    public static void main(String[] args){
      /*
      * 123,132,213,231,312,321
      */
     int[] numbers = new int[] {1,2,3};
     backTrackPermutation(numbers ,0 ,2);
    }
    
    private static void backTrackPermutation(int[] numbers,int startIdx , int endIdx){
 
 if(startIdx == endIdx){
     printArray(numbers);
 }else{
     for(int j = startIdx; j <= endIdx ; j++){
  swap(numbers, startIdx , j);
  backTrackPermutation(numbers ,startIdx+1, endIdx);
  swap(numbers, startIdx , j);
     }
     
 }
 
    }
    
    private static void swap(int[] numbers,int idx1 , int idx2){
 int temp = numbers[idx1];
 numbers[idx1] = numbers[idx2];
 numbers[idx2] = temp;
    }
    
    private static void printArray(int[] numbers){
 for(int i = 0 ; i < numbers.length ; i++){
     System.out.print(numbers[i]);
 }
 System.out.println();
    }
    
}

用動態規劃演算法計算費波南西數列

動態規劃比遞迴寫法快好多.

public static void main(String[] args){
 long start = System.currentTimeMillis();
 System.out.println(new Fib().calFib(40));
 long end = System.currentTimeMillis();
 System.out.println("Dynamic Programming :" + (end - start) +" million seconds");
 start = System.currentTimeMillis();
 System.out.println(new Fib().recurFib(40));
 end = System.currentTimeMillis();
 System.out.println("Recurrence :" + (float)(end - start) +" million seconds");
 
    }
    
    int calFib(int toNumber){
  int[] value = new int[100];
  value[1] = 1;
  for(int i = 1; i <= toNumber ; i++){
      value[i+1] = value[i] + value[i-1];
  }
  return value[toNumber];
    }
    
    int recurFib(int toNumber){
 if(toNumber == 0){
     return 0;
 }else if(toNumber == 1){
     return 1;
 }else{
     toNumber -= 1;
     return recurFib(toNumber)+recurFib(toNumber-1);
 }
    }