Du befindest dich hier: FSI Informatik » Prüfungsfragen und Altklausuren » Prüfungen im Bachelor-Studium (1. - 5. Semester) » aud » Forendiskussionen
Unterschiede
Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.
Beide Seiten, vorherige ÜberarbeitungVorherige ÜberarbeitungNächste Überarbeitung | Vorherige ÜberarbeitungNächste ÜberarbeitungBeide Seiten, nächste Überarbeitung | ||
pruefungen:bachelor:aud:loesungws16 [02.04.2019 09:29] – Nico Hambauer | pruefungen:bachelor:aud:loesungws16 [03.04.2019 10:25] – Nico Hambauer | ||
---|---|---|---|
Zeile 60: | Zeile 60: | ||
<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 80: | Zeile 84: | ||
<code java> | <code java> | ||
... | ... | ||
- | int b = ((x/ | + | int b = ((int) (x/ |
... | ... | ||
</ | </ | ||
Zeile 99: | Zeile 103: | ||
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, | return countDPH(mem, | ||
} | } | ||
Zeile 120: | Zeile 123: | ||
... | ... | ||
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]; |
} | } | ||
} | } | ||
... | ... | ||
+ | } | ||
+ | </ | ||
+ | |||
+ | 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, | ||
+ | } | ||
+ | return mem[n]; | ||
} | } | ||
</ | </ | ||
Zeile 174: | Zeile 191: | ||
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); |