Sitzung: Jeden Freitag in der Vorlesungszeit ab 16 Uhr c. t. im MAR 0.005. In der vorlesungsfreien Zeit unregelmäßig (Jemensch da?). Macht mit!

Javakurs/Übungsaufgaben/Rekursion vs. Iteration/Musterlösung

< Javakurs‎ | Übungsaufgaben‎ | Rekursion vs. Iteration
Version vom 22. März 2010, 11:28 Uhr von 130.149.24.73 (Diskussion) (Die Seite wurde neu angelegt: „<pre> public class RekursionVsIteration { public static void main( String args[] ) { int[] testValues= {5, 10, 15, 20, 30, 40}; timeTest( testValues);...“)
(Unterschied) ← Nächstältere Version | Aktuelle Version (Unterschied) | Nächstjüngere Version → (Unterschied)
public class RekursionVsIteration {

  public static void main( String args[] ) {

    int[] testValues= {5, 10, 15, 20, 30, 40};
    timeTest( testValues);

  }
 
  /* calculates FibonacciNumbers */
  public static int fibonacciRek( int n ) {

    int result;

    if (n <= 1) {
       if (n == 1) {
          result = 1;
       } else if (n == 0) {
          result= 0;    
       } else {
          System.out.println("Fibonacci numbers undefined for "+
                             "negative values."                );
          result = -1;
       }
    } else {
      result= fibonacciRek(n - 1) + fibonacciRek(n - 2);
    }
    return result;
  }

  public static int fibonacciIte (int n) {

    int result;

    if (n <= 1) {
      if (n == 1) {
        result = 1;
      } else if (n == 0) {
        result= 0;    
      } else {
        System.out.println("Fibonacci numbers undefined for "+
                           "negative values."                );
        result = -1;
      }
    } else {

      /* n+1 because in the n-th entry is the n-th 
       * fibonacci number */
      int[] predecessors= new int[n+1];
  
      predecessors[0]=  0;
      predecessors[1]=  1;

      for ( int i= 2; i < predecessors.length; i++ ) {
        predecessors[i]= predecessors[i-1] + predecessors[i-2];
      }

      result= predecessors[n];
    }

    return result;
  }

  public static void timeTest(int[] values){
    long before;
    long after;

    /*recursion time test*/
    before = System.currentTimeMillis();

    for ( int i=0; i< values.length; i++) {
 
     // fibonacciRek(values[i]);
      System.out.print("f(" +values[i] + ")= ");
      System.out.println( fibonacciRek(values[i]) );
    }

    after = System.currentTimeMillis();
    System.out.println("Rekursion benötigt: " + (after - before) + " ms");

    /*iteration time test*/
    before = System.currentTimeMillis();

    for ( int i=0; i< values.length; i++) {
      // fibonacciIte(values[i]);
      System.out.print("f(" +values[i] + ")= ");
      System.out.println( fibonacciIte(values[i]) );
    }

    after = System.currentTimeMillis();
    System.out.println("Iteration benötigt: " + (after - before) + " ms");

  }

}