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: Unterschied zwischen den Versionen

(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);...“)
 
K (fix alignment)
 
(Eine dazwischenliegende Version von einem anderen Benutzer wird nicht angezeigt)
Zeile 1: Zeile 1:
 
<pre>
 
<pre>
public class RekursionVsIteration {
+
public class RecursionVsIteration {
 +
public static void main(String args[]) {
 +
int[] testValues = { 5, 10, 15, 20, 30, 40 };
 +
timeTest(testValues);
 +
}
  
  public static void main( String args[] ) {
+
/* 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;
 +
}
  
    int[] testValues= {5, 10, 15, 20, 30, 40};
+
public static int fibonacciIte(int n) {
    timeTest( testValues);
+
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;
  /* calculates FibonacciNumbers */
+
long after;
  public static int fibonacciRek( int n ) {
+
// recursion time test
 
+
before = System.currentTimeMillis();
    int result;
+
for (int i = 0; i < values.length; i++) {
 
+
// fibonacciRek(values[i]);
    if (n <= 1) {
+
System.out.print("f(" + values[i] + ")= ");
      if (n == 1) {
+
System.out.println(fibonacciRek(values[i]));
          result = 1;
+
}
      } else if (n == 0) {
+
after = System.currentTimeMillis();
          result= 0;   
+
System.out.println("Rekursion benötigt: " + (after - before) + " ms");
      } else {
+
// iteration time test
          System.out.println("Fibonacci numbers undefined for "+
+
before = System.currentTimeMillis();
                            "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");
 
 
 
  }
 
  
 +
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");
 +
}
 
}
 
}
 
</pre>
 
</pre>

Aktuelle Version vom 4. März 2013, 13:41 Uhr

public class RecursionVsIteration {
	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");
	}
}