xMax
, xSuf
sowie i
zusätzlich angelegt.x.length
.r
und rn
angelegt, die in jeder Schleiteniteration ungefähr doppelt so groß gewählt istrn
in jedem Schritt um eine weitere Reihe x
ergänzt wird. Ansonsten kann man auch durch die Betrachtung des Quellcodes auf ähnliche Ergebnisse kommen.Anmerkung zum O-Kalkül: Grundsätzlich beschreibt das O-Kalkül immer eine obere Schranke, wenn z. B. eine Funktion f(n) in O(n) liegt, liegt sie auch in O(n^2), aber nicht unbedingt in O(1) (vgl. dazu auch Lösungsvorschlag der Miniklausur dieses Semesters).
CatRoom
ist Unterklasse von CatBase
CatRoom
gibt es maximal ein CatHouse
, also wird jeder CatRoom
von höchsten einem CatHouse
referenziert (in KonzMod-Logik würde also insbesondere die funktionale Abhängigkeit CatRoom
→ CatHouse
gelten).finally
-Block wird immer ausgeführt.a
und b
erfüllt ist, wird der Code X
ausgeführt, ist a
wahr und b
falsch, wird der Code Y
ausgeführt, ansonsten, also wenn a
nicht erfüllt ist, muss die Bedingung Q
ohne Änderung erfüllt sein.private int recurse(int[][] a, int row, int col) { int n = a.length; int best = 0; assert row >= 0 && row < n && col >= 0 && col < n; for (int r = row - 1; r <= row + 1; r++) { // 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)); } } // Der Wert des aktuellen Feldes muss noch dazu addiert werden best += a[row][col]; return best; }
public int maxPathDP(int[][] a) { int n = a.length; int best = 0; // Feld initialisieren und letzte Spalte befüllen int[][] mem = new int[n][n]; for(int row = 0; row < n; row++) { mem[row][n-1] = a[row][n-1]; } int b = 0; // von der vorletzten Spalte bis zur vordersten for(int col = n-2; col >= 0; col--) { // Suche den größten Nachbarn in der rechten Spalte in einer Reihe // darüber, darunter oder gleicher Reihe und speichere dessen Wert in b for(int row = 0; row < n; row++) { if (row == 0) { b = Math.max(mem[row][col+1], mem[row+1][col+1]); } else if(row == n-1) { b = Math.max(mem[row][col+1], mem[row-1][col+1]); } else { b = 0; for(int r = row-1; r <= row+1; r++) { b = Math.max(mem[r][col+1], b); } } // Der neue Wert in mem ist der alte in a plus b mem[row][col] = a[row][col] + b; } } } //Suche das Maximum in der ersten Spalte for(int i = 0; i < n; i++) { if(mem[i][0] > best) { best = mem[i][0]; } } return best; }
Fach | k (verkettete Liste, zuletzt eingetragener Schlüssel rechts) |
---|---|
0 | E ⇒ U |
1 | |
2 | ? ⇒ |
3 | |
4 | Y ⇒ ! ⇒ A |
5 | B ⇒ |
6 | |
7 | D ⇒ |
k | sondierte Fächer und Art der Kollision |
---|---|
B | 5 |
Y | 4 |
E | 0 |
! | 4 (P)⇒ 5 (P)⇒ 6 |
A | 4 (P)⇒ 5 (P)⇒ 6 (S)⇒ 7 |
U | 0 (P)⇒ 1 |
D | 7 (S)⇒ 0 (P)⇒ 1 (S)⇒ 2 |
? | 2 (S)⇒ 3 |
Fach | k | Streufunktion (i) |
---|---|---|
0 | E | 0 |
1 | A | 1 |
2 | U | 1 |
3 | ! | 1 |
4 | Y | 0 |
5 | B | 0 |
6 | ? | 2 |
7 | D | 0 |
private long helperNums(T v, long num) { // Füge Preorder-Knoten hinzu nums.put(v, num); // Nächster Knoten bekommt eine um eins höhere Nummerierung num++; // Schaue, ob in sptree schon eine Adjazenzliste angelegt wurde // (eigentlich ist das ein Set, das ist aber nicht relevent) if (!sptree.containsKey(v)){ sptree.put(v, new HashSet<>()); } // Betrachte alle Nachbarn im Graphen for (T w : graph.get(v)) { // Überprüfe, ob Nachbar schon besucht wurde if (!nums.containsKey(w) { sptree.get(v).add(w); // Füge Knoten zum Spannbaum hinzu num = helperNums(w, num); // Führe rekursiv die dfs-Nummerierung aus } } return num; }
private long helperLows(T v) { long low = nums.get(v); // num-Wert des Knoten selbst for (T w : sptree.get(v)) { long wLow = helperLows(w); // low-Wert der Nachbarknoten if (wLow >= nums.get(v)) { // Fall, in dem Knoten zu der Menge der Artikulationspunkte hinzugefügt werden muss aps.add(v); } low = Math.min(low, wLow); } for (T w : graph.get(v)) { low = Math.min(low, nums.get(w)); // num-Werte der Nachbarknoten } return low; }
push4(ts, x, y) = Push(Push(Push(Push(ts, x+1, y), x, y+1), x-1, y), x, y-1)//
paintHLine(c, x, y, n, nc) = ... = c, falls n < = 0 ... = paintHLine(Paint(c, x, y, nc), x + 1, y, n - 1, nc), sonst
getCol(New, x, y) = White getCol(Paint(c, a, b, col), x, y) = ... ... = col, falls x = a und y = b ... = getCol(c, x, y), sonst
floodH(c,Empty,oc,nc) = c 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
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); } }
Anmerkung zu der Stelle move strings with '1' - '9' from in to bs
: Hier scheint es prinzipiell zwei andere Möglichkeiten zu geben:
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.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.