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 [07.02.2018 10:37] – l Horsccht | pruefungen:bachelor:aud:loesungws16 [04.04.2019 08:52] – Nico Hambauer | ||
---|---|---|---|
Zeile 1: | Zeile 1: | ||
- | <note warning> | ||
- | |||
- | </ | ||
- | |||
===== Forendiskussionen ===== | ===== Forendiskussionen ===== | ||
Zeile 27: | Zeile 23: | ||
** a) ** | ** a) ** | ||
- | TODO | + | Bucket 1: 27 - 75 |
+ | |||
+ | Bucket 3: 44 - 4 - 0 | ||
+ | |||
+ | Bucket 5: 13 - 65 - 33 | ||
+ | |||
+ | Bucket 7: 46 - 26 | ||
** b) ** Es werden nur die ungeraden Buckets befüllt, da 2 und 8 nicht teilerfremd sind. | ** b) ** Es werden nur die ungeraden Buckets befüllt, da 2 und 8 nicht teilerfremd sind. | ||
- | ** c) ** TODO | + | ** c) ** |
- | ==== Aufgabe | + | Bucket 0: 12 S |
- | ** a) *** | + | |
+ | Bucket 1: 33 D | ||
+ | |||
+ | Bucket 2: 66 S | ||
+ | |||
+ | Bucket 3: 28 P | ||
+ | |||
+ | Bucket 4: 14 D | ||
+ | |||
+ | Bucket 5: 6 S | ||
+ | |||
+ | Bucket 6: 18 D | ||
+ | |||
+ | Bucket 7: 5 D | ||
+ | |||
+ | Bucket 8: 15 P | ||
+ | |||
+ | Bucket 9: 9 D | ||
+ | |||
+ | ==== Aufgabe | ||
+ | ** 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 57: | Zeile 84: | ||
<code java> | <code java> | ||
... | ... | ||
- | int b = ((x/ | + | int b = ((int) (x/ |
... | ... | ||
</ | </ | ||
- | ==== Aufgabe 5 Sortieren==== | ||
- | **a)** | ||
- | ^L * ^A1 ^B1 ^F ^A2 ^B2| | + | oder einfacher: |
- | |A1|L*|B1|F |A2|B2| | + | |
- | |A1|B1|L*|F |A2|B2| | + | |
- | |A1|B1|F |L*|A2|B2| | + | |
- | |A1|A2|B1|F |L*|B2| | + | |
- | |A1|A2|B1|B2|F |L*| | + | |
- | + | ||
- | **b)** | + | |
- | + | ||
- | ==== Aufgabe 7 Graphen ==== | + | |
<code java> | <code java> | ||
- | public class GraphWS15 | + | ... |
+ | bs[b + 9].addLast(x); | ||
+ | </ | ||
+ | ==== Aufgabe 4 Dynamische Programmierung ==== | ||
+ | **a)** | ||
+ | <code java> | ||
+ | long countNaive(int n) { | ||
+ | if (n == 0 || n == 1) { | ||
+ | return 1; | ||
+ | } | ||
+ | int sum = 0; //sum muesste eigentlich ein long sein | ||
+ | for (int i = 0; i < n; i++){ | ||
+ | sum = sum + countNaive(i) * countNaive(n-1-i); | ||
+ | } | ||
+ | return sum; | ||
+ | } | ||
- | void sammle(boolean[][] am, int k, Set< | + | long countDP |
- | if (!bes.contains(k)) { | + | long[] mem = new long[n+1]; |
- | verb.add(k); | + | mem[0] = mem[1] = 1; |
- | bes.add(k); | + | return countDPH(mem, n); |
- | for (int i = 0; i < am[k].length; i++) { | + | } |
- | if (am[k][i]){ | + | |
- | sammle(am, i, verb, bes); | + | |
- | } | + | |
- | } | + | |
- | for (int i = 0; i < am.length; i++) { | + | private long countDPH (long[] mem, int n) { |
- | if (am[i][k]){ | + | if (mem[n] != 0) { |
- | sammle(am, i, verb, bes); | + | return mem[n]; |
- | } | + | } else { |
- | } | + | int sum = 0; |
+ | for (int i = 0; i < n; i++){ | ||
+ | sum = sum + countDPH(mem, i) * countDPH(mem, n-1-i); | ||
} | } | ||
+ | mem[n] = sum; | ||
+ | return sum; | ||
} | } | ||
+ | } | ||
- | List< | + | long countIter |
- | // Ergebnisliste: | + | ... |
- | List< | + | for (int k = 2; k < n+1; k++){ |
- | // Menge besuchter Knoten: | + | for (int i = 0; i < n; i++){ //Meiner Meinung nach mus hier unbedingt!!! i < k stehen, sonst rechnet man mit unbefuellten werten |
- | Set< | + | mem[k] = mem[k] + mem[i] * mem[n-1-i]; //hier auch mem[k-1-i]! |
- | // Ermittle alle Teilgraphen mittels Hilfsmethode sammle: | + | |
- | for (int k = 0; k < am.length; k++) { | + | |
- | if (!bk.contains(k)){ | + | |
- | // falls k noch nicht besucht | + | |
- | Set< | + | |
- | sammle(am, | + | |
- | ergebnis.add(verb); | + | |
- | } | + | |
- | + | ||
} | } | ||
+ | } | ||
+ | ... | ||
+ | } | ||
+ | </ | ||
- | return | + | oder schöner: |
+ | |||
+ | <code java> | ||
+ | private long countDPH (long[] mem, int n) { | ||
+ | if (mem[n] != 0) { | ||
+ | return | ||
} | } | ||
+ | for (int i = 0; i < n; i++){ | ||
+ | mem[n] += countDPH(mem, | ||
+ | } | ||
+ | return mem[n]; | ||
+ | } | ||
+ | </ | ||
- | void itg(boolean[][] am, Set<Integer> vs) { | + | ==== Aufgabe 5 Graphen ==== |
- | for (int i=0;i<am.length;i++){ | + | ** a) ** |
- | for (int j=0;j< | + | Ergebnis: A 14, E 18, H4 6, H7 3, M 2, W 0 |
- | if (am[i][j]){ | + | |
- | if (vs.contains(i) && vs.contains(j)){ | + | ** b) ** siehe Tafeluebungsfolien |
- | // ok | + | |
- | } | + | ** c) ** M - H7, M - W, M - H4, A - E, A - H4 oder A - W |
- | else | + | |
- | am[i][j] = false; | + | ** d) ** |
- | } | + | nein: bei 4 Knoten ungerader Grad |
- | } | + | nein: nicht mal ein Eulerweg |
- | } | + | |
- | + | ==== Aufgabe 6 Rekursion ==== | |
+ | <code java> | ||
+ | class MaxFlowMinCut { | ||
+ | | ||
+ | | ||
+ | ev.add(v); | ||
+ | | ||
+ | this.erreichbareVerteiler(r.a, | ||
+ | this.erreichbareVerteiler(r.e, | ||
+ | } | ||
+ | } | ||
+ | } | ||
+ | |||
+ | double schnittDurchfluss(List< | ||
+ | | ||
+ | for(Verteiler v : quelleSeite){ | ||
+ | for(Rohr r : v.rohre){ | ||
+ | if(senkeSeite.contains(r.a) || senkeSeite.contains(r.e)){ | ||
+ | sum += r.df; | ||
+ | } | ||
+ | } | ||
+ | } | ||
+ | return sum; | ||
+ | } | ||
+ | |||
+ | |||
+ | double durchfluss(List< | ||
+ | Verteiler[] ssa = senkeSeite.toArray(new Verteiler[senkeSeite.size()]); | ||
+ | double df = schnittDurchfluss(quelleSeite, | ||
+ | for(Verteiler v : ssa){ | ||
+ | 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); | ||
+ | senkeSeite.remove(v); | ||
+ | df = Math.min(df, | ||
+ | senkeSeite.add(v); | ||
+ | quelleSeite.remove(v); | ||
} | } | ||
} | } | ||
- | + | return df; | |
- | public static void main(String[] args){ | + | |
- | // | + | |
- | GraphWS15 g = new GraphWS15(); | + | |
- | boolean[][] am = {{false, true, false, true, false, false}, | + | |
- | | + | |
- | | + | |
- | {false, true, false, false, false, false}, | + | |
- | {false, false, false, false, false, false}, | + | |
- | {false, false, false, false, false, false}}; | + | |
- | // | + | |
- | List< | + | |
- | System.out.println(n.size()); | + | |
- | System.out.println(n.get(0).size()); | + | |
- | System.out.println(n.get(1).size()); | + | |
- | System.out.println(n.get(2).size()); | + | |
- | } | + | |
} | } | ||
</ | </ |