|
Bei dieser Anwendung der Rekursion macht man sich die Eigenschaft des Pascalcompilers zunutze, daß lokale Variablen bei jedem Selbstaufruf neu angelegt werden, die Werte der vorigen Rekursionsebenen aber noch im Speicher vorhanden sind. So ist es möglich, Lösungen nach dem "Trial and Error" - Prinzip zu suchen. Dabei wird immer die selbe Vorgangsweise verwendet: Von einer gegebenen Ausgangsstellung aus wird nach gewissen Regeln ein Lösungsversuch gemacht, der in einer Variablen notiert wird. Dann kommt es zum Selbstaufruf, und ein Lösungsversuch wird gesucht. Ist die Aufgabenstellung bereits erfüllt, wird der Lösungsweg gespeichert und der Suchvorgang abgebrochen, oder es wird weitergesucht, bis alle Versuche erschöpft sind. Wird kein gültiger Versuch mehr gefunden, ist das Unterprogramm in einer Sackgasse gelandet und wird beendet. Das aufrufende Unterprogramm löscht den Versuch aus der Variablen und sucht eine neue Versuchsmöglichkeit, wobei nie zweimal derselbe Versuch unternommen wird. Das Backtracking endet entweder nach dem Finden der ersten Lösung oder aber nachdem alle möglichen Versuche unternommen worden sind.
Auch hier gibt es vielfältige Anwendungsbeispiele. Die bekannteste Variante dient zum Finden eines oder aller Wege aus einem Labyrinth.
3.2.1 Finden eines Weges aus einem Labyrinth
Um den Ausweg aus einem Labyrinth mit dem Computer suchen zu können, muß dieses zuerst in einer geeigneten Form gespeichert werden. Dies ist am besten mit einem zweidimensionalen Zahlenfeld, einem Array of Byte, zu bewerkstelligen. Somit steht für jeden Ort des Labyrinths eine Zahl zur Verfügung, mit deren Hilfe man speichern kann, ob ein Feld zugänglich ist oder nicht und ob es schon betreten wurde. Letzteres ist sehr wichtig, um ein Im-Kreis-Gehen oder gar ein Zurückgehen zu vermeiden, denn dadurch könnte die Lösung nie gefunden werden und die Rekursion liefe endlos, bis es zu einem Stack-Overflow käme. Damit das nicht passiert, kontrolliert das Unterprogramm, ob das Betreten eines Feldes, das an den momentanen Standpunkt grenzt, möglich ist. Im Array wird dieser Versuch gespeichert, und die Prozedur ruft sich selbst mit den neuen Koordinaten des eben betretenen Feldes auf. Dort beginnt der Prozeß von neuem. Landet das Programm dabei in einer Sackgasse, kommt es also zu einem Feld, bei dem es keine Möglichkeit eines weiterführenden Schrittes gibt, geht es um ein Feld zurück und überprüft dieses auf weitere Versuchsmöglichkeiten. Werden sie gefunden, geht ihnen der Algorithmus nach, andernfalls geht er um ein weiteres Feld zurück.
Man kann entweder nur den erstbesten Weg suchen und dann die Suche abbrechen wie im folgenden Programm, oder man speichert diesen gefundenen Weg und sucht so lange, bis alle Versuchsmöglichkeiten erschöpft sind. Ersteres wurde im folgenden Beispielprogramm realisiert. Um den Suchvorgang zu veranschaulichen, leuchten die Felder, die gerade auf ihre Betretbarkeit überprüft werden, andersfärbig auf. Gelb bedeutet, daß das Feld betretbar ist, braune Felder sind verbaut, dunkelrote wurden bereits besucht.. Der Weg, der während der Suche hellrot leuchtet, wird bei Erreichen eines Ausgangs hellgrün. Weiters sind Verzögerungen in den Algorithmus eingebaut, um die Suche überhaupt nachvollziehen zu können. Das folgende Programm sucht den erstbesten Weg aus dem Labyrinth.
program labyrinth;
uses crt, tools07;
type feld = array[1..20,1..20] of byte;
const labnorm : feld = ((2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,3,2,2,2,2), {1}
(2,2,2,2,2,0,0,2,2,2,2,2,2,0,0,0,2,2,2,2),
(2,2,2,2,2,0,2,2,2,2,2,2,2,2,0,2,2,2,2,2),
(2,2,0,0,0,0,2,0,0,0,0,0,0,2,0,2,2,0,2,2),
(2,2,2,2,2,0,2,0,2,2,2,2,0,0,0,0,2,0,2,2),
(2,2,2,2,2,0,0,0,2,0,2,2,0,2,2,0,2,0,2,2),
(2,2,2,2,2,0,2,2,2,0,2,2,0,2,2,0,2,0,2,2),
(2,2,2,2,2,0,2,2,2,0,2,2,0,2,2,0,2,0,2,2),
(2,2,2,2,2,0,2,2,2,0,0,0,0,0,0,0,2,0,0,3),
(3,0,0,0,0,0,2,2,2,0,2,2,2,0,2,2,2,0,2,2),
(2,2,2,2,2,2,2,2,2,2,2,2,2,0,2,2,2,0,2,2),
(2,2,2,2,2,2,2,0,0,0,0,0,0,0,0,0,2,0,2,2),
(2,2,0,0,0,0,2,0,2,2,2,0,2,2,2,0,2,0,2,2),
(2,2,0,2,2,0,2,0,2,2,0,0,0,0,0,0,0,0,2,2),
(2,2,0,2,2,0,0,0,2,2,0,2,2,2,2,2,0,2,2,2),
(2,2,2,2,2,2,2,2,2,2,0,2,2,2,2,2,0,2,2,2),
(2,2,2,2,2,2,2,2,0,0,0,2,2,2,2,2,0,2,2,2),
(2,2,2,2,0,0,0,0,0,2,0,0,0,0,2,0,0,2,2,2),
(2,2,2,2,2,2,0,2,2,2,2,2,0,2,2,2,2,2,2,2),
(2,2,2,2,2,2,2,2,2,2,2,2,3,2,2,2,2,2,2,2));
gefunden : boolean = false; {2}
var lab : feld;
procedure zeigelab; {3}
var i, j : integer;
begin
clrscr;
for j:= 1 to 20 do begin
for i:= 1 to 20 do begin
if (i=10) and (j=10) then begin
textcolor(9);
write('ST');
end else case lab[i,j] of
0: write(\' \');
1: begin
if gefunden then textcolor(10) else textcolor(12);
write(#219,#219);
end;
2: begin
textcolor(7);
write(#219,#219);
end;
3: begin
textcolor(10);
write(\'AU\');
end;
end;
end;
writeln;
end;
end;
procedure suchweg(x,y:integer); {4}
var a,b : integer;
begin
gotoxy(x*2-1,y); {5}
textcolor(14);
write(#219,#219);
delay(333);
if not gefunden then begin
case lab[x,y] of {6}
3: begin {7}
gefunden:=true;
zeigelab;
end;
2:begin {8}
gotoxy(x*2-1,y);
textcolor(6);
write(#219,#219);;
end;
1:begin {9}
gotoxy(x*2-1,y);
textcolor(4);
write(#219,#219);;
end;
0: begin {10}
lab[x,y]:=1; {11}
zeigelab; {12}
if not gefunden then suchweg(x-1,y); {13}
if not gefunden then suchweg(x+1,y);
if not gefunden then suchweg(x,y+1);
if not gefunden then suchweg(x,y-1);
if not gefunden then begin
zeigelab;
delay(333);
end;
lab[x,y]:=0; {14}
end;
end;
end;
end;
begin
clrscr;
writeln(\' Programm zum Suchen eines Ausweges aus einem Labyrith\');
window(20,3,70,25);
lab:=labnorm;
zeigelab;
writeln(\'Bitte Taste drücken, um einen Ausweg zu zeigen...\');
wt;
clrscr;
suchweg(10,10);
wt;
window(1,1,80,25);
clrscr;
end.
Zuerst wird das Labyrinth als Konstante definiert {1}. Die Variable gefunden ist ein Flag {2}. Ihr wird der Wert True zugewiesen, wenn bereits ein Ausweg gefunden wurde, anderenfalls hat sie den Wert False. Damit kann auf das Finden des Weges an anderen Stellen des Programmes entsprechend reagiert werden. Die Prozedur zeigelab {3} dient lediglich zum Anzeigen des Labyrinths und des bisher gegangenen Weges. Die rekursive Prozedur suchweg {4} ist für das Finden des Ausweges verantwortlich. Ihr werden die Koordinaten (x und y) des als nächstes zu überprüfenden Feldes als Parameter übergeben. Das Unterprogramm markiert dieses Feld zunächst gelb {5}. Nur wenn noch kein Ausweg gefunden wurde, wird das Feld getestet {6}. Ist das aktuelle Feld ein Ausgang, wird der Flag gefunden auf True gesetzt und es erfolgt kein Selbstaufruf {7}. Befindet sich aber eine Mauer darauf oder {8} oder wurde es bereits betreten {9}, wird es in der entsprechenden Farbe dargestellt. Da dieser Versuch nicht erfolgversprechend ist, werden von diesem Feld keine weiteren Schritte gemacht. Anders liegt der Fall, wenn das aktuelle Feld betretbar ist {10}: Das Feld wird als betreten markiert {11}, die veränderte Position auf dem Bildschirm sichtbar gemacht, und von dort ausgehend werden, wenn noch immer kein Ausweg gefunden wurde, alle vier angrenzenden Felder getestet, das heißt, die Prozedur ruft sich selbst mit den entsprechend veränderten Koordinaten auf {13}. Sind alle Versuche beendet, wird das Feld wieder als unbetreten markiert {14}, und die Prozedur endet.
Die Beschreibung des Rekursionsablaufes ist bei diesem Programm äußerst langwierig und kann wesentlich besser durch das obige Programm veranschaulicht werden.
Die zweite Variante dieses Programms sucht alle Auswege aus dem Labyrinth und findet zusätzlich den kürzesten heraus. Diesmal ist kein Flag notwendig, da alle möglichen Felder durchsucht werden müssen. Zusätzlich wird ein Zähler für die Anzahl der unternommenen Schritte eingeführt, und ein Array vom Typ feld wird global deklariert. Immer, wenn ein Ausweg gefunden wurde, wird er in diesem Array gespeichert, und die notwendige Schrittanzahl wird mit der niedrigsten bisherigen verglichen, und gegebenenfalls wird die aktuelle Schrittzahl zum neuen Minimum. Sowohl auf eine Darstellung als auch auf eine Verzögerung des Suchvorganges wurde bei dieser Version aus Gründen der Laufzeit verzichtet.
Nach der sehr schnell beendeten Suche werden nacheinander die gefundenen Auswege angezeigt, wobei der kürzeste gekennzeichnet ist. Da diese Variante der obigen ziemlich ähnlich ist, ist ihr Quellcode nur im Anhang (A4, "labyrinth_alle") abgedruckt.
3.3.2 Suche nach möglichst kurzen Strecken zwischen mehreren Punkten
Eine andere Einsatzmöglichkeit des Backtrackings ist das Suchen nach Verbindungen zweier Orte in einem Ortsnetz. Auch hier kann entweder nur die erstbeste Verbindung oder alle Wege zwischen den beiden Orten gesucht werden. Das Schema des Programmes ist dem vorigen sehr ähnlich: Es werden schrittweise alle Reisemöglichkeiten durchprobiert, bis entweder ein Weg gefunden wurde oder aber alle Möglichkeiten erschöpft sind. Zur Speicherung der Länge der Straßen zwischen zwei Orten dient abermals ein zweidimensionales Array. Ist die Länge Null, so ist keine direkte Straßenverbindung vorhanden.
Eine rekursive Prozedur speichert in einem String den bisher gegangenen Weg, überprüft, ob der Zielort bereits erreicht wurde und geht zu jedem vom aktuellen Ort aus erreichbaren und noch nicht besuchten Ort weiter. Dies geschieht mit einem Selbstaufruf, sodaß der Prozeß von neuem beginnt. Wichtig ist wieder, daß kein Ort zweimal besucht wird, da das Programm sonst im Kreis herum ginge, der Algorithmus nicht abbräche und das Programm auf Grund eines Stack-Overflows abstürzte. Folgendes Programm sucht alle möglichen Wege, zeigt sie an und ermittelt den kürzesten:
program weg;
uses crt, tools07;
const ortanz = 7;
type Tortnetz = array[1..ortanz,1..ortanz] of integer;
const ortnetz : Tortnetz = ( ( 0, 43, 0,12, 0, 54, 0), {1}
( 43, 0,34, 3, 0, 23,32),
( 0, 34, 0, 0, 34, 0, 0),
( 12, 3, 0, 0,92, 11, 0),
( 0, 0,34,92, 0, 12, 0),
( 54,23, 0,11,12, 0, 0),
( 0, 32, 0, 0, 0, 0, 0));
gefunden : integer = 0;
var k : integer;
min, lang : integer;
start, ziel : integer;
weg, kweg : string;
procedure zeigeortsnetz; {2}
var i, j :integer;
begin
writeln(\' Ortsabstände ( --- .......keine Straße vorhanden)\');
write(\' \');
for j:=1 to ortanz do write(\' \',i,\' \');
writeln;
for i:=1 to ortanz do begin
write(\' \',i,\' \');
for j:=1 to ortanz do if ortnetz[i,j]=0 then write(\' --- \')
else write(\' \',ortnetz[i,j]:3,\' \');
writeln;
end;
writeln;
end;
procedure gehezu(ort:integer); {3}
var k : integer;
begin
weg:=weg+chr(48+ort); {4}
if ort=ziel then begin {5}
writeln(weg); {6}
inc(gefunden); {7}
if gefunden mod 10 = 0 then begin
writeln;
write(\'Weiter mit irgendeiner Taste...\');
wt;
clrscr;
end;
if (lang0) and (pos(chr(48+k),weg)=0) then begin {10}
lang:=lang+ortnetz[ort,k]; {????} {11}
gehezu(k); {12}
lang:=lang-ortnetz[ort,k]; {13}
end;
end;
weg:=copy(weg,1,length(weg)-1); {14}
end;
begin
lang:=0;
min:=0;
weg:=\'\';
color(7,0);
clrscr;
writeln(\' PROGRAMM ZUM REKURSIVEN SUCHEN DES\');
writeln(\' KÜRZESTEN WEGES ZWISCHEN ZWEI ORTEN IN EINEM ORTSNETZ\');
writeln;
writeln(\' programmiert von Stefan Krywult im Zuge seiner Informatikfachbereichsarbeit\');
writeln;
zeigeortsnetz;
writeln;
write(\' Bitte Startort eingeben: \');
readln(start);
write(\' Bitte Zielort eingeben: \');
readln(ziel);
writeln;
write(\'Suche begint bei Tastendruck...\');
wt;
clrscr;
zeigeortsnetz;
window(1,12,80,25);
gehezu(start);
if gefunden > 0 then writeln(\'Kürzeste von \',gefunden,\' Wegen ist \',kweg,\' mit \',min,\' Wegeinheiten.\')
else writeln(\'Es gibt keinen Weg von Ort \',start,\' nach Ort \',ziel,\'.\');
writeln;
writeln(\'Programmende bei Tastendruck...\');
wt;
color(7,0);
clrscr;
end.
Die Längen der Verbindungswege werden als Konstanten in einem zweidimensionalen Feld gespeichert {1}. Die Orte selbst sind durch die Zahlen Eins bis Sieben definiert. Die Prozedur zeigeortsnetz {2} dient zur tabellierten Anzeige dieser Daten. Das Unterprogramm gehezu {3}sucht rekursiv alle möglichen von dem in der Variablen start gespeicherten Ausgangsort ausgehende Wege durch, und gibt diejenigen am Bildschirm aus, die zum in ziel gespeicherten Zielort führen. Als Parameter wird die Nummer des als nächstes zu begehenden Ortes übergeben. Beim ersten Aufruf vom Hauptprogramm aus ist dies der Startort.
Zunächst wird die Nummer des Ortes dem String weg hinzugefügt {4}, worin der bisher zurückgelegte Weg gespeichert ist. Wenn der aktuelle Ort bereits der Zielort ist {5}, wird der bisherige Weg am Bildschirm ausgegeben {6} und die Anzahl der gefundenen Wege um eins erhöht {7}. Außerdem wird die aktuelle Weglänge mit der bisher kürzesten verglichen und das Minimum gegebenenfals neu gesetzt {8}.
Ist der Zielort jedoch noch nicht erreicht, wird systematisch versucht, alle anderen Orte von der momentanen Position aus zu erreichen{9}. Das ist aber nur dann möglich bzw. sinnvoll, wenn es eine Straße dorthin gibt (der Abstand größer als Null ist) und der Ort noch nicht zuvor betreten wurde (im String gespeichert ist) {10}. Kann der Ort betreten werden, wird die Länge der Verbindung des neuen und des momentanen Ortes zur Gesamtlänge des Weges addiert {11} und das Unterprogramm gehezu mit dem neuen Ort als Parameter aufgerufen {12}. Hier beginnt der Vorgang von neuem.
Falls der Algorithmus keine Orte mehr findet, die er vom aktuellen Standpunkt aus erreichen könnte, geht er schrittweise den Weg zurück, um andere Möglichkeiten auszuprobieren. Deswegen muß die Länge des letzten Wegstückes nach dem Ausprobieren wieder vom Gesamtweg subtrahiert werden {13}. Am Ende der Prozedur wird die letzte Wegnummer aus dem String weg wieder entfernt, um ihn wieder zugänglich zu machen {14}.
3.2.3 Das Acht-Damen-Problem
Auch das Acht-Damen-Problem läßt sich mit einem relativ einfachen rekursiven Programm lösen. Dabei müssen auf einem Schachbrett acht Damen so aufgestellt werden, daß sie einander nicht schlagen können (bei mehr als acht Damen ist dies nicht mehr möglich).
Zur Speicherung eines Schachbretts im Computer bietet sich wieder ein zweidimensionales Feld an, in dem festgehalten wird, ob ein Feld frei, von einer Dame bedroht oder besetzt ist. Um den Algorithmus schneller zu machen, wird davon ausgegangen, daß in jeder Zeile des Schachbrettes nur eine einzige Dame stehen kann. Andernfalls könnten zwei Damen einander schlagen. Mittels Backtracking wird versucht, schrittweise auf jedes freie und unbedrohte Feld eine Dame zu stellen, bis es entweder nur mehr bedrohte und besetzte Felder gibt oder aber bereits 8 Damen aufgestellt worden sind. Wenn noch Damen aufzustellen sind und dies noch möglich ist, wird die neue Dame positioniert, und auf dem Spielfeld werden die betroffenen Felder markiert, anschließend erfolgt ein Selbstaufruf, bei dem das Spielbrett mit der neuen Situation übergeben wird.
Auf jedes unbedrohte freie Feld kann eine neue Dame gesetzt werden, da eine unbedrohte Dame sicher keine andere, bereits vorhandene Dame schlagen kann.
Nun folgt der Quellcode des Programmes, das nur eine Lösung des Acht-Damen-Problems sucht, wobei der Status der Suche auf Wunsch ständig angezeigt werden kann:
program acht_damen;
uses crt, tools07;
type Tbrett=array[1..8,1..8] of byte; {1}
var start : Tbrett; {2}
i,ii,verz : integer;
danz, lanz : integer;
gefunden : boolean;
procedure zeigbrett(br:Tbrett); {3}
var j,k:integer;
begin
writeln(\' 1 2 3 4 5 6 7 8\');
for j:=1 to 8 do begin
for k:=0 to 8 do
if k=0 then write(j,\' \') else begin
case br[k,j] of
0: begin textcolor(15); write(\'O \'); end;
1: begin textcolor(12); write(\'X \'); end;
2: begin textcolor(14); write(\'D \'); end;
end;
end;
textcolor(7);
writeln;
end;
writeln;
writeln(\'O = frei, X = durch Dame bedroht, D = durch Dame besetzt \');
writeln(danz,\' Damen sind gesetzt.\');
end;
procedure stell_dame(brett:Tbrett); {4}
var ax,ay,b : integer;
test : tbrett; {5}
begin
if (verz >0) and not gefunden then begin {6}
gotoxy(1,1);
zeigbrett(brett);
delay(verz);
end;
if (danz=8) and not gefunden then begin {7}
clrscr;
zeigbrett(brett);
gefunden:=true;
writeln(#7);
wt;
end
else if not gefunden then begin {8}
for ax:=1 to 8 do begin
ay:=danz+1; {9}
if brett[ax,ay]=0 then begin {10}
test:=brett; {11}
test[ax,ay]:=2; {12}
inc(danz); {13}
for b:=1 to 8 do begin {14}
if test[ax,b]=0 then test[ax,b]:=1;
if test[b,ay]=0 then test[b,ay]:=1;
if (ax-b) > 0 then begin
if ((ay-b) > 0) and (test[ax-b,ay-b]=0) then test[ax-b,ay-b]:=1;
if ((ay+b) < 9) and (test[ax-b,ay+b]=0) then test[ax-b,ay+b]:=1;
end;
if (ax+b) < 9 then begin
if ((ay-b) > 0) and (test[ax+b,ay-b]=0) then test[ax+b,ay-b]:=1;
if ((ay+b) < 9) and (test[ax+b,ay+b]=0) then test[ax+b,ay+b]:=1;
end;
end;
stell_dame(test); {15}
dec(danz); {16}
end; {if brett...}
end; {for ax}
end; {else begin}
end; {procedure stell_dame}
begin
clrscr;
writeln(\' 8 DAMEN AUF EINEM SCHACHBRETT\');
writeln(\' ein Programm von Stefan Krywult für seine Informatikfachbereichsarbeit\');
window(2,4,78,24);
gefunden:=false;
write(\'Verzögerung (z.B.:2/20; 0=keine Darstellung): \'); {17}
readln(verz);
clrscr;
writeln(\'Suche läuft...\');
for i:=1 to 8 do for ii:=1 to 8 do start[i,ii]:=0; {18}
stell_dame(start); {19}
window(1,1,80,25);
clrscr;
end.
Mit der Type-Anweisung {1} wird der Datentyp TBrett als Array[1..8, 1..8] of byte also als zweidimensionales Zahlenfeld definiert. In Variablen dieses Datentyps soll das Schachbrett gespeichert werden. Es ist nicht notwendig, einen eigenen Datentyp dafür zu definieren, da anstelle von TBrett auch Array[1..8,1..8] of byte geschrieben werden könnte, was aber wesentlich unübersichtlicher wäre. Die global deklarierte Variable start ist vom Typ TBrett {2}. Die Prozedur zeigebrett {3} dient zur Anzeige des momentanen Suchfortschrittes und der Lösungen. Das rekursive Unterprogramm stell_dame {4} sucht die Lösung des 8-Damen-Problems. Als Parameter wird eine Variable vom Typ TBrett übergeben, in der die momentane Aufstellung gespeichert ist. Neben einigen anderen Hilfsvariablen wird auch das Feld test deklariert {5}. Wichtig ist, daß Laufvariablen für Schleifen immer lokal deklariert werden, da sie nur von einer einzigen Rekursionsstufe aus zugänglich sein dürfen.
Wenn noch keine Lösung gefunden wurde, erfolgt, falls gewünscht, eine Darstellung des Suchfortschrittes {6}. Beim eigentlichen Suchvorgang wird dann zunächst überprüft, ob nicht schon acht Damen auf dem Schachbrett untergebracht sind. Wenn dies der Fall ist, wurde bereits eine Lösung gefunden, und sie wird mit Hilfe der Prozedur zeigebrett angezeigt {7}, dann wird das Flag gefunden gesetzt, wodurch die Suche abgebrochen wird. Anderenfalls {8} wird die nächste Zeile, in der noch keine Dame steht, durchlaufen und nach freien Feldern durchsucht {9}. Wurde eines entdeckt {10}, wird zuerst das übergebene Feld in die Hilfsvariable hilf kopiert {11}. In diese wird die gefundene freie Stelle als von einer Dame besetzt markiert {12}. Nachdem die Anzahl der Damen erhöht wurde {13}, werden im Array hilf auch alle von der neu aufgestellten Dame bedrohten Felder markiert {14}. Dann erfolgt ein Selbstaufruf, wobei als Parameter die Variable hilf, also das alte Feld mit der zusätzlichen Dame und der von ihr bedrohten Felder, übergeben wird {15}.
Danach wird die Anzahl der Damen wieder um eins reduziert {16}. Die Dame muß nicht wieder vom Spielfeld entfernt werden, was sehr aufwendig wäre, da die Aufstellung vor dem Hinzufügen der Dame in der Variable brett noch vorhanden ist. Dies ist der Grund für die Einführung der lokalen Hilfsvariablen hilf. Dann werden die anderen Felder der Zeile nach dem gleichen Schema durchprobiert.
Die Rekursion endet, sobald eine Lösung des Problems gefunden wurde. Jeder Versuch endet, sobald keine weitere Dame mehr aufgestellt werden kann oder sobald acht Damen auf dem Brett stehen. Vor dem Aufruf des rekursiven Suchalgorithmus {19} im Hauptprogramm müssen zuerst die gewünschte Verzögerung der Suchdarstellung in verz eingegeben {17} und die Elemente des Felds start, das beim ersten Aufruf des Unterprogrammes stell_dame übergeben wird, durch Zuweisen des Wertes Null initialisiert werden, da das Brett zu Beginn ja noch leer ist {18}.
3.3.4 Rekursives Durchsuchen des Verzeichnisbaumes nach Dateien
Eine etwas andere Art des Backtracking wird in der Praxis oft für das Suchen von Dateien in einem Verzeichnisbaum eingesetzt: Einer rekursive Prozedur wird ein Verzeichnis als Parameter übergeben. Sie durchsucht dieses zuerst nach dem eingegebenen Dateinamen und gibt gegebenenfalls passende aus. Anschließend wird das Verzeichnis nach Unterverzeichnissen durchsucht. Wird eines gefunden, ruft sich die Prozedur selbst auf, wobei sie als Parameter dessen Pfad übergibt. Danach wird mit dem Unterverzeichnis genauso verfahren wie mit dem Überverzeichnis. Der Suchvorgang bricht ab, sobald alle Unterverzeichnisse des vom Startverzeichnis ausgehenden Verzeichnisbaumes durchsucht worden sind.
Folgendes Programm verfährt nach dem oben beschriebenen Prinzip. Wegen der Übersichtlichkeit wurde der Arbeitsgang auf drei Prozeduren aufgeteilt:
program rekfsuch;
uses crt,dos,tools07;
const abbruch : boolean = false; {1}
var anz : integer;
s : string;
ch : char;
suchstring : string;
suchpfad : string;
procedure ausgabe(erg : string; a:byte); {2}
begin
inc(anz);
if odd(anz) then textcolor(7) else textcolor(3);
write(anz,\': \',erg);
gotoxy(60,wherey);
if (a and $01)=$01 then write(\'RO \') else write(\' \');
if (a and $02)=$02 then write(\'H \') else write(\' \');
if (a and $04)=$04 then write(\'S \') else write(\' \');
if (a and $10)=$10 then write(\'D \') else write(\' \');
if (a and $20)=$20 then write(\'A\') else write(\' \');
writeln;
textcolor(7);
if anz mod 15 = 0 then begin
writeln;
writeln(\'RO=Read Only, H=Hidden, S=System, D=Direktory, A=Archiv\');
write(\'Weiter mit Taste (Ende=[Esc]) ...\');
repeat until keypressed;
ch:=readkey;
if ch=#27 then abbruch:=true;
if not abbruch then clrscr else gotoxy(1,wherey-2);
end;
end;
procedure suchdateien(verzeichnis:string); {3}
var files : SearchRec; {4}
begin
if not abbruch then begin
FindFirst(verzeichnis+suchstring,anyfile,files); {5}
while (doserror=0) and not abbruch do begin {6}
if ((files.attr and VolumeID)VolumeID)
then ausgabe(verzeichnis+files.name, files.attr); {7}
if keypressed then begin {8}
ch:=readkey;
if ch=#27 then abbruch:=true;
end;
findnext(files); {9}
end;
end;
end;
procedure such(verzeichnis:string); {10}
var dirs : SearchRec; {11}
begin
if not abbruch then begin {12}
suchdateien(verzeichnis); {13}
FindFirst(verzeichnis+\'*.*\',directory,dirs); {14}
while (doserror=0) and not abbruch do begin {15}
if (dirs.attr and directory=directory) {16}
and (dirs.name \'.\')
and (dirs.name \'..\')
then such(verzeichnis+dirs.name+\'\\\');
if keypressed then begin {17}
ch:=readkey;
if ch=#27 then abbruch:=true;
end;
findnext(dirs); {18}
end;
end;
end;
begin
color(15,1);
anz:=0;
clrscr;
writeln(\' REKURSIVES DATEISUCHPROGRAMM\');
writeln(\' geschrieben von Stefan Krywult für seine Fachbereichsarbeit 1998\');
window(3,4,78,24);
color(7,0);
clrscr;
window(5,5,76,23);
write(\'Suchpfad: \');
readln(suchpfad);
write(\'Zu suchende Datei oder zu suchendes Verzeichnis: \');
readln(suchstring);
writeln;
writeln(\'Suche beginnt bei Tastendruck.\');
writeln(\'Ein Abbruch ist jeder Zeit mit [Esc] möglich.\');
wt;
clrscr;
such(suchpfad); {19}
writeln;
writeln(\'RO=Read Only, H=Hidden, S=System, D=Direktory, A=Archiv\');
If not abbruch then writeln(\'In \',suchpfad,\' wurde \',suchstring,\' \',anz,\'mal gefunden.\')
else writeln(\'In \',suchpfad,\' wurde \',suchstring,\' bis zum Abbruch \',anz,\'mal gefunden.\');
write(\'Programm endet bei Tastendruck...\');
wt;
window(1,1,80,25);
color(7,0);
clrscr;
end.
Die typisierte Konstante abbruch ist ein Variable vom Typ Boolean, die zu Beginn des Programmes den Wert False besitzt und als Flag verwendet wird {1}. Ist es gesetzt, wird die Suche abgebrochen. Die Prozedur ausgabe gibt den in erg übergebenen Datei- oder Verzeichnisnamen mit Pfad und Attributen formatiert am Bildschirm aus {2}. Das Unterprogramm suchdateien {3} durchsucht das in der Variablen verzeichnis übergebene Unterverzeichnis nach der zuvor eingegebenen Datei und gibt sie gegebenenfalls mit Hilfe der Prozedur ausgabe aus. Als lokale Variable wird files als SearchRec deklariert. Dieser Variablentyp enthält mehrere Datenfelder und ist für den Aufruf der Pascalprozeduren FindFirst und FindNext notwendig {4}. Ein Feld dieses Typs enthält den Dateinamen, andere die Dateiattribute, die Dateigröße sowie interne Daten, die für die Suche notwendig sind und mit denen ihr momentaner Status gespeichert ist.
Zunächst erfolgt der Aufruf von FindFirst, um die Suche zu initialisieren {5}. Als Argumente werden der Dateiname (nach DOS-Konventionen, das heißt, es sind auch Sternchen erlaubt) mit vollständigem Pfad, nach dem gesucht werden soll, die Dateiattribute, die sie haben müssen, um gefunden zu werden, und eine Variable vom Typ SearchRec angegeben. Für die Dateiattribute wurde im obigen Programm die Konstante anyfile angegeben, damit alle Dateien und Verzeichnisse gefunden werden. Wenn die Suche erfolgreich verlaufen ist, enthält DosError den Wert Null, im Feld name von files ist die erste gefundene Datei enthalten und es beginnt eine while-Schleife{6}. Nach der Sicherstellung, ob das Suchergebnis nicht der Laufwerksname ist, wird es ausgegeben {7}. Falls die Escape-Taste gedrückt wurde, wird das Flag abbruch gesetzt {8}, was zum Abbruch der while-Schleife und der gesamten Suche führt. Anderenfalls wird die Suche mit dem Befehl FindNext fortgeführt {9}. Die Schleife endet spätestens dann, wenn keine entsprechende Datei mehr gefunden werden konnte und DosError daher einen Wert ungleich Null aufweist.
Die rekursiv programmierte Prozedur such ist ähnlich aufgebaut wie suchdateien, auch ihr wird ein Verzeichnisname als Parameter übergeben {10}. Die einzige lokale Variable ist dirs vom Typ SearchRec die für FindFirst und FindNext notwendig ist {11}. Die Prozedur wird nur dann weiter ausgeführt, wenn das Flag abbruch nicht gesetzt ist {12}, und es wird suchdateien mit dem übergebenen Verzeichnis als Parameter aufgerufen, um alle entsprechenden Dateien in diesem Verzeichnis anzuzeigen {13}. Dann wird FindFirst so aufgerufen, daß alle Unterverzeichnisse des übergebenen Verzeichnisses gefunden werden {14}. Wieder läuft eine while-Schleife, so lange, bis keine Unterverzeichnisse mehr gefunden werden können und DosError einen Wert ungleich Null besitzt oder bis das Flag abbruch gesetzt ist {15}. In der Schleife wird zunächst kontrolliert, ob es sich bei dem Suchergebnis wirklich um ein Unterverzeichnis und nicht um eines der Symbole für das gegenwärtige bzw. das darüberliegende Verzeichnis handelt {16}. (Wäre dies der Fall, käme es beim nachfolgenden Selbstaufruf nämlich zu einer endlosen Rekursion und somit zum Stack-Overflow.) Anschließend wird wieder überprüft, ob die Escape-Taste gedrückt wurde, und - wenn das der Fall ist - das Flag abbruch gesetzt {17}. Dann wird die Suche mit FindNext fortgesetzt. Die Schleife läuft, solange bis Escape gedrückt wird und die Variable abbruch den Wert True besitzt oder keine weiteren Unterverzeichnisse mehr gefunden werden können.
Im Hauptprogramm wird die zu suchende Datei als globale Variable, die in allen Unterprogrammen zugänglich ist, gespeichert, das Startverzeichnis wird der Prozedur such als Parameter übergeben. Diese gibt dann zuerst alle entsprechenden Dateien des übergebenen Verzeichnisses aus, durchsucht es dann nach Unterverzeichnissen und ruft sich mit jedem brauchbaren Suchergebnis selbst auf. Da viele Suchen durcheinanderlaufen, ist es wichtig, daß deren Status genau gespeichert wird. Um das braucht sich der Programmierer jedoch nicht zu kümmern, da ihm die Prozeduren FindFirst und FindNext dies abnehmen.
|
