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
Letzte ÜberarbeitungBeide Seiten, nächste Überarbeitung
pruefungen:bachelor:aud:loesungws16 [02.04.2019 11:34] – Nico Hambauerpruefungen:bachelor:aud:loesungws16 [22.05.2019 12:32] – SpeedyGonzalez
Zeile 60: Zeile 60:
 <code java> <code java>
 void radixSort (LinkedList<Integer> list) { void radixSort (LinkedList<Integer> list) {
 +        //prepare sufficient buckets bs with empty lists:
  LinkedList<Integer>[] bs = new LinkedList[10];  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 = (int) (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 j = 0; j < bs.length; j++) {  for (int j = 0; j < bs.length; j++) {
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 99: Zeile 109:
 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] = mem[1] = 1;
- mem[1] = 1;+
  return countDPH(mem, n);  return countDPH(mem, n);
 } }
Zeile 120: Zeile 129:
  ...  ...
  for (int k = 2; k < n+1; k++){  for (int k = 2; k < n+1; k++){
- for (int i = 0; i < n; i++){ + 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];+ mem[k] = mem[k] + mem[i] * mem[n-1-i]; //hier auch mem[k-1-i]!
  }  }
  }  }
  ...  ...
 +}
 +</code>
 +
 +oder schöner:
 +
 +<code java>
 +private long countDPH (long[] mem, int n) {
 + if (mem[n] != 0) {
 + return mem[n];
 + }
 + for (int i = 0; i < n; i++){
 +            mem[n] += countDPH(mem, i) * countDPH(mem, n-1-i);
 + }
 + return mem[n];
 } }
 </code> </code>
Zeile 174: Zeile 197:
  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);