Sie befinden sich hier: Termine » Prüfungsfragen und Altklausuren » Prüfungen im Bachelor-Studium (1. - 5. Semester) » aud » Forendiskussionen   (Übersicht)

Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen gezeigt.

Link zu dieser Vergleichsansicht

Both sides previous revision Vorhergehende Überarbeitung
pruefungen:bachelor:aud:loesungws16 [22.05.2019 14:32]
SpeedyGonzalez
pruefungen:bachelor:aud:loesungws16 [02.08.2019 09:32] (aktuell)
dom Aufgabe 4 angepasst
Zeile 100: Zeile 100:
  return 1;  return 1;
  }  }
- int sum = 0; //sum muesste eigentlich ein long sein + long sum = 0;  
- for (int i = 0; i < n; i++){ + for (int i = 0; i < n; i++) { 
- sum = sum + countNaive(i) * countNaive(n-1-i);​+ sum += countNaive(i) * countNaive(n-1-i);​
  }  }
  return sum;  return sum;
 } }
 +</​code>​
 +
 +**b)**
  
 +<​code=java>​
 long countDP (int n) { long countDP (int n) {
- long[] mem = new long[n+1];​ + long[] mem = new long[n + 1]; 
- mem[0] = mem[1] = 1;+ mem[0] = 1; 
 +        ​mem[1] = 1; 
 +        ​
  return countDPH(mem,​ n);  return countDPH(mem,​ n);
 } }
  
 private long countDPH (long[] mem, int n) { private long countDPH (long[] mem, int n) {
 +        // Lookup
  if (mem[n] != 0) {  if (mem[n] != 0) {
  return mem[n];  return mem[n];
  } else {  } else {
- int sum = 0; + long sum = 0; 
- for (int i = 0; i < n; i++){ + for (int i = 0; i < n; i++) { 
- sum = sum + countDPH(mem,​ i) * countDPH(mem,​ n-1-i);+ sum ​+= countDPH(mem,​ i) * countDPH(mem,​ n-1-i);
  }  }
 +                // Memoization
  mem[n] = sum;  mem[n] = sum;
  return sum;  return sum;
  }  }
-} 
- 
-long countIter (int n) { 
- ... 
- for (int k = 2; k < n+1; k++){ 
- for (int i = 0; i < n; i++){ //Meiner Meinung nach mus hier unbedingt!!! i < k stehen, sonst rechnet man mit unbefuellten werten (buttom up beachten!) 
- mem[k] = mem[k] + mem[i] * mem[n-1-i]; //hier auch mem[k-1-i]! 
- } 
- } 
- ... 
 } }
 </​code>​ </​code>​
Zeile 141: Zeile 139:
 <code java> <code java>
 private long countDPH (long[] mem, int n) { private long countDPH (long[] mem, int n) {
- if (mem[n] != 0) {+ // Lookup 
 +        ​if (mem[n] != 0) {
  return mem[n];  return mem[n];
  }  }
- for (int i = 0; i < n; i++){+ for (int i = 0; i < n; i++) { 
 +            // Berechnung + Memoization
             mem[n] += countDPH(mem,​ i) * countDPH(mem,​ n-1-i);             mem[n] += countDPH(mem,​ i) * countDPH(mem,​ n-1-i);
  }  }
Zeile 150: Zeile 150:
 } }
 </​code>​ </​code>​
 +
 +**c)**
 +
 +<​code=java>​
 +long countIter (int n) {
 + ...
 + for (int k = 2; k < n+1; k++) { // for-Schleife fuer bottom-up
 + for (int i = 0; i < k; i++) {
 + mem[k] = mem[k] + mem[i] * mem[k-1-i];
 + }
 + }
 + ...
 +}
 +</​code>​
 +
  
 ==== Aufgabe 5 Graphen ==== ==== Aufgabe 5 Graphen ====