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 09:29] Nico Hambauerpruefungen:bachelor:aud:loesungws16 [02.08.2019 07:32] (aktuell) – Aufgabe 4 angepasst dom
Zeile 60: Zeile 60:
 <code java> <code java>
 void radixSort (LinkedList<Integer> list) { void radixSort (LinkedList<Integer> list) {
- LinkedList<Integer>[] bs = new LinkedList[];+        //prepare sufficient buckets bs with empty lists: 
 + LinkedList<Integer>[] bs = new LinkedList[10];
  for (int i = 0; i < bs.length; i++) {  for (int i = 0; i < bs.length; i++) {
- bs[i] = new LinkedList();+ bs[i] = new LinkedList<>();
  }  }
 +        //for each segment of the Integer radix...
  for (int i = 0; i < 10; i++) {  for (int i = 0; i < 10; i++) {
 +                //...distribute values into buckets:
  for (Integer x: list) {  for (Integer x: list) {
- int b = (x/Math.pow(10,i)) % 10;+ int b = (int) (x/Math.pow(10,i)) % 10;
  bs[b].addLast(x);  bs[b].addLast(x);
  }  }
 +                //...recollect values from buckets:
  list.clear();  list.clear();
- for (int = 0; < bs.length; i++) { + for (int = 0; < bs.length; j++) { 
- list.addAll(bs[i]); + list.addAll(bs[j]); 
- bs[i].clear();+ bs[j].clear();
  }  }
  }  }
Zeile 80: Zeile 84:
 <code java> <code java>
 ... ...
-int b = ((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 90: 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] = 1;  mem[0] = 1;
- mem[1] = 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;
  }  }
 } }
 +</code>
 +
 +oder schöner:
 +
 +<code java>
 +private long countDPH (long[] mem, int n) {
 + // Lookup
 +        if (mem[n] != 0) {
 + return mem[n];
 + }
 + for (int i = 0; i < n; i++) {
 +            // Berechnung + Memoization
 +            mem[n] += countDPH(mem, i) * countDPH(mem, n-1-i);
 + }
 + return mem[n];
 +}
 +</code>
 +
 +**c)**
  
 +<code=java>
 long countIter (int n) { long countIter (int n) {
  ...  ...
- for (int k = 2; k < n+1; k++){ + for (int k = 2; k < n+1; k++) { // for-Schleife fuer bottom-up 
- for (int i = 0; i < n; i++){ + for (int i = 0; i < k; i++) { 
- mem[k] = mem[k] + mem[i] * mem[n-1-i];+ mem[k] = mem[k] + mem[i] * mem[k-1-i];
  }  }
  }  }
Zeile 127: Zeile 164:
 } }
 </code> </code>
 +
  
 ==== Aufgabe 5 Graphen ==== ==== Aufgabe 5 Graphen ====
Zeile 174: 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);