5 SET-Programm

5.1 Funktionen des Programms

Wir haben ein Computerprogramm geschrieben, das die Karten eines Set-Spiels mit beliebigen v>=3 und n>=1 verwalten kann. Man kann Karten auswählen, um zu sehen, welche anderen Karten mit diesen Sets bilden würden. Die Hauptfunktion liegt jedoch darin, die größte Anzahl von Karten ohne Set zu finden. Man kann also Karten eingeben, die auf jeden Fall vorhanden sein müssen; des weiteren kann man auch noch Karten ausschließen, die auf keinen Fall in der Lösung vorkommen sollen.

5.2 Realisierung

Das in Free Pascal [8] geschriebene Programm besteht im wesentlichen aus dem Objekt TKarten, das man als Set-Spiel mit beliebigen v>=3 und n>=1 instanziieren kann. Die Karten werden im Boolean-Array Karten, das von 0 bis vn-1 geht (siehe 2.3), gespeichert. Im Word-Array VerbotenVon wird festgehalten, ob eine Karte nicht mehr ausgewählt werden darf und - wenn ja - von wem das Verbot stammt.
Die wichtigsten Methoden sind SchliesseAus und GetMaxOhneSet. Vor jedem Hinzufügen einer Karte wird SchliesseAus aufgerufen. Es werden zwei Parameter übergeben, nämlich die hinzuzufügende Karte hinz und der in VerbotenVon zu speichernden Wert wert. SchliesseAus kombiniert hinz mit v-2 anderen vorhandenen Karten und ermittelt die jeweils setbildende Karte, die, wenn es sie gibt und wenn sie noch nicht verboten wurde, in VerbotenVon mit wert markiert und somit verboten wird. Diese wird ermittelt, indem in den v-1 Karten jede Eigenschaft für sich betrachtet wird und jeweils die Häufigkeit der einzelnen Varianten gezählt wird. Kommt genau eine Variante (v-1)-mal vor, so hat die setbildende Karte auch diese; kom-men alle Varianten bis auf eine genau einmal vor, so hat sie die fehlende Variante. Ansonsten gibt es keine setbildende Karte.
Zum Ermitteln der maximalen Anzahl von Karten ohne Set wird die Funktion GetMaxOhneSet verwendet. Sie probiert hierzu mit Hilfe der rekursiven Funktion TryFrom, die als Parameter eine Karte, ab der gesucht werden soll, erhält, alle Möglichkeiten durch. Mittels einer Schleifenvariable i wird bei alle folgenden Karten geprüft, ob die Karte noch belegt werden darf (ob VerbotenVon[i]=frei ist). Ist dies der Fall, wird diese belegt, TryFrom ruft sich selber wieder mit i+1 als Parameter auf, und danach wird die Karte wieder entfernt. Damit das Entfernen möglichst schnell ist, werden beim Hinzufügen nur alle Karten, die noch nicht ausgeschlossen waren, markiert, und zwar erhält VerbotenVon den Wert, mit dem das jeweilige TryFrom aufgerufen wurde. So müssen beim Entfernen der Karte nicht wieder alle Karten, die davor ein Set bildeten, ermittelt werden, sondern es genügt, einfach wieder die Benutzung aller Karten zu gestatten, die jetzt in VerbotenVon den Wert des TryFrom-Parameters haben.

vorheriges Kapitelnächstes Kapitel


Anregungen, Fragen, Kritik an: Wolf Behrenhoff, Felix Krahmer und Andreas Sorge