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.
Beide Seiten, vorherige ÜberarbeitungVorherige ÜberarbeitungNächste Überarbeitung | Vorherige ÜberarbeitungNächste ÜberarbeitungBeide Seiten, nächste Überarbeitung | ||
pruefungen:bachelor:aud:loesungws18 [17.06.2019 10:56] – gabriel2029 | pruefungen:bachelor:aud:loesungws18 [07.07.2019 09:22] – SpeedyGonzalez | ||
---|---|---|---|
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 && | ||
+ | // 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, | best = Math.max(best, | ||
} | } | ||
} | } | ||
| | ||
+ | // 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: | ||
< | < | ||
- | public | + | 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], | b = Math.max(mem[row][col+1], | ||
} else { | } else { | ||
- | b = 0; | + | |
- | | + | for(int r = row-1; r <= row+1; r++) { |
- | | + | b = Math.max(mem[r][col+1], |
- | | + | } |
} | } | ||
| | ||
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 // | ^ Fach ^ k // | ||
- | | 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, | + | if (!sptree.containsKey(v)){ |
- | | + | sptree.put(v, |
+ | | ||
// Betrachte alle Nachbarn im Graphen | // Betrachte alle Nachbarn im Graphen | ||
for (T w : graph.get(v)) { | for (T w : graph.get(v)) { | ||
// Überprüfe, | // Überprüfe, | ||
- | if (!nums.contains(w) { | + | if (!nums.containsKey(w) { |
sptree.get(v).add(w); | sptree.get(v).add(w); | ||
num = helperNums(v, | num = helperNums(v, | ||
Zeile 176: | Zeile 182: | ||
< | < | ||
private long helperLows(T v) { | private long helperLows(T v) { | ||
- | long low = nums.get(v); | + | long low = nums.get(v); |
| | ||
for (T w : sptree.get(v)) { | for (T w : sptree.get(v)) { | ||
- | long wLow = helperLows(w); | + | long wLow = helperLows(w); |
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, | + | low = Math.min(low, |
} | } | ||
| | ||
Zeile 202: | Zeile 209: | ||
// | // | ||
- | ... c | + | //... = c, falls n < = 0// |
- | ... paintHLine(Paint(c, | + | //... = paintHLine(Paint(c, |
| | ||
=== c) === | === c) === | ||
- | // | + | // |
- | getCol(Paint(c, | + | |
+ | //getCol(Paint(c, | ||
+ | |||
+ | //... = col, falls x = a und y = b// | ||
+ | |||
+ | //... = getCol(c, x, y), sonst// | ||
=== d) === | === d) === | ||
- | // | + | // |
- | floodH(c, | + | |
+ | //floodH(c, Push(ts, x, y), oc, nc) = ...// | ||
+ | |||
+ | //... = floodH(Paint(c, | ||
+ | |||
+ | //... = floodH(c, ts, oc, nc), sonst // | ||
____________________________________________________________________ | ____________________________________________________________________ | ||
- | ==== | + | ==== |
+ | < | ||
+ | public void sort(List< | ||
+ | sort(in, 0, new BucketPool(45)); | ||
+ | } | ||
+ | |||
+ | private void sort(List< | ||
+ | List< | ||
+ | if (charPos < 5) { | ||
+ | bs = bp.getBuckets(9); | ||
+ | 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 != ' | ||
+ | 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< | ||
+ | sort(bucket, | ||
+ | |||
+ | /* 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 | ||
+ | | ||
+ | */ | ||
+ | |||
+ | in.addAll(bucket); | ||
+ | } | ||
+ | |||
+ | // Hier muss man die Buckets wieder aus dem Pool entfernen | ||
+ | bp.dropBuckets(bs); | ||
+ | } | ||
+ | } | ||
+ | </ | ||
+ | Anmerkung zu der Stelle '' | ||
+ | * Arbeit mit '' | ||
+ | * Man iteriert mit einem Index '' |