Du befindest dich hier: FSI Informatik » Prüfungsfragen und Altklausuren » Prüfungen im Bachelor-Studium (1. - 5. Semester) » aud » Lösungsversuch
Unterschiede
Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.
Beide Seiten, vorherige ÜberarbeitungVorherige ÜberarbeitungNächste Überarbeitung | Vorherige ÜberarbeitungLetzte ÜberarbeitungBeide Seiten, nächste Überarbeitung | ||
pruefungen:bachelor:aud:loesungss14 [20.07.2018 15:02] – elias007 | pruefungen:bachelor:aud:loesungss14 [31.07.2019 09:30] – Anpassungen Aufgabe 4 dom | ||
---|---|---|---|
Zeile 106: | Zeile 106: | ||
**d)** \\ | **d)** \\ | ||
{{: | {{: | ||
+ | |||
+ | |||
==== 4) Backtracking ==== | ==== 4) Backtracking ==== | ||
+ | **a)** | ||
+ | <code java> | ||
+ | static boolean exists(boolean[][] brd, int r, int c) { | ||
+ | if (brd[r] == null || brd[r].length < 1) { // Zeilen null oder leer | ||
+ | return false; | ||
+ | } | ||
+ | if (r >= brd.length || c >= brd[r].length || r < 0 || c < 0) { // Indizes ausserhalb der Grenzen | ||
+ | return false; | ||
+ | } | ||
+ | return true; | ||
+ | } | ||
+ | </ | ||
- | Loesung uebernommen aus dem Forum, eventuell gegenchecken | + | **b)** |
- | https:// | + | |
+ | < | ||
+ | static int[][] allocateSolutionArray(boolean[][] brd, int mrl) { | ||
+ | int[][] = null; | ||
+ | int[][] sol = new int[brd.length][mrl]; | ||
- | static boolean | + | for (int r = 0; r < brd.length; r++) { |
- | if(brd[r] == null || brd[r].length < 1) { | + | for (int c = 0; c < mrl; c++) { |
- | return false; | + | if (exists(brd, |
- | } | + | sol[r][c] = 0; |
- | if(r >= brd.length || c >= brd[r].length || r < 0 || c < 0) { | + | } else { |
- | return false; | + | sol[c][c] = -1; // Felder mit -1 vorbelegen |
- | } | + | } |
- | return true; | + | } |
- | } | + | } |
+ | return sol; | ||
+ | } | ||
+ | </ | ||
+ | **c)** | ||
+ | < | ||
+ | static boolean | ||
+ | // possible targets from (r,c) | ||
+ | int[][] jumps = { { r + 2, c - 1 }, { r + 1, c - 2 }, { r - 1, c - 2 }, { r - 2, c - 1 }, | ||
+ | { r - 2, c + 1 }, { r - 1, c + 2 }, { r + 1, c + 2 }, { r + 2, c + 1 } }; | ||
+ | |||
+ | // | ||
+ | | ||
+ | sol[r][c] = n; | ||
+ | return true; | ||
+ | } | ||
+ | for (int j = 0; j < jumps.length; | ||
- | static int[][] allocateSolutionArray(boolean[][] brd, int mrl) { | + | // Wert setzen |
- | int[][] | + | sol[r][c] = n |
- | for(int i = 0; i < brd.length; i++) { | + | |
- | for(int j = 0; j < mrl; j++) { | + | |
- | if(exists(brd, | + | |
- | sol[i][j] = 0; | + | |
- | } else { | + | |
- | sol[i][j] = -1; | + | |
- | } | + | |
- | } | + | |
- | } | + | |
- | return sol; | + | |
- | } | + | |
- | static boolean solve(boolean[][] | + | // Brett brd und Loesungsfeld |
- | int[][] jumps = { { r + 2, c - 1 }, { r + 1, c - 2 }, { r - 1, c - 2 }, { r - 2, c - 1 }, { r - 2, c + 1 }, | + | if (exists(brd, |
- | { r - 1, c + 2 }, { r + 1, c + 2 }, { r + 2, c + 1 } }; | + | |
- | if(sol[r][c] >= 1) { | + | |
- | return false; | + | |
- | } | + | |
- | if(n == tf) { | + | |
- | sol[r][c] = n; | + | |
- | return true; | + | |
- | } | + | |
- | sol[r][c] = n; | + | |
- | for(int k = 0; k < jumps.length; | + | |
- | if(exists(brd, | + | |
- | if(solve(brd, | + | |
- | return true; | + | |
- | } | + | |
- | } | + | |
- | } | + | |
- | sol[r][c] = 0; | + | |
- | return false; | + | |
- | } | + | |
- | [[pruefungen: | + | // Rekursion |
+ | if (solve(brd, sol, tf, jumps[j][0], jumps[j][1], n + 1)) { | ||
+ | return true; | ||
+ | } | ||
+ | // Backtrack | ||
+ | sol[r][c] = 0; | ||
+ | } | ||
+ | } | ||
+ | return false; | ||
+ | } | ||
+ | </ | ||
+ | |||
+ | |||
+ | |||
+ | |||
+ | Alternative: | ||
** a) *** | ** a) *** | ||
Zeile 208: | Zeile 226: | ||
if (exists(brd, | if (exists(brd, | ||
sol[r][c] = n; | sol[r][c] = n; | ||
- | + | if (solve(brd, sol, tf, jump[0], jump[1], n + 1)) { | |
- | boolean res = solve(brd, sol, tf, jump[0], jump[1], n + 1); | + | |
- | if (res) { | + | |
return true; | return true; | ||
} | } | ||
- | |||
sol[r][c] = 0; | sol[r][c] = 0; | ||
} | } | ||
- | |||
} | } | ||
- | |||
return false; | return false; | ||
} | } | ||
</ | </ | ||
+ | [[pruefungen: | ||
==== 5) Haldensortierung ==== | ==== 5) Haldensortierung ==== | ||
Zeile 233: | Zeile 247: | ||
\\ | \\ | ||
c) | c) | ||
+ | <code java> | ||
+ | // | ||
void reheap(W[] w, Comparator< | void reheap(W[] w, Comparator< | ||
int leftId = 2 * i + 1; | int leftId = 2 * i + 1; | ||
Zeile 250: | Zeile 266: | ||
} | } | ||
} | } | ||
+ | </ | ||
\\ | \\ | ||
d) | d) | ||
Zeile 275: | Zeile 292: | ||
HashMap< | HashMap< | ||
for(char c : s.toCharArray()) { | for(char c : s.toCharArray()) { | ||
- | if(map.get(c) | + | Node n = map.get(c); |
- | map.put(c, new Node(c, 1)); | + | if(n != null) { |
+ | //variable frequenz updaten | ||
+ | n.f++; | ||
} else { | } else { | ||
- | int value = map.get(c).f += 1; | + | //neuer node in die map |
- | map.put(c, | + | map.put(c, |
} | } | ||
} | } |