Die heutige Aufgabe stammt von einem Schüler meiner aktuellen elften Klasse. Da mir bei der Diskussion mit dem Schüler mehrere Lösungen eingefallen sind, möchte ich hier ein paar Lösungen präsentieren.
Aufgabe
In einem Turnier sollen n Spieler gegeneinander antreten. Dabei soll jeder gegen jeden spielen, wer am Schluss am meisten Punkte hat, gewinnt.
a) Wie viele Spiele gibt es?
b1) Implementiere eine Lösung nur mit Hilfe von eindimensionalen Feldern.
b2) Implementiere eine Lösung auf Basis von Graphen.
b3) Wie ließe sich das Problem mit Excel oä. lösen
Die Frage b3) kommt urspünglich von meinem Schüler, daher habe ich sie mit aufgelistet. Allerdings fällt mir nur eine Lösung mit Hilfe von VBA ein, daher kann man auch gleich einen allgemeinen Ansatz versuchen. Jetzt aber zu ein paar Erklärungen:
zu a): Ein rein kombinatorisches Problem aus der Mathematik. Jeder der n Spieler spielt gegen einen der n-1 anderen Spieler. Dabei gibt es keine Unterscheidung, ab Spieler A gegen B oder B gegen A spielt: n*(n-1)/2
zu b1) Die Spielernamen A, B, C, … seien in einem Feld (Array) gegeben:
spieler = [A,B,C,D,E]
Mit Hilfe des Feldes spieler wird ein zweites Array mit Paarungen gebildet:
paarungen = [(A,B), (A,C), (A,D), (A,E),
(B,C), (B,D), (B,E),
(C,D), (C,E),
(D,E)]Das Feld paarungen wird durch einen beliebigen Algorithmus gemischt.
paarungen = [(B,E), (A,C), (A,E), (A,D),
(B,C), (B,D), (A,B),
(C,D), (D,E),
(C,E)]Dann kann von vorne (oder auch hinten) beginnend eine Paarung aus dem Array entfernt werden. D.h. die erste Partie wäre: (B,E), dann (A,C) . E kann erstmal nicht spielen. Im nächsten Durchgang kommt dann (A,E) dran und dann kommt das Problem bei dieser Lösung: Die Partie (A,D) muss übergangen werden, da a ja schon belegt ist. Als nächstes wäre damit (B,C) dran. Das geht dann immer so weiter.
zu b2) Fasst man das ganze als Graph (unser aktuelles Thema, daher bin ich wohl auch erst mal auf diese Lösungen gekommen) auf, so gehen von Spieler A vier Kanten zu den Spielern B, C, D, E. Von B gehen Kanten zu C, D, E. Eine Kante zu A braucht man nicht mehr, da diese Kante ja von A aus gezogen wurde.
Um nun das Spiel zu organisieren, wählt man bei A eine belibiege Kante, zum Beispiel die zu B. Dann müssen alle anderen Kanten, die von A oder B ausgehen als blockiert gemerkt werden, da dies andere mögliche Partien sind, die sich aber im Moment nicht realisieren lassen (s. Problem bei b1) ). Man könnte aber auch die Knoten A und B als schon benutzt markieren. Der nächste freie Knoten wäre dann C, der seinen Partner in D findet. Beide werden wieder markiert. E muss dann am Schluss noch warten.
Sind alle Spiele beendet, werde die Kanten, die die gemachten Spiele symbolisieren gelöscht.