3.2.3 Das Programm
PROGRAM KoenigsbergerBrueckenproblem;
USES crt;
CONST
ANZAHL = 7;
TYPE
tStadtteile = (Pregel, Nord, Sued, Ost, Insel);
tBrueckenplan = ARRAY [Nord..Insel,Nord..Insel] OF shortint;
tStrecke = RECORD
Weg : ARRAY[1..ANZAHL] OF tStadtteile;{zurückgelegter
Weg}
wievielte : integer; {Wievielte Brücke ?}
END;
VAR
Brueckenplan : tBrueckenplan;
Strecke : tStrecke;
Startpunkt : tStadtteile;
Loesung : boolean; {stellt mögliche Lösung fest}
In der Prozedur InitialisiereBrueckenplan wird die Brückenverteilung
festgeschrieben. Die globale Feldvariable Brückenplan
übergibt das Feld an die Prozedur, welches hier neu beschrieben
wird.
PROCEDURE InitialisiereBrueckenplan
(VAR Bruecken : tBrueckenplan);
BEGIN
Bruecken[Nord, Nord] := 0;
Bruecken[Nord, Sued] := 0;
Bruecken[Nord, Ost] := 1;
Bruecken[Nord, Insel] := 2;
Bruecken[Sued, Nord] := 0;
Bruecken[Sued, Sued] := 0;
Bruecken[Sued, Ost] := 1;
Bruecken[Sued, Insel] := 2;
Bruecken[Ost, Nord] := 1;
Bruecken[Ost, Sued] := 1;
Bruecken[Ost, Ost] := 0;
Bruecken[Ost, Insel] := 1;
Bruecken[Insel, Nord] := 2;
Bruecken[Insel, Sued] := 2;
Bruecken[Insel, Ost] := 1;
Bruecken[Insel, Insel] := 0;
END;
Die Prozeduren SchreibeStadtteil und die Prozedur SchreibeStrecke dienen
der Anzeige der Brückenüberquerungen.
SchreibeStadtteil wird aufgerufen, um den Startpunkt auszugeben. Außerdem
wird die Anzeige von gültigen
Brückenüberquerungen von der Prozedur SchreibeStrecke aufgerufen.
PROCEDURE SchreibeStadtteil
(Stadtteil : tStadtteile);
BEGIN
CASE Stadtteil OF
Nord : write('Nord');
Sued : write('Süd');
Ost : write('Ost');
Insel : write('Insel');
END;
END;
PROCEDURE SchreibeStrecke
(Strecke : tStrecke);
VAR i : integer;
BEGIN
FOR i := 1 TO Strecke.wievielte DO BEGIN
write(' = ');
SchreibeStadtteil(Strecke.Weg[i]);
END;
writeln;
END;
In der Prozedur NaechsterSchritt sind noch zwei Funktionen und zwei
Prozeduren enthalten.
PROCEDURE NaechsterSchritt
(von : tStadtteile);
VAR nach : tStadtteile;
Die Funktion Naechster ermittelt den nächsten Stadtteil. Im Anweisungsteil
der Prozedur NaechsterSchritt findet zunächst die
Initialisierung der Stadtteile statt, indem die Variable nach auf Pregel
gesetzt wird. Das erscheint sinnvoll, weil in der Schleife
jeweils mit der ersten Anweisung nach := Naechster(nach) ein gültiger
Stadtteil ausgewählt wird.
FUNCTION Naechster
(Stadtteil : tStadtteile) : tStadtteile;
BEGIN
Naechster := Succ(Stadtteil);
END;
Die Funktion Moeglich prüft, ob zwischen den Stadtteilen, die durch
von und Stadtteil repräsentiert werden, noch eine
Brückenüberquerung möglich ist.
FUNCTION Moeglich
(von, Stadtteil : tStadtteile) : boolean;
BEGIN
Moeglich := Brueckenplan[von, Stadtteil] > 0;
END;
In der Prozedur NotiereSchritt wird eine Brückenüberquerung
protokolliert. Dazu werden die Werte in der Tabelle um Eins
verringert, die Anzahl der Brückenüberquerung um Eins erhöht
und der letzte Schritt aufgezeichnet: Strecke.Weg
[Strecke.wievielte] := nach. Die möglicherweise aufgetretene Lösung
wird abgefragt, indem geprüft wird, ob am Startpunkt
angekommen wurde und die ANZAHL der Brücken überquert wurde.
PROCEDURE NotiereSchritt
( VAR Bruecke : tBrueckenplan; VAR Strecke : tStrecke);
BEGIN
Bruecke[von,nach] := Bruecke[von,nach] - 1;
Bruecke[nach,von] := Bruecke[nach,von] - 1;
Strecke.wievielte := Strecke.wievielte + 1;
Strecke.Weg[Strecke.wievielte] := nach;
Loesung := (nach = Startpunkt) AND (Strecke.wievielte = ANZAHL);
END;
Wenn ein Schritt zurückgeommen werden muß, dann wird die
Prozedur LoescheSchritt aufgerufen.
PROCEDURE LoescheSchritt
(VAR Bruecke : tBrueckenplan; VAR Strecke : tStrecke);
BEGIN
Bruecke[von,nach] := Bruecke[von,nach] + 1;
Bruecke[nach,von] := Bruecke[nach,von] + 1;
Strecke.wievielte := Strecke.wievielte - 1;
END;
An die Prozedur NaechsterSchritt wird als Parameter der jeweilige Standort
übergeben (von). Im Weiteren wird systematisch
nach noch zur Verfügung stehenden Brücken gesucht. Zunächst
wird ein neuer Stadtteil ausgewählt. Wenn die Wahl des
Zielstadtteiles eine Brückenüberquerung zuläßt,
dann wird der Schritt notiert und geprüft, ob eine Lösung realisiert
wurde. Ist
die Lösung noch nicht erreicht, wird die Prozedur NaechsterSchritt
von diesem Standpunkt aus (rekursiv) aufgerufen. Erweist
sich eineBrückenüberquerung als Sackgasse, wird der letzte
Schritt gelöscht. Der Vorgang terminiert, wenn eine Lösung
erreicht ist oder alle Varianten getestet wurden (Loesung OR (nach
= Insel)).
BEGIN
nach := Pregel;
REPEAT
nach := Naechster(nach);
IF Moeglich(von, nach) THEN BEGIN
NotiereSchritt(Brueckenplan, Strecke);
IF NOT Loesung THEN BEGIN
NaechsterSchritt(nach);
IF NOT Loesung THEN LoescheSchritt(Brueckenplan, Strecke);
END;
END;
UNTIL Loesung
OR (nach = Insel);
END;
Im Hauptprogramm werden die Startpunkte vorbereitet. Nach dem Finden
einer Lösung wird die Strecke ausgegeben.
BEGIN
clrscr;
Startpunkt := Pregel;
REPEAT
InitialisiereBrueckenplan(Brueckenplan);
Startpunkt := Succ(Startpunkt);
Strecke.wievielte := 0;
Loesung := false;
NaechsterSchritt(Startpunkt);
SchreibeStadtteil(Startpunkt);
IF Loesung
THEN SchreibeStrecke(Strecke)
ELSE writeln(' Es gibt keine gültige Strecke.');
writeln;
UNTIL Startpunkt
= Insel;
readln;
END.
|
