Du befindest dich hier: FSI Informatik » Prüfungsfragen und Altklausuren » Prüfungen im Bachelor-Studium (1. - 5. Semester) » aud » Forendiskussionen, bei Fragen bitte:   (Ü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:loesungws18 [17.06.2019 11:34] – Erster vollständiger Lösungsversuch der Klausur gabriel2029pruefungen:bachelor:aud:loesungws18 [19.07.2019 12:42] (aktuell) – Formatierung ADTs dom
Zeile 54: Zeile 54:
     int best = 0;     int best = 0;
     assert row >= 0 && row < n && col >= 0 && col < n;     assert row >= 0 && row < n && col >= 0 && col < n;
-    for (int r = row - <; r <= row + 1; r++) { +    for (int r = row - 1; r <= row + 1; r++) { 
-        if (r >= 0 && r < n) {+        // Betrachte, ob das angeforderte Feld überhaupt im Quadrat liegt 
 +        if (col < n - 1 && r >= 0 && r < n) { 
 +            // Die erreichte Summe wird genau dann maximal, wenn man 
 +            // den Weg wählt, bei dem man von diesem Nachbarfeld die 
 +            // maximale Summe erhält -> Eigentliche Rekursion
             best = Math.max(best, recurse(a, r, col + 1));             best = Math.max(best, recurse(a, r, col + 1));
         }         }
     }     }
          
 +    // Der Wert des aktuellen Feldes muss noch dazu addiert werden
     best += a[row][col];     best += a[row][col];
     return best;     return best;
Zeile 68: Zeile 73:
  
 <code=java> <code=java>
-public static int maxPathDP(int[][] a) {+public int maxPathDP(int[][] a) {
     int n = a.length;     int n = a.length;
     int best = 0;     int best = 0;
Zeile 89: Zeile 94:
                 b = Math.max(mem[row][col+1], mem[row-1][col+1]);                 b = Math.max(mem[row][col+1], mem[row-1][col+1]);
             } else {             } else {
-                 b = 0;  +                b = 0;  
-                 for(int r = row-1; r <= row+1; r++) { +                for(int r = row-1; r <= row+1; r++) { 
-                     b = Math.max(mem[r][col+1], b); +                    b = Math.max(mem[r][col+1], b); 
-                 }+                }
      }      }
                          
Zeile 102: Zeile 107:
          
     //Suche das Maximum in der ersten Spalte     //Suche das Maximum in der ersten Spalte
-    for(int i = 0; i < mem.length; i++) {+    for(int i = 0; i < n; i++) {
         if(mem[i][0] > best) {         if(mem[i][0] > best) {
             best = mem[i][0];             best = mem[i][0];
Zeile 114: Zeile 119:
 === a) === === a) ===
 ^ Fach      ^ k //(verkettete Liste, zuletzt eingetragener Schlüssel rechts) //      ^  ^ Fach      ^ k //(verkettete Liste, zuletzt eingetragener Schlüssel rechts) //      ^ 
-| 0    | E =>    +| 0    | E =>    
 | 1      | 1     
 | 2    |? =>    |  | 2    |? =>    | 
Zeile 151: Zeile 156:
 private long helperNums(T v, long num) {  private long helperNums(T v, long num) { 
     // Füge Preorder-Knoten hinzu     // Füge Preorder-Knoten hinzu
-    nums.add(v, num);+    nums.put(v, num);
          
     // Nächster Knoten bekommt eine um eins höhere Nummerierung     // Nächster Knoten bekommt eine um eins höhere Nummerierung
Zeile 158: Zeile 163:
     // Schaue, ob in sptree schon eine Adjazenzliste angelegt wurde     // Schaue, ob in sptree schon eine Adjazenzliste angelegt wurde
     // (eigentlich ist das ein Set, das ist aber nicht relevent)     // (eigentlich ist das ein Set, das ist aber nicht relevent)
-    if (!sptree.contains(v)) sptree.put(v, new HashSet<>()); +    if (!sptree.containsKey(v))
-    +     sptree.put(v, new HashSet<>()); 
 +    }
     // Betrachte alle Nachbarn im Graphen     // Betrachte alle Nachbarn im Graphen
     for (T w : graph.get(v)) {     for (T w : graph.get(v)) {
         // Überprüfe, ob Nachbar schon besucht wurde         // Überprüfe, ob Nachbar schon besucht wurde
-        if (!nums.contains(w) {+        if (!nums.containsKey(w) {
             sptree.get(v).add(w); // Füge Knoten zum Spannbaum hinzu             sptree.get(v).add(w); // Füge Knoten zum Spannbaum hinzu
-            num = helperNums(v, num); // Führe rekursiv die dfs-Nummerierung aus+            num = helperNums(w, num); // Führe rekursiv die dfs-Nummerierung aus 
         }         }
     }     }
Zeile 176: Zeile 182:
 <code=java> <code=java>
 private long helperLows(T v) { private long helperLows(T v) {
-    long low = nums.get(v);+    long low = nums.get(v); // num-Wert des Knoten selbst
          
     for (T w : sptree.get(v)) {     for (T w : sptree.get(v)) {
-        long wLow = helperLows(w);+        long wLow = helperLows(w); // low-Wert der Nachbarknoten
         if (wLow >= nums.get(v)) {         if (wLow >= nums.get(v)) {
 +            // Fall, in dem Knoten zu der Menge der Artikulationspunkte hinzugefügt werden muss
             aps.add(v);             aps.add(v);
         }         }
Zeile 187: Zeile 194:
          
     for (T w : graph.get(v)) {     for (T w : graph.get(v)) {
-        low = Math.min(low, graph.nums(w));+        low = Math.min(low, nums.get(w)); // num-Werte der Nachbarknoten
     }     }
          
Zeile 197: Zeile 204:
  
 === a) === === a) ===
-//push4(ts, x, y) = Push(Push(Push(Push(ts, x+1, y), x, y+1), x-1, y), x, y-1)// +<code=java> 
 +push4(ts, x, y) = Push(Push(Push(Push(ts, x+1, y), x, y+1), x-1, y), x, y-1)// 
 +</code>
 === b) === === b) ===
-//paintHLine(c, x, y, n, nc) = ...//+<code=java> 
 +paintHLine(c, x, y, n, nc) = 
  
-//... = c, falls n < = 0//+... = c, falls n < = 0
  
-//... = paintHLine(Paint(c, x, y, nc), x + 1, y, n - 1, nc), sonst/+... = paintHLine(Paint(c, x, y, nc), x + 1, y, n - 1, nc), sonst 
-    +</code>
 === c) === === c) ===
-//getCol(New, x, y) = White//+<code=java> 
 +getCol(New, x, y) = White
  
-//getCol(Paint(c, a, b, col), x, y) = ...//+getCol(Paint(c, a, b, col), x, y) = ...
  
-//... = col, falls x = a und y = b// +... = col, falls x = a und y = b
- +
-//... = getCol(c, x, y), sonst//+
  
 +... = getCol(c, x, y), sonst
 +</code>
 === d) === === d) ===
-//floodH(c,Empty,oc,nc) = c //+<code=java> 
 +floodH(c,Empty,oc,nc) = c 
  
-//floodH(c, Push(ts, x, y), oc, nc) = ...//+floodH(c, Push(ts, x, y), oc, nc) = ...
  
-//... = floodH(Paint(c, x, y, nc), push4(ts, x, y), oc, nc), falls getCol(c, x, y) = oc// +... = floodH(Paint(c, x, y, nc), push4(ts, x, y), oc, nc), falls getCol(c, x, y) = oc
- +
-//... = floodH(c, ts, oc, nc), sonst //+
  
 +... = floodH(c, ts, oc, nc), sonst 
 +</code>
 ____________________________________________________________________ ____________________________________________________________________
 ====   Aufgabe 6 (Radix-Exchange-Sortierung)==== ====   Aufgabe 6 (Radix-Exchange-Sortierung)====
 <code=java> <code=java>
 public void sort(List<String> in) { public void sort(List<String> in) {
-    sort(int, 0, new BucketPool(45));+    sort(in, 0, new BucketPool(45));
 } }
  
Zeile 234: Zeile 245:
     List<List<String>> bs;     List<List<String>> bs;
     if (charPos < 5) {     if (charPos < 5) {
-        List<List<String>> buckets = bp.getBuckets(9); +        bs = bp.getBuckets(9); 
-         +        Iterator<String> it = in.iterator(); 
-        for (Iterator<String> it = in.iterator(); it.hasNext();) {+        while (it.hasNext()) {
             String nextString = it.next();             String nextString = it.next();
             char c = nextString.charAt(charPos);             char c = nextString.charAt(charPos);
Zeile 242: Zeile 253:
             // Nur Elemente, die an dieser Stelle einen Char != 0 haben,             // Nur Elemente, die an dieser Stelle einen Char != 0 haben,
             // in andere Liste schieben             // in andere Liste schieben
-            if (c >= '1' && c <= '9') {+            if (c != '0') { 
 +                bs.get(Character.getNumericValue(c)).add(nextString);
                 it.remove();                 it.remove();
-                buckets.get(c - '1').add(nextString); 
             }                      }         
         }         }
Zeile 256: Zeile 267:
             sort(bucket, charPos + 1, bp);             sort(bucket, charPos + 1, bp);
                          
-            /* Zum Verstädnis:+            /* Zum Verständnis:
              * Dadurch, dass die Strings in erster Priorität nach dem Char              * Dadurch, dass die Strings in erster Priorität nach dem Char
              * an Position c sortiert sind, wird die Liste korrekt sortiert:              * an Position c sortiert sind, wird die Liste korrekt sortiert:
              * -> Durch sort wird eine Teilliste korrekt sortiert              * -> Durch sort wird eine Teilliste korrekt sortiert
              * -> Die sortierten Teillisten werden nach dem ersten Character              * -> Die sortierten Teillisten werden nach dem ersten Character
-                 zusammen gebaut -> korrekte Sortierung+                zusammen gebaut -> korrekte Sortierung
              */              */