Du befindest dich hier: FSI Informatik » Prüfungsfragen und Altklausuren » Prüfungen im Bachelor-Studium (1. - 5. Semester) » aud » Forendiskussionen   (Übersicht)

Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

Link zu der Vergleichsansicht

Beide Seiten, vorherige ÜberarbeitungVorherige Überarbeitung
pruefungen:bachelor:aud:loesungws16 [22.05.2019 12:32] SpeedyGonzalezpruefungen:bachelor:aud:loesungws16 [02.08.2019 07:32] (aktuell) – Aufgabe 4 angepasst dom
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 ====