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
Letzte ÜberarbeitungBeide Seiten, nächste Überarbeitung
pruefungen:bachelor:aud:loesungss14 [28.05.2019 14:50] – Dbadtf_385pruefungen: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 ====