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
Letzte ÜberarbeitungBeide Seiten, nächste Überarbeitung
pruefungen:bachelor:aud:loesungws18 [17.06.2019 10:56] – gabriel2029pruefungen:bachelor:aud:loesungws18 [14.07.2019 13:15] – Dbadtf_385
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 => K    | +| 0    | E => U    | 
 | 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 202: Zeile 209:
 //paintHLine(c, x, y, n, nc) = ...// //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//
          
 === c) === === c) ===
-//getCol(New,x,y) = White +//getCol(New, x, y) = White// 
-getCol(Paint(c, a, b, col), x, y) = To-Do//+ 
 +//getCol(Paint(c, a, b, col), x, y) = ...// 
 + 
 +//... = col, falls x = a und y = b// 
 + 
 +//... = getCol(c, x, y), sonst//
  
 === d) === === d) ===
-//floodH(c,Empty,oc,nc) = c // oc =􏰁 FoldC, nc =􏰁 FnewC, FoldC ̸= FnewC +//floodH(c,Empty,oc,nc) = c //
-floodH(c,Push(ts,x,y),oc,nc) =To-Do+
  
 +//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(c, ts, oc, nc), sonst //
  
 ____________________________________________________________________ ____________________________________________________________________
-====   Aufgabe 6 (Radix-Exchange Sortierung)====+====   Aufgabe 6 (Radix-Exchange-Sortierung)==== 
 +<code=java> 
 +public void sort(List<String> in) { 
 +    sort(in, 0, new BucketPool(45)); 
 +} 
 + 
 +private void sort(List<String> in, int charPos, BucketPool bp) { 
 +    List<List<String>> bs; 
 +    if (charPos < 5) { 
 +        bs = bp.getBuckets(9); 
 +        Iterator<String> it = in.iterator(); 
 +        while (it.hasNext()) { 
 +            String nextString = it.next(); 
 +            char c = nextString.charAt(charPos); 
 +             
 +            // Nur Elemente, die an dieser Stelle einen Char != 0 haben, 
 +            // in andere Liste schieben 
 +            if (c != '0') { 
 +                bs.get(Character.getNumericValue(c)).add(nextString); 
 +                it.remove(); 
 +            }          
 +        } 
 +         
 +        // In in sind im Moment nur noch Strings, 
 +        // die an dieser Stelle 0 sind => Lässt sich wie der Rest sortieren 
 +        sort(in, charPos + 1, bp); 
 +         
 +        // Für alle anderen Strings wurden die eigenen Buckets angelegt 
 +        for (List<String> bucket : bs) { 
 +            sort(bucket, charPos + 1, bp); 
 +             
 +            /* Zum Verständnis: 
 +             * Dadurch, dass die Strings in erster Priorität nach dem Char 
 +             * an Position c sortiert sind, wird die Liste korrekt sortiert: 
 +             * -> Durch sort wird eine Teilliste korrekt sortiert 
 +             * -> Die sortierten Teillisten werden nach dem ersten Character 
 +             *    zusammen gebaut -> korrekte Sortierung 
 +             */ 
 +             
 +            in.addAll(bucket); 
 +        } 
 +         
 +        // Hier muss man die Buckets wieder aus dem Pool entfernen 
 +        bp.dropBuckets(bs); 
 +    } 
 +} 
 +</code> 
 +Anmerkung zu der Stelle ''move strings with '1' - '9' from in to bs'': Hier scheint es prinzipiell zwei andere Möglichkeiten zu geben: 
 +  * Arbeit mit ''for (String nextString : in)'': Nicht wirklich zu empfehlen, da man beim Iterieren durch die Liste Elemente aus dieser entfernen muss. Das kann zu Fehlern beim Iterieren führen. Außerdem ist nicht zwingend vorgeschrieben, dass die Liste keine Duplikate enthält. Bei ''in.remove(nextString)'' würde man diese entfernen. 
 +  * Man iteriert mit einem Index ''i'' über die Liste. Hier muss man beim Entfernen eines Elementes aus der Liste entsprechend ''i'' um eins dekrementieren (um eins verkleinern), damit keine Elemente ausgelassen werden. Diese Lösung funktioniert, ist aber etwas schwieriger zu implementieren. Auch möglich ist es, mit ''i = in.size() - 1'' zu beginnen und abwärts zu zählen. Falls ein Element entfernt wird, wird ''i'' in einem Schritt zusätzlich um 1 verkleinert. Wenn ''i < 0'' ist, wird abgebrochen.