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.