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.
Beide Seiten, vorherige ÜberarbeitungVorherige ÜberarbeitungNächste Überarbeitung | Vorherige Überarbeitung | ||
pruefungen:bachelor:aud:loesungws16 [07.02.2018 14:50] – Horsccht | pruefungen:bachelor:aud:loesungws16 [02.08.2019 07:32] (aktuell) – Aufgabe 4 angepasst dom | ||
---|---|---|---|
Zeile 22: | Zeile 22: | ||
==== Aufgabe 2 Streupeicherung ==== | ==== Aufgabe 2 Streupeicherung ==== | ||
** a) ** | ** a) ** | ||
+ | |||
Bucket 1: 27 - 75 | Bucket 1: 27 - 75 | ||
+ | |||
Bucket 3: 44 - 4 - 0 | Bucket 3: 44 - 4 - 0 | ||
+ | |||
Bucket 5: 13 - 65 - 33 | Bucket 5: 13 - 65 - 33 | ||
+ | |||
Bucket 7: 46 - 26 | Bucket 7: 46 - 26 | ||
Zeile 31: | Zeile 35: | ||
** c) ** | ** c) ** | ||
+ | |||
Bucket 0: 12 S | Bucket 0: 12 S | ||
+ | |||
Bucket 1: 33 D | Bucket 1: 33 D | ||
+ | |||
Bucket 2: 66 S | Bucket 2: 66 S | ||
+ | |||
Bucket 3: 28 P | Bucket 3: 28 P | ||
+ | |||
Bucket 4: 14 D | Bucket 4: 14 D | ||
+ | |||
Bucket 5: 6 S | Bucket 5: 6 S | ||
+ | |||
Bucket 6: 18 D | Bucket 6: 18 D | ||
+ | |||
Bucket 7: 5 D | Bucket 7: 5 D | ||
+ | |||
Bucket 8: 15 P | Bucket 8: 15 P | ||
+ | |||
Bucket 9: 9 D | Bucket 9: 9 D | ||
- | ==== Aufgabe | + | ==== Aufgabe |
** a) ** | ** a) ** | ||
<code java> | <code java> | ||
void radixSort (LinkedList< | void radixSort (LinkedList< | ||
- | LinkedList< | + | //prepare sufficient buckets bs with empty lists: |
+ | LinkedList< | ||
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++) { | ||
+ | // | ||
for (Integer x: list) { | for (Integer x: list) { | ||
- | int b = (x/ | + | int b = (int) (x/ |
bs[b].addLast(x); | bs[b].addLast(x); | ||
} | } | ||
+ | // | ||
list.clear(); | list.clear(); | ||
- | for (int i = 0; i < bs.length; | + | for (int j = 0; j < bs.length; |
- | list.addAll(bs[i]); | + | list.addAll(bs[j]); |
- | bs[i].clear(); | + | bs[j].clear(); |
} | } | ||
} | } | ||
Zeile 66: | Zeile 84: | ||
<code java> | <code java> | ||
... | ... | ||
- | int b = ((x/ | + | int b = ((int) (x/ |
... | ... | ||
+ | </ | ||
+ | |||
+ | oder einfacher: | ||
+ | <code java> | ||
+ | ... | ||
+ | bs[b + 9].addLast(x); | ||
</ | </ | ||
==== Aufgabe 4 Dynamische Programmierung ==== | ==== Aufgabe 4 Dynamische Programmierung ==== | ||
Zeile 76: | Zeile 100: | ||
return 1; | return 1; | ||
} | } | ||
- | int sum = 0; | + | 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; | ||
} | } | ||
+ | </ | ||
+ | |||
+ | **b)** | ||
+ | < | ||
long countDP (int n) { | long countDP (int n) { | ||
- | long[] mem = new long[]; | + | long[] mem = new long[n + 1]; |
mem[0] = 1; | mem[0] = 1; | ||
- | mem[1] = 1; | + | |
+ | | ||
return countDPH(mem, | return countDPH(mem, | ||
} | } | ||
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(i) * countDPH(n-1-i); | + | sum |
} | } | ||
+ | // Memoization | ||
mem[n] = sum; | mem[n] = sum; | ||
return sum; | return sum; | ||
} | } | ||
} | } | ||
+ | </ | ||
+ | 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, | ||
+ | } | ||
+ | return mem[n]; | ||
+ | } | ||
+ | </ | ||
+ | |||
+ | **c)** | ||
+ | |||
+ | < | ||
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 113: | Zeile 164: | ||
} | } | ||
</ | </ | ||
+ | |||
==== Aufgabe 5 Graphen ==== | ==== Aufgabe 5 Graphen ==== | ||
Zeile 156: | Zeile 208: | ||
double df = schnittDurchfluss(quelleSeite, | double df = schnittDurchfluss(quelleSeite, | ||
for(Verteiler v : ssa){ | for(Verteiler v : ssa){ | ||
- | if(!v.equals(senke)){ | + | if(!v.equals(senke)){ |
+ | // Hier kann man noch checken, ob zu v auch eine Kante aus quelleSeite existiert, aber nicht notwendig, da der Cut nur länger weden würde -> nur geringere Laufzeit | ||
quelleSeite.add(v); | quelleSeite.add(v); | ||
senkeSeite.remove(v); | senkeSeite.remove(v); | ||
- | df = Math.min(df, | + | df = Math.min(df, |
+ | //" | ||
senkeSeite.add(v); | senkeSeite.add(v); | ||
quelleSeite.remove(v); | quelleSeite.remove(v); |