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
Lösungsversuch
Aufgabe 1
- 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(a[n] != -1) { return a[n]; } long resultA; if(n == 0) { resultA = 1; } else if(n == 1) { resultA = 0; } else { resultA = aDP(n-2, a, b) + 2*bDP(n-1, a, b); //muss hier nicht a[n]=... stehen statt resultA=... } return resultA; } long bDP(int n, long[] a, long[] b) { if(b[n] != -1) { return b[n]; } long resultB; if(n == 0 || n == 1) { resultB = n; }else { resultB = aDP(n -1, a, b) + bDP(n-2, a, b); } return resultB; }
- 1.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]; }
- 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 | [ ] |
- 2.b) A → C → E → B
- 2.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 |
* 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); // eingehender Betrag (zu Geldgeber): dAlt = ds.get(s.g); dAlt = dAlt == null ? 0L : dAlt; ds.put(s.g, dAlt + s.b); } 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) { dS = d;} if (G == null) { G = p; dG = d; } if (dG < d) {dG = d;} } // begleiche Schuld von S nach G: long dmin = Math.min(Math.abs(dS), Math.abs(dG)); if (deltas.size() == 2){ Schuld result = new Schuld (S, dMin, G); ergebnis.add(result); } // aktualisiere deltas von S bzw. G: if (dmin == Math.abs(dS)) { long dNeuG = deltas.get(G) ; dNeuG += dS; // hier habe ich: dNeuG -= dmin; deltas.put(G, dNeuG); deltas.remove(S); } else { long dNeuS = deltas.get(S); dNeuS += dG; // hier habe ich: dNeuS += dmin; deltas.put(S, dNeuS); deltas.remove(G); } } return ergebnis; }
* 4.a) remove(Add(s,v1),v2) = remove (s,v2) falls v1 == v2 Add(remove(s,v2),v1) sonst * 4.b) contains(Add(s, v1), v2) = true falls v1 == v2 contains(s,v2) sonst * 4.c) addAll(Add(s1; v); s2) = Add(addAll(s1,s2), v) * 4.d) eval(Decision(v; t; f); s) = eval (t,s) falls contains(s,v) == true eval (f,s) sonst * 4.e) collect(Decision(v; t; f)) = Add(addAll(collect(t), collect(f)),v) * 4.f) isBDD(Decision(v; t; f)) = isBDD(t) ^ isBDD(f) ^ contains(addAll(collect(t), collect(f)),v)
- 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 }
- 6.
- a) 3,4 richtig /–2 recht sicher auch, steht so zumindest auf den TÜ- Folien
- b) 2, 3,4 richtig /–4 ist denke ich falsch, siehe 02-2008-7f2.png
- c) 1,4 richtig
- d) 1,3 richtig /–Code von 2 in Eclipse eingetippt, hat nicht gemeckert.
- e) 2 richtig (vielleicht 3 auch richtig, aber nicht sicher)