- left
- right
- up
- down
Aufgabe 1 habe ich einfach mit Backtracking gelöst, sicher gab es hier schönere Lösungen...
Aufgabe 2 habe ich reines Brute-Force verwendet. Ich habe eine Optimierung gefunden, aber nicht implementiert. Wie habt ihr das optimiert?
Aufgabe 3 habe ich Monte-Carlo verwendet, mich würde interessieren, ob jemand hier stattdessen was mathematisch bewiesen/ausgerechnet hat.
Aufgabe 5 habe ich mit einem Graphenalgorithmus für den Maximalen Fluss mit den Minimalen Kosten gelöst. Hier interessiert mich auch richtig, wie ihr das gemacht habt!
Ich habe kurze, kompakte Dokus
Aufgabe 1 habe ich mit einem bipartiten Graphen gelöst. Dazu habe ich bewiesen, dass der Graph, wenn genau eine korrekte Zuordnung existiert (das bedeutet praktisch „perfektes Matching“), immer mindestens einen Knoten enthält, der den Grad 1 hat. So kann man immer diesen (mindestens) einen Knoten zuordnen und erreicht für die Zuordnung lineare Laufzeit zur Anzahl der Kanten. Die Errechnung des Graphen lässt sich allerdings nur durch O(n²) einschränken.
Aufgabe 2 habe ich auch mit Brute-Force gelöst (etwa bis zu 7,1*10^9 Möglichkeiten als sichere obere Schranke). Mein Backtracking-Verfahren hat immer nur passende Teile versucht anzusetzen; dadurch hat es für kein Beispiel länger als 0.1 Sekunden gebraucht.
Aufgabe 3 habe ich durch einfache Simulation der Spiele gelöst. Durch eine mehr oder weniger ausgeschmückte graphische Benutzeroberfläche (ein Fenster mit Button) kann man die Simulationen sogar ganz bequem beenden. Bei K. O. werden die Paare vorher zufällig zugeordnet.
Bei A3 hätte man die Gewinnwahrscheinlichkeit beim K. O. System sicher auch ausrechnen können, aber ich wollte nicht zu viel Arbeit in diese Aufgabe stecken, weil ich die Simulationslösung (die genau genug ist) schon fertig hatte.
https://github.com/LinuxUserJTB/Einsendung_BwInf_39_1
Aufgabe 1: Endlosschleife, die solange die Wörter zuordnet, bis keine eindeutige Zuordnung mehr möglich ist.
Aufgabe 2: Auch Brute-Force
Aufgabe 3: Liga via Zufall. K.O.-Turnier via Zufall und Berechnung. Wenn die Startanordnung fürs K.O.-Turnier bekannt ist, kann man die genaue Wahrscheinlichkeit berechnen, mit der ein Spieler gewinnt (via Binomialverteilung). Ich bin dann einfach viele verschiedene zufällige Startpositionen durchgegangen, um eine Annäherung für den Durchschnitt zu erhalten.
Für spielstaerken1.txt, spielstaerken2.txt und spielstaerken4.txt kann man so innerhalb von paar Sekunden auch die exakte Wahrscheinlichkeit berechnen (ohne Benutzung von Zufällen).
Und hier die Lösung meines Teams:
https://github.com/christopher-besch/bwinf39_round1