Du befindest dich hier: FSI Informatik » Prüfungsfragen und Altklausuren » Prüfungen im Bachelor-Studium (1. - 5. Semester) » aud » Lösungsversuch   (Übersicht)

Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

Link zu der Vergleichsansicht

Beide Seiten, vorherige ÜberarbeitungVorherige Überarbeitung
Nächste Überarbeitung		Vorherige Überarbeitung
Letzte ÜberarbeitungBeide Seiten, nächste Überarbeitung
pruefungen:bachelor:aud:loesungss14 [03.04.2019 17:45] – Nico Hambauerpruefungen:bachelor:aud:loesungss14 [31.07.2019 09:30] – Anpassungen Aufgabe 4 dom
Zeile 106: Zeile 106:
 **d)** \\ **d)** \\
 {{:pruefungen:bachelor:aud:floyd.png|}} {{:pruefungen:bachelor:aud:floyd.png|}}
 +
 +
 ==== 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;
 +}
 +</code>
  
-Loesung uebernommen aus dem Forum, eventuell gegenchecken +**b)**
-https://fsi.informatik.uni-erlangen.de/forum/thread/12419-Backtracking-SS14+
  
 +<code=java>
 +static int[][] allocateSolutionArray(boolean[][] brd, int mrl) {
 +    int[][] = null;
 +    int[][] sol = new int[brd.length][mrl];
  
- static boolean exists(boolean[][] brd, int r, int c) { +    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, r, c) && brd[r][c]) { // Diese Felder duerfen betreten werden 
- } +                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; 
 +} 
 +</code> 
 +**c)** 
 +<code=java> 
 +static boolean solve(boolean[][] brd, int[][] sol, int tf, int r, int c, int n) { 
 +    // 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 } }; 
 +     
 +    //Basisfall, letzter Wert muss hier noch gesetzt werden 
 +    if (n == tf) { 
 +        sol[r][c] = n; 
 +        return true; 
 +    } 
 +    for (int j = 0; j < jumps.length; j++) {
  
- static int[][] allocateSolutionArray(boolean[][] brd, int mrl) { +        // Wert setzen 
- int[][] sol = new int[brd.length][mrl]; +        sol[r][c] = n 
- for(int i = 0; i < brd.length; i++) { +
- for(int j = 0; j < mrl; j++) { +
- if(exists(brd, i, j)) { //Hier noch mit &&brd[i][j] verunden +
- sol[i][j] = 0; +
- } else { +
- sol[i][j] = -1; +
- } +
- } +
- } +
- return sol; +
- }+
  
-        //Achtung die folgende Implementierung enthaelt fehler! Lieber die Implementierung aus  +        // Brett brd und Loesungsfeld sol pruefen 
-        //<<Code zum Selber Testen>> verwenden! Diese ergibt mehr sinn! +        if (exists(brd, jumps[j][0], jumps[j][1]) && sol[jumps[j][0]][jumps[j][1]] == 0) {
- static boolean solve(boolean[][] brd, int[][] sol, int tf, int r, int c, int n) { +
- 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 } }; +
- 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; k++) { +
- if(exists(brd, jumps[k][0], jumps[k][1])) { +
- if(solve(brd, sol, tf, jumps[k][0], jumps[k][1], n + 1)) { +
- return true; +
- } +
- } +
- } +
- sol[r][c] = 0; +
- return false; +
- }+
  
-[[pruefungen:bachelor:aud:loesungss14:codezuaufgabe4|>>>code zum selber testen<<<]]+            // Rekursion 
 +            if (solve(brd, sol, tf, jumps[j][0], jumps[j][1], n + 1)) { 
 +                return true; 
 +            } 
 +            // Backtrack 
 +            sol[r][c] = 0; 
 +        }         
 +    }         
 +    return false; 
 +} 
 +</code> 
 + 
 + 
 + 
 + 
 +Alternative:
  
 ** a) *** ** a) ***
Zeile 210: Zeile 226:
  if (exists(brd, jump[0], jump[1]) && sol[jump[0]][jump[1]] == 0) {  if (exists(brd, jump[0], jump[1]) && sol[jump[0]][jump[1]] == 0) {
  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;
  }  }
 </code> </code>
 +[[pruefungen:bachelor:aud:loesungss14:codezuaufgabe4|>>>code zum selber testen<<<]]
  
 ====   5) Haldensortierung ====    ====   5) Haldensortierung ====   
Zeile 235: Zeile 247:
 \\ \\
 c) c)
 +<code java>
 +       //vorsicht! hier sind nicht alle faelle abgedeckt! was passiert bei rightId > w.length - 1 ? ggf mit Vorlesungsfolie 13 S.39 von ws18/19 gegenchecken!!!
  void reheap(W[] w, Comparator<W> c, int i, int k) {  void reheap(W[] w, Comparator<W> c, int i, int k) {
  int leftId = 2 * i + 1;  int leftId = 2 * i + 1;
Zeile 252: Zeile 266:
  }  }
  }  }
 +</code>
 \\ \\
 d) d)
Zeile 277: Zeile 292:
  HashMap<Character, Node> map = new HashMap<>();  HashMap<Character, Node> map = new HashMap<>();
  for(char c : s.toCharArray()) {  for(char c : s.toCharArray()) {
- if(map.get(c) == null) { + 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, value);+ map.put(c, new Node(c,1));
  }  }
  }  }