Vor kurzem erhielt ich per Email folgende Frage, die ich hier nur verkürzt und sinngemäß darstellen möchte:
Ich habe 53 Spieler, die paarweise gegeneinander spielen sollen. Nach Ihrer Internetseite sind das 1378 Paarungen, so dass am Ende jeder gegen jeden mal gespielt hat. Jetzt sollen an jedem Tag jeweils die Paarungen so gebildet werden, dass es zu keinen Dopplungen kommt.
Jetzt kenne ich aus der 11. Klasse Informatik nur eine mögliche Lösung für ein KO-Spielsystem, die ich zunächst als Antwort zurückschickte:
Sie mischen alle Teilnehmer zufällig (das ginge z.B. auch mit Excel und einer Liste). Dann ziehen Sie von vorne (Kopf der Warteschlange) immer zwei aufeinanderfolgende Karten. Das wäre das erste Paar. Dann die nächsten zwei etc. Der Gewinner einer Paarung wird jeweils wieder unter den hinten an die Warteschlange angehängt So reduzieren sich die Karten schrittweise bis ein Gewinner feststeht.
Was aber gemeint war, war ein sogenanntes Rundenturnier (Round-Robin). Da die Organisation dabei gar nicht so einfach ist (z.B. durch eine beschränkte Anzahl an Plätzen wie bei Tennisturnieren) kann eine Lösung relativ kompliziert werden. Zum Glück hat sich jemand schon einen Kopf gemacht und die Internetseite turniereditor.de geschaffen. Hier lassen sich schonmal solche Rundenturniere auswerten. Auch die Internetseite www.oxfordcroquet.com/manage/roundrobin/ ermöglicht eine solche Organisation. Aber wie programmiert man so etwas?
Hierzu bedient man sich des Scheduling-Algorithmus. Dieser läuft wie folgt ab: Angenommen alle Spielernamen stünden auf Karten. Lege alle Karten so in zwei Reihen, dass in der oberen und unteren Reihe genau gleich viele Karten liegen. Bei einer ungeraden Anzahl wird ein Joker ergänzt. Der entsprechende Spielpartner hätte dann quasi frei. Bei 10 Spielern (A bis J) ergäbe sich folgendes Bild:
A-B-C-D-E F-G-H-I-J
Hiermit ergeben sich als erste Paarung A-F, B-G, C-H, D-I, E-J. Für die weiteren Paarungen bleibt A an der Position fest und alle anderen Karten werden im Uhrzeigersinn um 1 weiter geschoben
A-F-B-C-D G-H-I-J-E
Die neuen Paarungen wären dann A-G, F-H, B-I, C-J und D-E. Das macht man solange bis die Ausgangssituation wieder hergestellt ist.
Damit wäre auch die Programmieraufgabe klar:
Programmieraufgabe
Implementiere den oben dargestellten Scheduling-Algorithmus für ein Round-Robin-System.