Der Einfachheit halber beschreibt diese HTML-Seite das Verfahren mit Zahlen an Stelle von Farben.
1. Begriffe:
Stellen: Anzahl der Elemente einer Kombination
Ziffern: Anzahl der verschiedenen Ziffern (Farben)
leere Antwort: die Antwort besteht weder aus + noch aus -
Dieser Algorithmus bezieht sich auf den Fall, dass der Computer die geheime Kombination erraten soll.
2. Schritte des Algorithmus:
Ideale Anfangskombination:
Aus vielen Versuchsreihen haben wir erkannt, dass folgendes gilt:
Wenn die Anzahl der verschiedenen Ziffern größer oder gleich der Anzahl der verschiedenen Stellen ist, wäre die beste Startkombination alle aufeinanderfolgenden Ziffern. Also bei 4 Stellen und Ziffern 1234.
Wenn es weniger Ziffern als Stellen gibt, kann man so eine Kombination logischerweise nicht formulieren. Für diesen Fall haben die Startkomnbination so gewählt, dass beim Erreichen der Zifferngrenze von vorne gezählt wird. Bei 6 Stellen und 4 Ziffern also 123412.
Zu Beginn der Suche wird eine Listendatei, die alle möglichen Kombinationen in richtiger Reihenfolge (z. B.: 111,112,113,121,122 usw.) enthält, angelegt.
Der eigentliche Suchalgorithmus besteht aus folgenden Teilen:
1. Antwortstring einlesen
2. Aus der Liste werden nun von vorne die Kombinationen ausgelesen und es wird geprüft ob beim Vergleich mit den Startstring die selbe Antwort entstehen würde.
3. Ist dies der Fall, wird diese Kombination als zweiter Versuch angeboten.
4. Der zweite Antwortstring wird eingelesen.
5. Nun wird in der Liste "weitergelesen" (also von der letzten Kombination an), bis der Computer eine Kombination findet, die beim Vergleich mit der Startkombination auch die entsprechende Antwort und bei Vergleich mit der zweiten Kombination die entsprechende Antwort liefert.
6. Dieser Algorithmus wird nun so fortgeführt, dass immer alle vorhergehenden Versuche mit in die Suche einbezogen werden.
7. Die Suche erfolgt so lange bis die Geheimkomnbination erraten wurde oder der Computer am Listenende angelangt ist ohne eine passende Kombination zu finden.
8. Im letztgenannten Fall, gibt der Computer eine Fehlermeldung aus, da offensichtlich eine Antworteingabe des Benutzer nicht korrekt war.
Beispiel:
Gegeben ist eine Liste mit allen möglichen Kombinationen der Ziffern zwischen 1 und 3 mit 3 Stellen Länge.
Weiterhin gegeben ist der Verständlichkeit halber die gesuchte Kombination "311".
1. Das Programm testet die Kombination "123" und erhält vom Benutzer den Hinweis "--".
2. Das Programm durchläuft die Liste bis zu der Kombination "211".
(Das ist die erste Kombination,auf die "--" zutrifft)
3. Das Programm gibt die Kombination aus und erwartet eine Eingabe des Benutzers. Dieser gibt den Hinweis "++" zurück.
4. Das das Programm durchläuft die Liste von der letzten Stelle an und prüft jetzt 2 Bedingungen. Die Zahlen werden also durch den ersten Hinweis vorgefiltert und durch den zweiten weiterführend gefiltert. Die nächste Stelle, an der beide Bedingungen zutreffen, ist "311"
5. Das Programm gibt die Kombination aus und erwartet einen erneuten Hinweis vom Benutzer,der mit "+++" antwortet.
3. Sonderfälle:
Manchmal ist es taktisch günstiger nicht nach den Algorithmus zu gehen, sondern einer anderen Kombination den Vorrang zu geben. Zum Verständnis hier ein Beispiel:
Es gibt 6 verschiedene Stellen und Ziffern. Die gesuchte Kombination heißt 666666.
Der Algorithmus beginnt normal mit 123456. Die Antwort daruaf lautet +
Wenn es nun nach den Algorithmus weiter gehen müsste, würde der Computer die Kombinationen 111111, 222222, 333333, 444444, 555555 (jeweils mit leeren Antwort) und 666666 prüfen. Mit den ersten Versuch sind es also 7 Versuche. Wenn man als zweiter Versuch 122333 nehmen würde könnte man sofort feststellen, ob 111111, 222222 oder 333333 die gesuchte Kombination ist. Ist den Antwort leer, prüft der Computer die Kombination 455666. Dann wüsste er sofort welche Kombination richtig ist. Hier noch einmal die Zusammenfassung des Dialogs:
123456 +
122333
455666 +++
666666
Mit dieser Methode benötigt der Computer gerade mal 4 Versuche. Es war nur ein Beispiel
für einen Sonderfall es gibt zahlreiche weiterer solcher Fälle, die wir mit berücksichtig haben.
Hier folgt nun ein Auszug des Quelltextes in dem die ersten Schritte des Algorithmus kommentiert (Kommentare in geschweiften Klammern)
dargestellt werden.
BEGIN
DrawGameScreen(false); {Zeichnet Spielbildschirm}
init(false); {Initialisiert Ziffern- und Stellenzahl}
gotoxy(28,20);
write('Wählen sie ihre');
gotoxy(28,21);
write('Geheimkombination!');
Choiceboard(Digits,zi,49,4); {Choiceboard wird zum Aussuchen einer Kombination erstellt}
HideText;
erzeuge(Digits,zi); {Listendatei erzeugen}
FOR i:=0 TO Digits-1 DO x1[i]:=(i MOD zi)+1; {1. Versuch, z.B. 1234 generieren}
reset(f); {Listendatei öffnen}
gotoXY(4,4); write('V1: ');
FOR i:=0 TO Digits-1 DO WriteColor(x1[i]); {Versuch hinschreiben}
gotoXY(4,5); write('E1: ');
readln(ant[0]); {Antwort einlesen}
IF ant[0]=richtig THEN {Wenn Antwort richtig zeige Textmeldung}
BEGIN
ShowText(3);
exit;
END;
IF (zi>=3) AND (Digits=3) AND (ant[0]='+') THEN {Definition eines Sonderfalls}
BEGIN
x2[0]:=1;
x2[1]:=2;
x2[2]:=2;
gotoXY(4,6); write('V2: '); WriteColor(122);
GOTO zwei; {Sprung bei Sonderfall}
END;
.
.
.
REPEAT
BEGIN
read(f,z2); {Zahl aus Listendatei lesen}
split(1,z2); {Zahl in einzelne Ziffern zerlegen}
END;
UNTIL (test(x1,xt)=ant[0]) OR (eof(f)); {liest so lange Zahlen ein bis die Antwort des Benutzers übereinstimmen würde oder die Listendatei zu Ende ist}
IF (eof(f) AND (test(x1,xt)<>ant[0])) OR (z2=0) THEN {2.Bedingung notwendig,da z.B. 4444 bei 4 Ziffern noch richtig sein kann, 3. Bedingung, weil er manchmal Null einliest}
BEGIN
Showtext(4);{Wenn Listendatei zu Ende und keine gültige Zahl gefunden, schreibe Meldung: "Eingabefehler des Benutzers}
exit;
END;
FOR i:=0 TO Digits-1 DO x2[i]:=xt[i]; {gefunden Testzahl wird im neuen Array gespeichert,da sie bei der nächsten Suche überschrieben wird}
gotoXY(4,6); write('V2: '); WriteColor(z2);
zwei: {Sprungstelle für Sonderfall}
gotoXY(4,7); write('E2: ');
readln(ant[1]); {Einlesen der zweiten Antwort}
IF ant[1]=richtig THEN
BEGIN
Showtext(3);
exit;
END;
.
.
.