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 [04.04.2019 08:28] – 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 ==== 
  
-Loesung uebernommen aus dem Forum, eventuell gegenchecken 
-https://fsi.informatik.uni-erlangen.de/forum/thread/12419-Backtracking-SS14 
  
 +==== 4) Backtracking ====
 +**a)**
 <code java> <code java>
- static boolean exists(boolean[][] brd, int r, int c) { +static boolean exists(boolean[][] brd, int r, int c) { 
- if(brd[r] == null || brd[r].length < 1) { +    if (brd[r] == null || brd[r].length < 1) { // Zeilen null oder leer 
- return false; +        return false; 
- } +    }  
- if(r >= brd.length || c >= brd[r].length || r < 0 || c < 0) { +    if (r >= brd.length || c >= brd[r].length || r < 0 || c < 0) { // Indizes ausserhalb der Grenzen 
- return false; +        return false; 
- } +    } 
- return true; +    return true; 
- }+} 
 +</code>
  
- static int[][] allocateSolutionArray(boolean[][] brd, int mrl) { +**b)**
- int[][] sol = new int[brd.length][mrl]; +
- 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  +<code=java> 
-        //<<Code zum Selber Testen>> verwenden oder weiter scrollen +static int[][] allocateSolutionArray(boolean[][] brd, int mrl) { 
- static boolean solve(boolean[][] brd, int[][] sol, int tf, int r, int c, int n) { +    int[][] = null; 
- int[][] jumps = { { r + 2, c - 1 }, { r + 1, c - 2 }, { r - 1, c - 2 }, { r - 2, c - 1 }, { r - 2, c + 1 }, +    int[][] sol = new int[brd.length][mrl]; 
- { r - 1, c + 2 }, { r + 1, c + 2 }, { r + 2, c + 1 } }; + 
- if(sol[r][c] >= 1) { +    for (int r = 0; r < brd.length; r++) { 
- return false; +        for (int c = 0; c < mrl; c++) { 
- } +            if (exists(brd, r, c) && brd[r][c]) { // Diese Felder duerfen betreten werden 
- if(n == tf) { +                sol[r][c] = 0; 
- sol[r][c] = n; +            } else { 
- return true; +                sol[c][c] = -1; // Felder mit -1 vorbelegen 
- } +            } 
- sol[r][c] = n; +        } 
- for(int k = 0; k < jumps.length; k++) { +    } 
- if(exists(brd, jumps[k][0], jumps[k][1])) { +    return sol; 
- if(solve(brd, sol, tf, jumps[k][0], jumps[k][1], n + 1)) { +}
- return true; +
- } +
- } +
- } +
- sol[r][c] = 0; +
- return false; +
- }+
 </code> </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++) {
  
-[[pruefungen:bachelor:aud:loesungss14:codezuaufgabe4|>>>code zum selber testen<<<]]+        // Wert setzen 
 +        sol[r][c] = n  
 + 
 +        // Brett brd und Loesungsfeld sol pruefen 
 +        if (exists(brd, jumps[j][0], jumps[j][1]) && sol[jumps[j][0]][jumps[j][1]] == 0) { 
 + 
 +            // 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 220: Zeile 235:
  }  }
 </code> </code>
 +[[pruefungen:bachelor:aud:loesungss14:codezuaufgabe4|>>>code zum selber testen<<<]]
  
 ====   5) Haldensortierung ====    ====   5) Haldensortierung ====   
Zeile 276: 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));
  }  }
  }  }