Kapitel 1: die rekursion als mathematisches verfahren
Fachbereichsarbeit aus Informatik
Rekursive Verfahren
von Stefan Krywult
geschrieben bei
Hr. Prof. Herbert Paukert
BG/BRG Franklinstraße 21
Abgabetermin: 12.2.1998
Inhaltsverzeichnis
INHALTSVERZEICHNIS i
VORWORT ii
1 DIE REKURSION ALS MATHEMATISCHES VERFAHREN 1
2 DIE REALISIERUNG VON REKURSIONEN IM COMPUTER 2
2.1 Das modulare Konzept von Pascal 2
2.
2 Rekursionen in Pascal 3
3 REKURSIVE ANWENDUNGSPROGRAMME 6
3.1 Berechnung von Gliedern rekursiver Folgen 6
3.1.1 Die Fakultätsfunktion 7
3.1.2 Die Ackermann-Funktion 8
3.
2 Lösungsfindung durch Zerteilen eines Problems 10
3.2.1 Die ggT Berechnung nach Euklid 10
3.2.2 Quicksort 11
3.2.
3 Die Türme von Hanoi 13
3.3 Backtracking 15
3.2.1 Finden eines Weges aus einem Labyrinth 15
3.3.2 Suche nach möglichst kurzen Strecken zwischen mehreren Punkten 19
3.
2.3 Das Acht-Damen-Problem 23
3.3.4 Rekursives Durchsuchen des Verzeichnisbaumes nach Dateien 26
3.4 Grafische Anwendung der Rekursion 30
3.4.
1 Der fraktale Baum 30
3.4.2 Die Kochkurve 33
3.4.3 Die Sierpinsky-Dreiecke 36
ANHANG A1
A.1 Die Quellcodes aller erwähnten Programme A1
A.
2 Bibliographie und Quellennachweis A9
OFFIZIELLE ERKLÄRUNG
BESPRECHUNGSPROTOKOLL
Vorwort
Als leidenschaftlicher Hobbyprogrammierer und begeisterter Informatik-Wahlpflichtfach-Besucher wollte ich bei meiner Matura einen Schwerpunkt auf dieses interessante Fachgebiet setzen und beschloß daher, diese Fachbereichsarbeit zu schreiben. Ich habe das Thema „Rekursive Verfahren“ gewählt, weil mich die gewaltigen Möglichkeiten der rekursiven Programmierung beeindrucken: Scheinbar schwierige, beinahe unlösbar scheinende Aufgaben können mit ihrer Hilfe recht einfach bewältigt werden. Es übte einen zusätzlichen Reiz auf mich aus, daß Rekursionen dadurch, daß ihr Ablauf als ziemlich schwer zu durchschauen gilt, den Ruf des Geheimnisvollen haben.
Besonders bedanken möchte ich mich bei Herrn Professor Paukert, der mir nicht nur in vielen Sitzungen die Grundlagen meiner Fachbereichsarbeit zu erarbeiten half, sondern mir auch persönliche Aufzeichnungen als Literatur für meine Arbeit zur Verfügung stellte und mich auch zwischen den Sitzungen geduldig betreute. Er vertiefte außerdem mein Interesse in das Fachgebiet der Informatik und motivierte mich beim Schreiben dieser Arbeit.
Weiters möchte ich meiner Familie und vor allem meinen Eltern danken, die sich bemühten, jeden anderen Streß von mir fernzuhalten und besonders viel Verständnis für mich hatten, während ich an meiner Arbeit schrieb.
Abschließend möchte ich bemerken, daß es sicherlich wesentlich einfachere bzw. weniger aufwendige Varianten der Matura gegeben hätte. Trotzdem bin ich sehr froh, diese Form gewählt zu haben, da ich auf diese Weise auf vielen verschiedenen Gebieten wichtige, interessante und schöne Erfahrungen machen konnte.
Wien, 12.02.19981 Die Rekursion als mathematisches Verfahren
In der Mathematik gibt es zwei grundlegend verschiedene Methoden, das Bildungsgesetz einer bestimmten Folge darzustellen.
Bei der expliziten Beschreibung ist es möglich, ein Folgenglied direkt über die Nummer desselben auszurechnen, so zum Beispiel
an=2n+1 => a4: n = 4 => a4 = 2 * 4 + 1 => a4 = 9
=> a198: n = 198 => a198 = 2 * 198 + 1 => a198 = 397
Bei der rekursiven Darstellung wird das Glied nicht absolut definiert, sondern es wird nur der Zusammenhang mit dem vorigen Glied angegeben, so zum Beispiel
z an = a(n-1) + 2
Um also das dritte Glied dieser Folge zu erhalten, muß zuerst das zweite ausgerechnet werden. Das zweite basiert jedoch auf dem ersten. Die Glieder müssen daher schrittweise berechnet werden. Damit der Vorgang beim ersten Glied endet, muß dieses einen festen Wert besitzen, der ebenfalls bei der Definition angegeben werden muß. Das obige Bildungsgesetz lautet daher richtig:
an = a(n-1) + 2, a1 = 3
Dadurch wird dieselbe Folge wie oben definiert. Die Länge des Rechenwegs zu einem bestimmten Glied ist proportional zur Höhe der Gliednummer, während sie beim expliziten Bildungsgesetz immer gleich ist.
Hier sind zum Beispiel die Rechenschritte für das dritte Glied:
explizit: a3=2*3+1
a3=7
rekursiv: a3=a2+2
a2=a1+2
a1=3
a2=3+2
a3=3+2+2
a3=7
Trotz ihrer Länge ist die rekursive Darstellung oft nützlicher, da sie meistens einfacher ist und mit ihr manche Rechenarten gezielt umgangen werden können:
an = x*n => an = a(n-1)+x
an = x^n => an = a(n-1)*x
an = n! => an = a(n-1)*n
Abschließend ist zu bemerken, daß die Bildungsgesetze der meisten Folgen auf beide Arten darstellbar sind. Bei manchen ist dies jedoch nicht möglich.
2 Die Realisierung von Rekursionen im Computer
Rekursive Verfahren sind nicht nur in der Mathematik, sondern auch in der Informatik von großer Bedeutung. Sie werden nicht nur zum Errechnen rekursiver Folgen, die zum Beispiel bei der Darstellung von Wachstumsprozessen oder Fraktalen Anwendung finden, sondern auch zum schrittweisen und effektiven Lösen komplizierter und langwieriger Aufgaben (zum Beispiel bei Sortieralgorithmen oder Backtrackingprogrammen) verwendet.
Während früher solche Verfahren auch wirklich rekursiv programmiert wurden, werden sie heute meistens in einer leichter verständlichen iterativen, d.h.
nicht rekursiven, Form verwirklicht, was es Programmierern wesentlich erleichtert, sich in Programmen ihrer Kollegen zurechtzufinden.
In diesem Kapitel wird anhand der Programmiersprache Pascal die Programmierung und die Funktionsweise rekursiver Programme erklärt. Dazu muß vorher das modulare Konzept der Programmiersprache Pascal, an der die Verwendung rekursiver Verfahren demonstriert werden soll, näher betrachtet werden.
2.1 Das modulare Konzept von Pascal
Die Programmiersprache Pascal ermöglicht die Verwendung von sogenannten Unterprogrammen in Form von Prozeduren und Funktionen. Der einzige Unterschied zwischen den beiden ist, daß Funktionen nach dem Aufruf einen Wert besitzen und Prozeduren nicht.
Unterprogramme sind eigenständige Programmabschnitte, die aus dem Hauptprogramm, aber auch aus anderen Unterprogrammen, aufgerufen werden können. Ihre Verwendung ist von großem Vorteil, da sie das Programm übersichtlicher gestalten. So können lange Befehlsketten, die immer wieder vorkommen, durch einen einzigen Befehl, nämlich einen Unterprogrammaufruf, ersetzt werden. Dieser Aufruf wird Call genannt.
Bei einem Call werden auf dem Stack folgende Informationen gespeichert:
die Parameter für das Unterprogramm,
die Rücksprungadresse, d.h.
die Speicherstelle, an der die Programmausführung nach dem Durchlaufen des Unterprogrammes fortgesetzt werden soll,
der letzte Inhalt des BP-Registers(),
lokale Variablen, die nur im Unterprogramm Gültigkeit haben,
etwaige Funktionswerte.
Die Verwaltung des Stacks erfolgt nach dem LIFO-Prinzip (Last In - First Out) wobei der zuletzt abgelegte Wert als erstes wieder gelesen wird. Den Vorgang, Daten auf den Stack zu legen, nennt man Push.
Beim Verlassen eines Unterprogrammes ermöglicht die zuvor auf den Stack geschriebene Rücksprungadresse die Rückkehr zum aufrufenden Programmteil (RET). Der Speicherplatz der lokalen Variablen wird wieder freigegeben, und auf dem Stack liegende Werte werden in umgekehrter Reihenfolge wieder abgehoben. Dieser Prozeß wird POP genannt.
Vom Stack entfernte Daten sind unwiderruflich gelöscht.
In Pascal ist es möglich, auch aus einem Unterprogramm heraus ein anderes Unterprogramm aufzurufen. Es ist sogar zulässig, daß ein Unterprogramm während seines Ablaufes sich selbst noch einmal aufruft. Diesen Selbstaufruf nennt man Rekursion.
2.2 Rekursionen in Pascal
Bei der rekursiven Definition von Folgen, die im vorigen Kapitel beschrieben wurde, ist es notwendig, das erste Glied a1 absolut zu bestimmen, indem man ihm einen Zahlenwert zuweist.
Auch bei der Programmierung rekursiver Unterprogramme muß es eine Abbruchbedingung geben, bei der die Rekursion stoppt und kein neuerlicher Selbstaufruf mehr erfolgt. Beim Fehlen einer Abbruchbedingung ruft sich das Unterprogramm so lange selbst auf, bis der Stack-Speicher erschöpft ist. In der Folge kommt es zu einer Fehlermeldung, dem sogenannten Stack-Overflow.
Wird ein rekursives Unterprogramm aufgerufen, erfolgt ein Push-Vorgang und Daten werden auf den Stack gelegt. Dann werden die Befehle bis zum Selbstaufruf ausgeführt. Dies wird „rekursiver Aufstieg“ genannt.
Ist die Abbruchbedingung noch nicht erreicht, erfolgt ein Selbstaufruf. Erneut werden Daten auf dem Stack abgelegt.
So entwickelt sich Schritt für Schritt eine Datenstruktur auf dem Stack. Bis jetzt wurde nur der rekursive Aufstieg ausgeführt. Tritt jedoch die Abbruchbedingung in Kraft, erfolgt der „rekursive Abstieg“, bei dem die Befehle nach dem Selbstaufruf ausgeführt werden. Nach Beendigung des Unterprogrammes werden Daten vom Stack geholt.
Es erfolgt ein schrittweises Auflösen der zuvor gebildeten Datenstruktur. Der rekursive Abstieg endet mit dem Rücksprung ins Hauptprogramm.
Die Anzahl der Selbstaufrufe nennt man „Rekursionstiefe.“
Folgendes Beispielprogramm soll zur Veranschaulichung des Rekursionsablaufes dienen:
program rekursion01;
uses crt;
var i : integer;
procedure zaehl(von:integer); {rekursive Prozedur mit dem Parameter von}
begin
write(von,' '); {Variable von am Bildschirm ausgeben - Rekursionsaufstieg}
if von>0 then zaehl(von-1); {Abbruchbedingung und Selbstaufruf}
write(von,' '); {Variable von am Bildschirm ausgeben-Rekursionsabstieg}
end;
begin
clrscr;
write('Rekursionstiefe: ');
readln(i);
zaehl(i); {erstmaliger Aufruf mit dem zuvor eingegebenen Wert i}
readln;
clrscr;
end.
Dieses Beispielprogramm gibt, wenn als Rekursionstiefe 6 eingegeben wurde, Folgendes am Bildschirm aus:
6 5 4 3 2 1 0 0 1 2 3 4 5 6
aufsteigende absteigende Rekursion
Um den Rekursionsablauf zu beschreiben, wird nur 3 als Eingabe für die Rekursiontiefe angenommen, damit sich die Länge der Beschreibung in Grenzen hält. Wird die Prozedur zaehl mit dem Wert 3 aufgerufen, so wird zunächst die Zahl Drei am Bildschirm ausgegeben.
Anschließend kommt es zu einem Selbstaufruf, da die Rekursionsbedingung erfüllt ist (Drei ist größer als Null). Als Parameter wird der eigene Parameter, um Eins verringert, übergeben. Für den neuen Prozeduraufruf werden neue lokale Variable auf dem Stack abgelegt, die der aufrufenden Prozedur bleiben jedoch auf dem Stack erhalten, da diese noch nicht beendet wurde. Hierauf wird die Zahl Zwei ausgegeben, und es kommt erneut zum Selbstaufruf.
Dieser Ablauf setzt sich so lange fort, bis die Prozedur zaehl mit Null als Parameter aufgerufen wird. Auch Null wird am Bildschirm ausgegeben, aber es kommt zu keinem weiteren Selbstaufruf, da die Rekursionsbedingung nicht mehr erfüllt ist (Null ist nicht größer als Null), und der Rekursionsabstieg beginnt.
Der Programmablauf wird mit dem nächsten Befehl der Prozedur fortgesetzt, und Null wird nochmals am Bildschirm ausgegeben. Dann wird das Unterprogramm beendet, die lokalen Variablen vom Stack entfernt und zur aufrufenden Prozedur zurückgekehrt. Hier hat die Variable von den Wert Eins. Die Zahl Eins wird daher ausgegeben und das Unterprogramm beendet. Wieder werden die lokalen Variablen vom Stack gelöscht und die Programmausführung mit der aufrufenden Prozedur fortgesetzt, in der die Variable von den Wert Zwei besitzt.
Nach der Ausgabe der Zahlen Zwei und Drei erfolgt schließlich der Rücksprung ins Hauptprogramm - die Rekursion ist beendet.
Bei jedem Aufruf der Prozedur zaehl wird für die Variable von neuer Speicherplatz belegt, sie ist daher jeweils nur auf einer Rekursionstufe gültig, d.h. auf jeder Rekursionsstufe bezeichnet die Variable von eine andere Stelle im Speicher. Um die Push- und Pop-Vorgänge muß sich der Programmierer in Pascal nicht selbst kümmern. Der Stack wird automatisch vom Compiler verwaltet. Um die compilerinterne Verwaltung des Stack zu veranschaulichen, habe ich das obige Programm so verändert, daß nicht nur die Variablenwerte, sondern auch deren Speicheradressen angegeben werden.
Außerdem wird die Adresse des Stack vor und nach dem Durchlaufen der Rekursion angezeigt. Den genauen Quellcode kann man dem Anhang entnehmen (A1, „rekursion01tx“). Die Ausgabe des Programms sieht ungefähr so aus:
Vor dem Prozeduraufruf: Stacksegment: 29031 Stackpointer: 16378
von: Wert: 3 Adresse: 29031:16380 Stackpointer: 16372
von: Wert: 2 Adresse: 29031:16374 Stackpointer: 16366
von: Wert: 1 Adresse: 29031:16368 Stackpointer: 16360
von: Wert: 0 Adresse: 29031:16362 Stackpointer: 16354
von: Wert: 0 Adresse: 29031:16362 Stackpointer: 16354
von: Wert: 1 Adresse: 29031:16368 Stackpointer: 16360
von: Wert: 2 Adresse: 29031:16374 Stackpointer: 16366
von: Wert: 3 Adresse: 29031:16380 Stackpointer: 16372
Nach dem Prozeduraufruf: Stacksegment: 29031 Stackpointer: 16378
Die maximale Größe des Stack beträgt 16 Kilobyte, und er wird von der höchsten bis zur niedrigsten Adresse gefüllt. Daher wird die Adresse des Stack-Endes, auf das der Stackpointer zeigt, mit jedem Prozeduraufruf kleiner.
3 Rekursive Anwendungsprogramme
Die Anwendungen der rekursiven Unterprogrammtechnik lassen sich in vier verschiedene Gruppen gliedern. Es sei nochmals darauf hingewiesen, daß heute fast alle Programme iterativ programmiert sind, um sie übersichtlicher zu gestalten, da die rekursiven Varianten manchmal ein schlechteres Laufzeitverhalten besitzen.
Dennoch ist die rekursive Programmierung bei vielen Projekten von großem Vorteil, da sie oft eine leichtere und schnellere Verwirklichung des Programms ermöglicht. Daher werden in diesem Kapitel vier wichtige Einsatzbereiche der rekursiven Unterprogrammtechnik beschrieben und Beispiele dazu gegeben.
3.1 Berechnung von Gliedern rekursiver Folgen
Das wohl naheliegendste Einsatzgebiet ist das Berechnen von Gliedern rekursiver Folgen. Hier bietet sich der Eisatz von rekursiven Funktionen an, die selbst einen Wert annehmen können. Beim Aufruf der Funktion muß überprüft werden, ob die als Parameter übergebene Nummer des Gliedes Eins ist.
Wenn dies der Fall ist, wird der Funktion der Wert für a1 übergeben und die Funktion beendet. Andernfalls wird der Funktion ein Wert zugewiesen, der aus einer Berechnung mit dem Funktionswert des vorhergehenden Gliedes resultiert, was einen Selbstaufruf mit dem um eins verringerten Parameter zur Folge hat - der Vorgang beginnt von neuem.
Im Folgenden sollen zwei Beispiele näher betrachtet werden:
3.1.1 Die Fakultätsfunktion
Die Glieder der Fakultätsfunktion erhält man, indem man alle ganzen Zahlen von 1 bis inklusive der Nummer des zu berechnenden Gliedes multipliziert. So ergibt sich für das dritte Glied zum Beispiel 6, für das fünfte schon 120.
Die Fakultätsfunktion läßt sich leicht in der rekursiven Form darstellen: an = n * a(n-1), wobei das erste Glied den Wert Eins besitzt. Auf diesem Bildungsgesetz basiert das folgende Programm:
program fakultaet;
uses crt;
var i : integer;
function fakt(n : integer) : real;
begin
if n=1 then fakt:=1 else fakt:=fakt(n-1)*n;
end;
begin
clrscr;
writeln(' Fakultätsberechnungsprogramm von Stefan Krywult');
write('n = ');
readln(i);
writeln(i,'! = ',fakt(i));
readln;
clrscr;
end.
Zunächst gibt der Benützer die Zahl ein, deren Fakultät berechnet werden soll. Sie wird in der Integervariablen i zwischengespeichert und dann der rekursiven Funktion fakt als mit n bezeichneter Parameter übergeben. Nun beginnt eine rekursive Schleife: Solange n größer als eins ist, erfolgen Selbstaufrufe, und die Werte, welche die Funktion dabei zurückliefert, werden mit dem jeweils gültigen n multipliziert. Ist n gleich eins, wird der Funktion der Wert Eins zugewiesen.
Nun folgt der genaue Ablauf der Rekursion, wenn als Startparameter Drei übergeben wurde:
Rekursionsebene: 1 n = 3 n <> 1 fakt := fakt(2)*3
Rekursionsebene: 2 n = 2 n <> 1 fakt := fakt(1)*2
Rekursionsebene: 3 n = 1 n = 1 fakt := 1
Rekursionsebene: 2 n = 2 n <> 1 fakt := 1*2 fakt := 2
Rekursionsebene: 1 n = 3 n <> 1 fakt := 2*3 fakt := 6 => fakt(3) = 6
3.1.2 Die Ackermann-Funktion
Wesentlich schwerer ist es, die Ackermann-Funktion zu berechnen. Sie ist eine zweidimensionale Funktion, das heißt, sie benötigt zwei Parameter. Ihr Bildungsgesetz sieht so aus:
n + 1 für m = 0, n > 0
A(m,n) = A(m-1, 1) für m > 0, n = 0
A(m-1, A(m, n-1)) für m > 0, n > 0
Doch auch diese Funktion läßt sich fast nach dem selben Schema wie die Fakultätsfunktion programmieren: Zuerst muß ermittelt werden, welcher der drei Fälle vorliegt (bei der Fakultät waren es nur zwei: n=1 oder n>1). Dann erfolgt entweder ein Selbstaufruf mit den entsprechenden Parametern oder die einfache Berechnung A=n+1.
Mit folgender Pascalfunktion lassen sich Werte der Ackermann-Funktion berechnen, der restliche Programmcode kann dem Anhang entnommen werden (A1, „ackermann“):
function ack(m, n : integer) : integer;
begin
If (m=0) and (n>0) then ack := n+1
If (m>0) and (n=0) then ack := ack(m-1,1);
If (m>0) and (n>0) then ack := ack(m-1, ack(m,n-1));
end;
Der Rekursionsablauf ist bei dieser Funktion nur schwer zu durchschauen, da sie sich oftmals sogar zweimal selbst aufruft: Sie ruft sich auf, um den Parameter für den eigentlichen Selbstaufruf zu erhalten. Da die Wahrscheinlichkeit, daß beide Parameter größer als Eins sind, ziemlich groß ist, verzweigt sich die Funktion häufig.
Das heißt: Die Funktion ruft sich zweimal auf, diese beiden Funktionen rufen sich wieder zweimal auf und so weiter. Die Zahl der Selbstaufrufe wächst daher stetig. Die rekursive Berechnung der Ackermann-Funktion ist deshalb sehr zeit- und speicherintensiv. Hier wäre es günstiger, die wesentlich schwierigere, aber zeit- und speichersparende iterative Variante zu wählen.
Um den komplizierten Ablauf der Funktionsberechnung zu zeigen, folgt nun die Beschreibung des Ablaufes nach dem Funktionsaufruf ack(1, 1):
Rekursionsebene: 1 m = 2 n = 1 m > 0 n > 0 ack := ack(1, ack(2,0))
Rekursionsebene: 2 m = 2 n = 0 m > 0 n = 0 ack := ack(1, 1)
Rekursionsebene: 3 m = 1 n = 1 m > 0 n > 0 ack := ack(0,ack(1,0))
Rekursionsebene: 4 m = 1 n = 0 m > 0 n = 0 ack := ack(0,1)
Rekursionsebene: 5 m = 0 n = 1 m = 0 n > 0 ack := 1+1 ack := 2
Rekursionsebene: 4 m = 1 n = 0 m > 0 n = 0 ack := 2
Rekursionsebene: 3 m = 1 n = 1 m > 0 n > 0 ack := ack(0, 2);
Rekursionsebene: 4 m = 0 n = 2 m = 0 n > 0 ack := 2 + 1 ack := 3
Rekursionsebene: 3 m = 1 n = 1 m > 0 n > 0 ack := 3
Rekursionsebene: 2 m = 2 n = 0 m > 0 n > 0 ack := 3
Rekursionsebene: 1 m = 2 n = 1 m > 0 n > 0 ack := ack(1, 3)
Rekursionsebene: 2 m = 1 n = 3 m > 0 n > 0 ack := ach(0, ack(1, 2))
Rekursionsebene: 3 m = 1 n = 2 m > 0 n > 0 ack := ach(0, ack(1, 1))
Rekursionsebene: 4 m = 1 n = 1 m > 0 n > 0 ack := ach(0, ack(1, 0))
Rekursionsebene: 5 m = 1 n = 0 m > 0 n = 0 ack := ach(0, 1)
Rekursionsebene: 6 m = 0 n = 1 m = 0 n > 0 ack := 1+1 ack := 2
Rekursionsebene: 5 m = 1 n = 0 m > 0 n = 0 ack := 2
Rekursionsebene: 4 m = 1 n = 1 m > 0 n > 0 ack := ach(0, 2)
Rekursionsebene: 5 m = 0 n = 2 m = 0 n > 0 ack := 2 + 1 ack := 3
Rekursionsebene: 4 m = 1 n = 1 m > 0 n > 0 ack := 3
Rekursionsebene: 3 m = 1 n = 2 m > 0 n > 0 ack := ach(0, 3)
Rekursionsebene: 4 m = 0 n = 3 m > 0 n > 0 ack := 3 + 1 ack := 4
Rekursionsebene: 3 m = 1 n = 2 m > 0 n > 0 ack := 4
Rekursionsebene: 2 m = 0 n = 3 m > 0 n > 0 ack := ach(0, 4)
Rekursionsebene: 3 m = 0 n = 4 m = 0 n > 0 ack := 4 +1 ack := 5
Rekursionsebene: 2 m = 0 n = 3 m > 0 n > 0 ack := 5
Rekursionsebene: 1 m = 2 n = 1 m > 0 n > 0 ack := 5
3.2 Lösungsfindung durch Zerteilen eines Problems
Oft werden Rekursionen dazu eingesetzt, um ein komplexes Problemlösungsverfahren in viele kleine, einfach zu lösende, Teilschritte aufzuspalten, durch deren Ausführung die gestellte Aufgabe schließlich gelöst werden kann.
Das Aufspalten erfolgt in mehreren Stufen, sodaß dieser Prozeß am besten mit einem Baumdiagramm darzustellen ist. Diese Baumstruktur verästelt sich, vom gegebenen Problem ausgehend, schrittweise in immer mehr und kleinere Probleme, bis diese leicht zu lösen sind. Bei den Baumdiagrammen unterscheidet man zwei Typen: den einfachen, bzw. linearen, und den mehrfach verzweigten, bzw.
unlinearen Typ, je nachdem, wie viele Verzweigungen von den Knotenpunkten des Baumes ausgehen. Bei linearen Bäumen hält sich die Größe der Struktur in Grenzen - mit jedem Lösungsschritt gibt es einen Ast mehr, und auch der Speicheraufwand steigt linear zur Anzahl der Lösungsschritte. Bei doppelt verzweigten Strukturen wächst der Speicheraufwand quadratisch mit der Anzahl der Lösungsschritte, bei dreifach verzweigten kubisch, und so weiter.
Folgende Programme dienen nicht nur als theoretisches Beispiel, sondern sind auch in der Praxis effizient einzusetzen.
3.2.
1 Die ggT Berechnung nach Euklid
Der griechische Mathematiker Euklid fand ein Verfahren, das es ermöglicht, den größten gemeinsamen Teiler (ggT) zweier Zahlen ohne Primfaktorenzerlegung zu berechnen. Beim Euklidischen Algorithmus (oder Kettendivision) wird zuerst der Rest R der Division der Zahl Z1 und der Zahl Z2 gebildet. Dann wird der Divisor Z2 durch den Rest R dividiert und der neue Rest gebildet. Mit diesem Verfahren fährt man so lange fort, bis man als Rest Null erhält, der letzte Rest, der größer als Null ist, teilt dann alle vorherigen Divisoren und Dividenden und ist somit ggT der Zahlen Z1 und Z2.
Dieser Algorithmus läßt sich als rekursive Funktion programmieren. Das komplexe Problem, den ggT zweier Zahlen zu suchen, beschränkt sich auf die einfache Kontrolle, ob der Rest der Division zweier Zahlen Null ist.
Da sich das rekursive Unterprogramm nur einmal selbst aufruft, steigt der Speicheraufwand linear mit der Anzahl der Lösungsschritte.
Die Funktion ggT sieht folgendermaßen aus:
function ggT(z1, z2 :integer);
begin
if z2=0 then ggt:=z1else ggt:=ggt(z2, z1 mod z2);
end;
(Den Rest des Programmes ist im Anhang zu finden)
Ist der Rest der letzten Division, der in z2 übergeben wurde, Null, dann ist der vorige Rest in z1 der ggT. Andernfalls ruft sich die Funktion mit dem Rest der letzten Division z2 und dem Rest der neuen Division (z1 mod z2) selbst auf. Im Speicher bildet sich beim Aufruf von ggt(64,52) folgende Baumstruktur:
ggt(64,52) -- ggt(52,12) -- ggt (12,4)
Dann bricht die Rekursion ab, da der Rest der Division Zwölf durch Vier Null ist.
3.2.
2 Quicksort
Quicksort ist , wie der Name bereits andeutet, ein sehr schnelles, natürlich rekursives Sortierverfahren. Der Quicksort-Algorithmus ist das Paradebeispiel für das Lösen komplexer Probleme durch Zerteilung:
In einem eindimensionalen Feld (Vektor) werden Daten gespeichert. Dann wird das rekursive Quicksort-Unterprogramm aufgerufen, wobei ihm als Parameter der Start- sowie der Endindex des zu sortierenden Feldbereiches übergeben werden. Der Algorithmus nimmt einen Wert aus diesem Feldbereich heraus (meistens den mittleren) und teilt den zu sortierenden Bereich somit in eine linke und in eine rechte Hälfte. Dann werden alle Werte im linken Teil, die größer sind als der herausgenommene Wert, mit einem aus dem rechten Teil, der kleiner ist als der Trennwert, vertauscht. Danach steht der Trennwert bereits an der richtigen Stelle.
Hierauf ruft sich das Unterprogramm zweimal selbst auf, um den linken und den rechten Teil nach dem obigen Schema zu sortieren.
Nun folgt der Quellcode des Quicksort-Algorithmus (a ist ein global definiertes array of integer). Die Erläuterung der einzelnen Programmstellen erfolgt erst nach dem Programmcode unter der jeweils zugeordneten Zahl:
procedure quicksort(l, r: integer);
var i, j, x, hilf: integer;
begin
i:=l;
j:=r;
x:=a[(l+r) div 2]; {1}
repeat
while a[i]< x do inc(i); {2}
while a[j]> x do dec(j); {3}
if i<=j then begin {4}
hilf:=a[i];
a[i]:=a[j]; {5}
a[j]:=hilf;
inc(i); {6}
dec(j);
end;
until i>j; {7}
if l<j then quicksort(l,j); {8}
if r>i then quicksort(i,r);
end;
Das vollständige Beispielprogramm sorter.pas ist auf der Begleitdiskette zu finden, das die Effiziens des Quicksort-Algorithmus und des Minimumsort-Verfahren im Vergleich zeigt. Der komplette Quellcode dieses Programmes ist im Anhang (A2, „sorter“) abgedruckt.
Zuerst wird das mittlere Element als Trennelement in der Variablen x zwischengespeichert {1}.
Die beiden Teilbereiche werden nacheinander von außen nach innen zum Trennelement hin durchlaufen. Im linken Teil wird ein Element gesucht {2}, das größer als das Trennelement ist, im rechten eines, das kleiner ist {3}. Dann werden diese Elemente, wenn sie wirklich in der falschen Hälfte liegen {4}, ausgetauscht {5}. Schließlich geht der Algorithmus sowohl in der linken als auch in der rechten Hälfte um eine Position weiter {6}, um nicht noch einmal die selben Elemente miteinander zu vergleichen. Es werden solange Elemente ausgetauscht, bis beide Seiten zur Gänze durchlaufen wurden {7}. Dann werden beide Teilmengen, wenn sie noch aus mehr als einem Element bestehen, durch einen Selbstaufruf der Prozedur quicksort sortiert {8}.
Die Größe des Sortierbereiches wird somit mit jedem neuerlichen Prozeduraufruf halbiert. Da ein zweifacher Selbstaufruf erfolgt ist, besitzt der Quicksort-Algorithmus eine doppelt verzweigte Baumstruktur.
Der iterative Sortieralgorithmus Bubblesort benötigt beim Sortieren eines Feldes mit 1000 Werten durchschnittlich etwa 50 mal so viele Vergleiche wie der Quicksort-Algorithmus. Unter bestimmten Bedingungen kann dieser jedoch entarten, sodaß beinahe so viele Vergleiche notwendig sind wie beim Bubblesort. Dies kann passieren, wenn der Wert des Trennelements sehr hoch oder sehr niedrig ist. Denn dann wird der zu sortierende Bereich nicht halbiert, sondern bleibt beinahe unverändert.
Je häufiger ein extremer Wert als Trennwert genommen wird, desto langsamer wird der Quicksort-Algorithmus.
3.2.3 Die Türme von Hanoi
Eines der bekanntesten Beispiele für eine praktische Anwendung der Rekursion ist das altchinesische Brettspiel 'Die Türme von Hanoi'. Es besteht aus einer Platte, auf der drei Stäbe senkrecht aufgestellt sind. Auf einem von ihnen befindet sich eine nach Belieben wählbare Anzahl von Scheiben mit verschiedenen, nach oben hin stetig abnehmenden Radien.
Ziel des Spieles ist es, alle Scheiben in gleicher Anordnung auf den dritten Stab umzuschichten, wobei der zweite als Hilfe verwendet werden kann. Es darf immer nur eine Scheibe bewegt werden, und diese darf nur auf einer Scheibe mit größerem Radius zu liegen kommen.
Ist nur eine Scheibe vorhanden, kann sie direkt vom ersten auf den dritten Stab gelegt werden. Bei zwei Scheiben muß die erste Scheibe auf dem zweiten Stab zwischengelagert werden, damit die zweite Scheibe vom ersten auf den dritten Stab gebracht werden kann. Liegen drei Scheiben auf dem ersten Stab, müssen folglich zwei Scheiben zuerst auf den zweiten Stab gebracht werden, um die dritte Scheibe ans Ziel bringen zu können. Dann muß die kleinste Scheibe am nun leeren ersten Stab zwischengelagert werden, um die mittlere Scheibe auf den dritten Stab legen zu können.
Schließlich kann dann auch die kleinste Scheibe auf den Turm geschichtet werden.
Der Arbeitsaufwand wächst mit jeder Scheibe enorm an. Doch auch hier kann man das komplexe Problem der Umlagerung der Scheiben mit Hilfe der Rekursion in kleine Teilprobleme aufteilen: Alle Scheiben mit Ausnahme der jeweils größten werden auf einem freien Stab, im Folgenden Puffer genannt, zwischengelagert, so daß die verbleibende letzte Scheibe problemlos ans Ziel gebracht werden kann. Dieser Vorgang wird so lange wiederholt, bis alle Scheiben umgelagert worden sind. Obwohl dieser Vorgang kompliziert klingt, ist er dennoch einfach zu programmieren:
procedure hanoi(anzahl, quelle, puffer, ziel :integer);
begin
if anzahl=1 then writeln('Scheibe von ',quelle,' nach ',ziel,'.') else begin {1}
hanoi(anzahl-1, quelle, ziel, puffer); {2}
writeln('Scheibe von ',quelle,' nach ',ziel,'.
'); {3}
hanoi(anzahl-1,puffer, quelle, ziel); {4}
end;
end;
Der Aufruf der Prozedur hanoi (4,1,2,3) würde also alle Schritte, die für das Umschichten vom ersten auf den dritten Stab unter der Zuhilfenahme des zweiten notwendig sind, am Bildschirm ausgeben. Beim vollständigen Programm, das im Anhang (A3, „Tuerme_von_Hanoi“) abgedruckt ist, kann der Benutzer die Zahl der Scheiben frei wählen. Die Anzahl der notwendigen Züge steigt jedoch exponential mit der Scheibenzahl. Für n Scheiben sind immer 2n - 1 Züge notwendig. Diesen Zusammenhang erhält man, da sich das rekursive Unterprogramm zweimal selbst aufruft.
Die Idee der Prozedur ist, daß eine Scheibe direkt ans Ziel gebracht wird, wenn dies möglich ist {1}.
Anderenfalls werden zuerst alle darüberliegenden Scheiben auf den Pufferstab gebracht {2}, dann wird die erste Scheibe auf den Zielstab gelegt {3}, und schließlich werden alle andern Scheiben ebenfalls ans Ziel gebracht {4}. Der genaue Rekursionsablauf, der dem Aufruf hanoi (3,1,2,3) folgt, ist folgender:
hanoi(3,1,2,3); 321
hanoi(2,1,3,2); 321
hanoi(1,1,2,3); 321
writeln('Scheibe von 1 nach 3.'); 32 1
writeln('Scheibe von 1 nach 2.'); 3 2 1
hanoi(1,3,1,2); 3 2 1
writeln('Scheibe von 3 nach 2.'); 3 21
writeln('Scheibe von 1 nach 3.'); 21 3
hanoi(2,2,1,3); 21 3
hanoi(1,2,3,1); 21 3
writeln('Scheibe von 2 nach 1.
'); 1 2 3
writeln('Scheibe von 2 nach 3.'); 1 32
hanoi(1,1,2,3); 1 32
writeln('Scheibe von 1 nach 3.'); 321
Je weiter die Zeilen eingerückt sind, desto tiefer ist die Rekursionsebene. Die Zahlenreihen auf der linken Seite zeigen die Stäbe eins bis drei. Die Zahlen selbst repräsentieren die Scheiben, wobei Eins für die mit dem kleinsten Radius steht, und Drei für die mit dem größten. Das rechte Ende der Zahlenreihen ist die Spitze des Stabes.
3.3 Backtracking
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 (lang<min) or (min=0) then begin {8}
min:=lang;
kweg:=weg;
end;
end
else
begin
for k:=1 to ortanz do {9}
if (ortnetz[ort,k]>0) 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
| Anmerkungen: |
| impressum | datenschutz
© Copyright Artikelpedia.com
