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
pruefungen:bachelor:aud:loesungss14 [28.05.2019 14:50] – Dbadtf_385pruefungen:bachelor:aud:loesungss14 [31.07.2019 09:54] (aktuell) – Verbesserung Aufgabe 5c,d 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 ====   
  
 \\ \\
-a) Das Element 0 wird im nächsten Schritt versickert. Daher werden die Kindelemente 5 und 2 verglichen. 5 ist größer, daher wird 5 mit 0 verglichen. 5 ist größer, weshalb 5 und 0 getauscht werden.+a)  
 + 
 +Das Element 0 wird im nächsten Schritt versickert. Daher werden die Kindelemente 5 und 2 verglichen. 5 ist größer, daher wird 5 mit 0 verglichen. 5 ist größer, weshalb 5 und 0 getauscht werden.
       => Kreuz bei Stelle 2, 5 und 6       => Kreuz bei Stelle 2, 5 und 6
       => Resultat: { 6, 7, 5, 3, 1, 0, 2 }       => Resultat: { 6, 7, 5, 3, 1, 0, 2 }
 \\ \\
-b) Ergebnis: { 6, 3, 5, 2, 1, 0, 7 }\\+b)  
 + 
 +Ergebnis: { 6, 3, 5, 2, 1, 0, 7 }\\
 \\ \\
 c) c)
 <code java> <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; +    int rightId = leftId + 1; 
- int rightId = leftId + 1; +    int kidId; 
- int kidId; + 
-  +    // nur 1 Kind (linkes) vorhanden; pruefen, ob Indizes innerhalb des Arrays liegen 
- if(leftId <= k) { +    if (leftId <= k && rightId > k) { 
- if(rightId > k || c.compare(w[leftId], w[rightId]) > 0) { +        if (c.compare(w[leftId], w[i]) > 0) { // Falls Kind groesser, dann tauschen 
- kidId = leftId; +            swap(w, leftId, i); 
- } else { +        } 
- kidId = rightId; +    } else { 
- } +        // 2 Kinder vorhanden, pruefen, ob rechtes Kind innerhalb des Arrays liegt 
- if(c.compare(w[kidId], w[i]) > 0) { +        if (rightId <= k) { 
- swap(w, i, kidId); +            // groesseres der beiden Kinder in kidId speichern 
- reheap(w, c, kidId, k); +            kidId = c.compare(w[leftId], w[rightId]) > 0 ? leftId : rightId; 
- } + 
- } +            // Schauen, ob Kind groesser ist, als aktuelles Element, falls ja, dann tauschen 
- }+            if (c.compare(w[kidId], w[i]) > 0) { 
 +                swap(w, kidId, i); 
 +                reheap(w, c, kidId, k); 
 +            } 
 +        } 
 +    } 
 +}
 </code> </code>
 \\ \\
 d) d)
- void heapSort(W[] w, Comparator<W> c) { +<code=java> 
- int n = w.length; +void heapSort(W[] w, Comparator<W> c) { 
-  +    int n = w.length;
- // Phase 1: Max-Heap-Eigenschaft herstellen +
- //          (siehe Teilaufgabe a) +
- for(int i = n / 2 - 1; i >= 0; i--) { +
- reheap(w, c, i, n-1); // Beide Grenzen inklusiv +
- } +
-  +
- // Phase 2: jeweils Maximum entnehmen und sortierte Liste am Ende aufbauen +
- //          (siehe Teilaufgabe b) +
- for(int i = n - 1; i > 0; i--) { +
- swap(w, 0, i); +
- reheap(w, c, 0, i - 1); +
- } +
- }+
                  
 +    // Phase 1: Halde aufbauen
 +    for (int i = n / 2; i >= 0; i--) {
 +        reheap(w, c, i, n - 1);
 +    }
 +
 +    // Phase 2: Maximum entnehmen und sortierte Liste am Ende aufbauen
 +    for (int i = n - 1; i > 0; i--) {
 +        // Maximum an das Ende der Halde tauschen
 +        swap(w, 0, i);
 +
 +        // Nach vorne getauschtes Element einsickern lassen und Haldeneigenschaft wiederherstellen
 +        reheap(w, c, 0, i - 1);
 +    }
 +} 
 +</code>
 +
 ====   6) Bäume und Rekursion====    ====   6) Bäume und Rekursion====   
 <code java>  <code java>