Du befindest dich hier: FSI Informatik » Prüfungsfragen und Altklausuren » Prüfungen im Bachelor-Studium (1. - 5. Semester) » aud » Forendiskussionen (Übersicht)
Dies ist eine alte Version des Dokuments!
Inhaltsverzeichnis
Forendiskussionen
- https://fsi.cs.fau.de/forum/post/159888 Allgemeine Diskussion
- https://fsi.cs.fau.de/forum/post/159926;nocount Aufgabe 3 (Gierige Algorithmen) Schulden begleichen
Lösungsversuch
Aufgabe 1
- a)
long aDP(int n) { long[] a = new long[n + 1]; long[] b = new long[n + 1]; Arrays.fill(a, -1); // -1 == UNKNOWN Arrays.fill(b, -1); return aDP(n, a, b); } long aDP(int n, long[] a, long[] b) { if(n ==0) return 1; if(n == 1) return 0; if(a[n] == -1){ a[n]=aDP(n-2, a, b) + 2*nDB(n-1, a, b); } return a[n]; } long bDP(int n, long[] a, long[] b) { if(n ==0) return 0; if(n ==1) return 1; if(b[n] == -1){ b[n]=aDP(n-1, a, b) + bDB(n-2, a, b); } return b[n]; }
- b)
long aIter(int n) { long[] a = new long[n + 1], b = new long[n + 1]; a[0] = 1; b[0] = 0; a[1] = 0; b[1] = 1; for (int i = 2; i <= n; i++){ a[i] = a[i-2] + 2*b[i-1]; b[i] = a[i-1] + b[i-2]; } return a[n]; }
Aufgabe 2
- a)
A | B | C | D | E | Prio-Queue |
---|---|---|---|---|---|
0 | ∞ | ∞ | ∞ | ∞ | [A] |
0 | 15 | 5 | ∞ | 12 | [C, E, B] |
0 | 13 | 5 | 10 | 8 | [E, D, B] |
0 | 10 | 5 | 9 | 8 | [D, B] |
0 | 10 | 5 | 9 | 8 | [B] |
Endergebnis | |||||
0 | 10 | 5 | 9 | 8 | [ ] |
- b) A → C → E → B
- c)
uj | vi | wk | γj,k alt | γj,i,k | γj,k neu |
---|---|---|---|---|---|
A | C | B | 15 | 13 | 13 |
A | C | D | ∞ | 10 | 10 |
A | C | E | 12 | 8 | 8 |
A | D | B | 13 | 12 | 12 |
C | D | B | 8 | 7 | 7 |
E | D | B | 2 | 3 | 2 |
A | E | B | 12 | 10 | 10 |
A | E | D | 10 | 9 | 9 |
C | E | B | 7 | 5 | 5 |
C | E | D | 5 | 4 | 4 |
Aufgabe 3
class Schuld { final String s; // Schuldner final long b; // Betrag final String g; // Geldgeber public Schuld(String s, long b, String g) { // [s --b--> g] ... } }
- a)
HashMap<String, Long> deltas(List<Schuld> schulden) { HashMap<String, Long> ds = new HashMap<>(); Long dAlt; // altes Delta in ds for (Schuld s : schulden) { // ausgehender Betrag (von Schuldner): dAlt = ds.get(s.s); dAlt = dAlt == null ? 0L : dAlt; ds.put(s.s, dAlt - s.b); //muss es nicht heissen dAlt + s.b? // eingehender Betrag (zu Geldgeber): dAlt = ds.get(s.g); dAlt = dAlt == null ? 0L : dAlt; ds.put(s.g, dAlt + s.b); //muss es nicht heissen dAlt - s.b? // Z.B. ist A Geldgeber ggü. B und D, gibt also 60. Ist ggü. C Schuldner in Höhe von 10. //Laut der Angabe ist ∆A: -50, mit den hier Im Lösungsvorschlag angegebenen Vorzeichen würde sich für // ∆A aber +50 ergeben wenn ich mich nicht täusche. //Anmerkung: du taeuscht dich, A ist Schuldner gegenueber B und D und Geldgeber gegenueber C (s.Zeile 2 S.6)! } return ds; }
- b)
List<Schuld> minimiere(List<Schuld> schulden) { List<Schuld> ergebnis = new LinkedList<>(); HashMap<String, Long> deltas = deltas(schulden); while (deltas.size() > 1) { // ermittle groessten Schuldner S bzw. Geldgeber G: String S = null, G = null; long dS = 0, dG = 0; // Deltas von S bzw. G for (String p : deltas.keySet()) { long d = deltas.get(p); if(S == null) { S = p; dS = d; } if (dS > d) { S = p; //(Ergänzt) auch der String des groessten Schuldners muss m.E.n. angepasst werden. dS = d; } if (G == null) { G = p; dG = d; } if (dG < d) { G = p; //(Ergänzt) auch der String des groessten Geldgebers muss m.E.n. angepasst werden. dG = d; } } // begleiche Schuld von S nach G: long dmin = Math.min(Math.abs(dS), Math.abs(dG)); Schuld result = new Schuld (S, dMin, G); ergebnis.add(result); // aktualisiere deltas von S bzw. G: if (dmin == Math.abs(dS)) { deltas.put(G, dG - dmin); // Alternative: long dNeuG = deltas.get(G) ; dNeuG += dS; oder dNeuG -= dmin; deltas.put(G, dNeuG); deltas.remove(S); } else { deltas.put(S, dS + dmin); // Alternative: long dNeuS = deltas.get(S); dNeuS += dG; oder dNeuS += dmin; deltas.put(S, dNeuS); deltas.remove(G); } } return ergebnis; }
Aufgabe 4
* a) remove(Add(s,v1),v2) = remove (s,v2) falls v1 == v2 Add(remove(s,v2),v1) sonst * b) contains(Add(s, v1), v2) = true falls v1 == v2 contains(s,v2) sonst * c) addAll(Add(s1; v); s2) = Add(addAll(s1,s2), v) * d) eval(Decision(v; t; f); s) = eval (t,s) falls contains(s,v) == true eval (f,s) sonst * e) collect(Decision(v; t; f)) = Add(addAll(collect(t), collect(f)),v) * f) isBDD(Decision(v; t; f)) = isBDD(t) ^ isBDD(f) ^ !contains(addAll(collect(t), collect(f)),v)
Aufgabe 5
- a)
Str8ts(boolean[][] blk, int[][] num) { // Konstruktor this.blk = blk; this.num = num; vert = new ArrayList<>(); horz = new ArrayList<>(); for(int i = 0; i < 9; i++) { vert.add(new HashSet<Integer>()); horz.add(new HashSet<Integer>()); } // fill vert/horz with predefined values for(int row = 0; row < 9; row++) { for(int col = 0; col < 9; col++) { vert.get(col).add(num[row][col]); horz.get(row).add(num[row][col]); } } solve(0, 0); // find solution if possible }
- b)
boolean isStr8tOrUnfinished(List<Integer> s) { Collections.sort(s); if (!s.contains(0)) { int previous = s.get(0); for(int i = 1; i < s.size(); i++) { if(s.get(i) != previous + 1) { return false; } previous = s.get(i); } } return true; }
- c)
boolean checkStr8t(int row, int col) { List<Integer> sh = new ArrayList<>(), sv = new ArrayList<>(); int c = col, r = row; while (c >= 0 && !blk[row][c]) { // search start of horizontal str8t c--; } // collect values of current horizontal str8t in sh: while(++c < 9 && !blk[row][c]) { sh.add(num[row][c]); } while (r >= 0 && !blk[r][col]) { // search start of vertical str8t r--; } // collect values of current vertical str8t in sv: while(++r < 9 && !blk[r][col]) { sv.add(num[r][col]); } // check that both sh and sv are str8ts or unfinished: return isStr8tOrUnfinished(sh) && isStr8tOrUnfinished(sv); }
- d)
boolean solve(int row, int col) { if (row >= 9) { return true; // solution found } else if (col >= 9) { return solve(row + 1, 0); } else if (blk[row][col] || num[row][col] > 0) { return solve(row, col + 1); // skip field } for (int v = 1; v <= 9; v++) { // if row and column do not contain v... if(!vert.get(col).contains(v) && !horz.get(row).contains(v)) { // ... process current field: num[row][col] = v; vert.get(col).add(v); horz.get(row).add(v); // check current str8t and recur on next field: if(checkStr8t(row, col)) { if(solve(row, col + 1) { return true; } } // backtrack current field: num[row][col] = 0; vert.get(col).remove(v); horz.get(row).remove(v); } } return false; // puzzle has no solution }
Aufgabe 6
- a) 3,4 richtig /–2 recht sicher auch, steht so zumindest auf den TÜ- Folien/ 2 ist falsch, QuickSort kann in-situ implementiert werden siehe Vorlesungsfolie „Überblick über die Sortierverfahren“
- b) 2, 3 richtig /–4 ist denke ich falsch, siehe 02-2008-7f2.png
- c) 1,4 richtig
- d) 1,2 richtig /–Code von 2 in Eclipse eingetippt, hat nicht gemeckert. 3 sollte auch nicht richtig sein, da der rueckgabetyp sehr wohl generisch sein kann, z.b Unimodale Suche
- e) 2 ,3 sind richtig, wobei bei 3 javac -ea fuer „enable assertions“ steht. (Wieso das Stoff in AuD ist, ist fraglich)