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 Überarbeitung | |||
pruefungen:bachelor:aud:loesungws16 [22.05.2019 12:32] – SpeedyGonzalez | pruefungen: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; | ||
} | } | ||
+ | </ | ||
+ | |||
+ | **b)** | ||
+ | < | ||
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; |
+ | | ||
+ | | ||
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(mem, | + | sum |
} | } | ||
+ | // 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]! | ||
- | } | ||
- | } | ||
- | ... | ||
} | } | ||
</ | </ | ||
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 |
+ | | ||
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, | mem[n] += countDPH(mem, | ||
} | } | ||
Zeile 150: | Zeile 150: | ||
} | } | ||
</ | </ | ||
+ | |||
+ | **c)** | ||
+ | |||
+ | < | ||
+ | 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]; | ||
+ | } | ||
+ | } | ||
+ | ... | ||
+ | } | ||
+ | </ | ||
+ | |||
==== Aufgabe 5 Graphen ==== | ==== Aufgabe 5 Graphen ==== |