Sektion Angewandte Informationsverarbeitung
Übungen zu Programmieren II, Sommersemester 1996
Blatt 17, 20 Punkte (5+5+10)
Abgabe: Donnerstag, den 13.06.1996
Ein klassisches Beispiel für das Backtracking stellt die Suche nach
dem Weg durch ein Labyrinth dar.
Aufgabe 21
Realisieren Sie zunächst ein Programm lab, das folgende Aufrufsyntax
akzeptiert :
$ lab infile [ outfile ]
Das Programm lab soll aus der Datei infile ein Labyrinth einlesen und auf
Zulässigkeit überprüfen.
Ist das Labyrinth zulässig, soll es in die Datei outfile oder, falls
kein 2. Argument angegeben wurde, am Bildschirm ausgegeben werden.
Ein Labyrinth ist dabei ein zweidimensionaler Character-Array.
In der Eingabedatei (infile) sind alle Zeichen außer dem Blank als Mauer
aufzufassen.
Ein Labyrinth muß genau einen Eingang auf der linken und genau einen Ausgan
g
auf der rechten Seite besitzen.
Oben und unten muß das Labyrinth abgeschlossen sein.
Ob ein Weg durch das Labyrinth existiert, muß in dieser Aufgabe noch nicht
geprüft werden.
Im Verzeichnis /home/laborix/pfetsch/prog/17 finden Sie die Dateien
lab1,...,lab5 zum Testen Ihres Programms. Stellen Sie diese mit dem
ln-Kommando in Ihrem Verzeichnis zur Verfügung.
Aufgabe 22
Entwickeln Sie ein Nassi-Schneidermann-Diagramm, das einen rekursiven
Algorithmus zur Durchquerung eines Labyrinths beschreibt.
Aufgabe 23
Implementieren Sie Ihren Algorithmus. Markieren Sie dabei (falls vorhanden)
den gefundenen Lösungsweg durch ein spezielles Zeichen im Labyrinth, bevor
Sie es ausgeben.
Hinweise:
Wenn Sie jede Eingabezeile durch das Nullzeichen (0C oder FROM ASCII IMPORT nul)
abschliessen, können Sie die Ausgabe des Labyrinths leicht mit der Funktion
FwriteString aus FtdIO realisieren.
Für Kontrollausgaben kann die Prozedur ShowLab aus dem Modul Labyrinth
verwendet werden. Dazu muß dann aber der Typ Labyrinth aus demselben Modul
benutzt werden. Um die Ausgabe am Bildschirm festzuhalten, kann die Prozedur
Labyrinth.ReadKey verwendet werden.
Falls Sie das Modul Labyrinth verwenden wollen, sollten Sie Ihre
Fehlermeldungen mit der Prozedur Labyrinth.ErrMesg ausgeben. Diese Prozedur
gibt die übergebene Fehlermeldung aus und bricht das Programm ab.
Stellen Sie die benötigten Dateien (im Verzeichnis ..prog/17/test) wieder
mit dem ln-Kommando zur Verfügung.