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
Nächste Überarbeitung		Vorherige Überarbeitung
pruefungen:bachelor:aud:loesungws16 [02.04.2019 14:33] – Nico Hambauerpruefungen:bachelor:aud:loesungws16 [02.08.2019 07:32] (aktuell) – Aufgabe 4 angepasst dom
Zeile 86: Zeile 86:
 int b = ((int) (x/Math.pow(10,i)) % 10) + 9; int b = ((int) (x/Math.pow(10,i)) % 10) + 9;
 ... ...
 +</code>
 +
 +oder einfacher:
 +<code java>
 +...
 +bs[b + 9].addLast(x);
 </code> </code>
 ==== Aufgabe 4 Dynamische Programmierung ==== ==== Aufgabe 4 Dynamische Programmierung ====
Zeile 94: 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 ArrayIndexOutOfBounds Exception! 
- mem[k] = mem[k] + mem[i] * mem[n-1-i]; //hier auch mem[k-1-i]! 
- } 
- } 
- ... 
 } }
 </code> </code>
Zeile 135: 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 144: 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 ====
Zeile 191: Zeile 212:
  quelleSeite.add(v);  quelleSeite.add(v);
  senkeSeite.remove(v);  senkeSeite.remove(v);
- df = Math.min(df, durchfluss(quelleSeite, senkeSeite));+ df = Math.min(df, durchfluss(quelleSeite, senkeSeite, senke)); 
 +                        //"Backtracking"
  senkeSeite.add(v);  senkeSeite.add(v);
  quelleSeite.remove(v);  quelleSeite.remove(v);