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.
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 => a : n = 4 => a => a
=> a : n = 198 => a => a
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)
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, a
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: a
a
rekursiv: a =a
a =a
a
a
a
a
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.
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.
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.
Bei der rekursiven Definition von Folgen, die im vorigen Kapitel beschrieben wurde, ist es notwendig, das erste Glied a 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);
begin
write(von,' ');
if von>0 then zaehl(von-1);
write(von,' ');
end;
begin
clrscr;
write('Rekursionstiefe: ');
readln(i);
zaehl(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.
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.
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 a ü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:
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
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
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.
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.
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];
repeat
while a[i]< x do inc(i);
while a[j]> x do dec(j);
if i<=j then begin
hilf:=a[i];
a[i]:=a[j];
a[j]:=hilf;
inc(i);
dec(j);
end;
until i>j;
if l<j then quicksort(l,j);
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 . Die beiden Teilbereiche werden nacheinander von außen nach innen zum Trennelement hin durchlaufen. Im linken Teil wird ein Element gesucht , das größer als das Trennelement ist, im rechten eines, das kleiner ist . Dann werden diese Elemente, wenn sie wirklich in der falschen Hälfte liegen , ausgetauscht . Schließlich geht der Algorithmus sowohl in der linken als auch in der rechten Hälfte um eine Position weiter , um nicht noch einmal die selben Elemente miteinander zu vergleichen. Es werden solange Elemente ausgetauscht, bis beide Seiten zur Gänze durchlaufen wurden . Dann werden beide Teilmengen, wenn sie noch aus mehr als einem Element bestehen, durch einen Selbstaufruf der Prozedur quicksort sortiert . 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.
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
hanoi(anzahl-1, quelle, ziel, puffer);
writeln('Scheibe von ',quelle,' nach ',ziel,'.');
hanoi(anzahl-1,puffer, quelle, ziel);
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 . Anderenfalls werden zuerst alle darüberliegenden Scheiben auf den Pufferstab gebracht , dann wird die erste Scheibe auf den Zielstab gelegt , und schließlich werden alle andern Scheiben ebenfalls ans Ziel gebracht . 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.
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.
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),
(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;
var lab : feld;
procedure zeigelab;
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);
var a,b : integer;
begin
gotoxy(x*2-1,y);
textcolor(14);
write(#219,#219);
delay(333);
if not gefunden then begin
case lab[x,y] of
3: begin
gefunden:=true;
zeigelab;
end;
2:begin
gotoxy(x*2-1,y);
textcolor(6);
write(#219,#219);;
end;
1:begin
gotoxy(x*2-1,y);
textcolor(4);
write(#219,#219);;
end;
0: begin
lab[x,y]:=1;
zeigelab;
if not gefunden then suchweg(x-1,y);
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;
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 . Die Variable gefunden ist ein Flag . 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 dient lediglich zum Anzeigen des Labyrinths und des bisher gegangenen Weges. Die rekursive Prozedur suchweg 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 . Nur wenn noch kein Ausweg gefunden wurde, wird das Feld getestet . Ist das aktuelle Feld ein Ausgang, wird der Flag gefunden auf True gesetzt und es erfolgt kein Selbstaufruf . Befindet sich aber eine Mauer darauf oder oder wurde es bereits betreten , 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 : Das Feld wird als betreten markiert , 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 . Sind alle Versuche beendet, wird das Feld wieder als unbetreten markiert , 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.
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),
( 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;
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);
var k : integer;
begin
weg:=weg+chr(48+ort);
if ort=ziel then begin
writeln(weg);
inc(gefunden);
if gefunden mod 10 = 0 then begin
writeln;
write('Weiter mit irgendeiner Taste');
wt;
clrscr;
end;
if (lang<min) or (min=0) then begin
min:=lang;
kweg:=weg;
end;
end
else
begin
for k:=1 to ortanz do
if (ortnetz[ort,k]>0) and (pos(chr(48+k),weg)=0) then begin
lang:=lang+ortnetz[ort,k];
gehezu(k);
lang:=lang-ortnetz[ort,k];
end;
end;
weg:=copy(weg,1,length(weg)-1);
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 . Die Orte selbst sind durch die Zahlen Eins bis Sieben definiert. Die Prozedur zeigeortsnetz dient zur tabellierten Anzeige dieser Daten. Das Unterprogramm gehezu 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 , worin der bisher zurückgelegte Weg gespeichert ist. Wenn der aktuelle Ort bereits der Zielort ist , wird der bisherige Weg am Bildschirm ausgegeben und die Anzahl der gefundenen Wege um eins erhöht . Außerdem wird die aktuelle Weglänge mit der bisher kürzesten verglichen und das Minimum gegebenenfals neu gesetzt .
Ist der Zielort jedoch noch nicht erreicht, wird systematisch versucht, alle anderen Orte von der momentanen Position aus zu erreichen. 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) . Kann der Ort betreten werden, wird die Länge der Verbindung des neuen und des momentanen Ortes zur Gesamtlänge des Weges addiert und das Unterprogramm gehezu mit dem neuen Ort als Parameter aufgerufen . 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 . Am Ende der Prozedur wird die letzte Wegnummer aus dem String weg wieder entfernt, um ihn wieder zugänglich zu machen .
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;
var start : Tbrett;
i,ii,verz : integer;
danz, lanz : integer;
gefunden : boolean;
procedure zeigbrett(br:Tbrett);
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);
var ax,ay,b : integer;
test : tbrett;
begin
if (verz >0) and not gefunden then begin
gotoxy(1,1);
zeigbrett(brett);
delay(verz);
end;
if (danz=8) and not gefunden then begin
clrscr;
zeigbrett(brett);
gefunden:=true;
writeln(#7);
wt;
end
else if not gefunden then begin
for ax:=1 to 8 do begin
ay:=danz+1;
if brett[ax,ay]=0 then begin
test:=brett;
test[ax,ay]:=2;
inc(danz);
for b:=1 to 8 do begin
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);
dec(danz);
end;
end;
end;
end;
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): ');
readln(verz);
clrscr;
writeln('Suche läuft');
for i:=1 to 8 do for ii:=1 to 8 do start[i,ii]:=0;
stell_dame(start);
window(1,1,80,25);
clrscr;
end.
Mit der Type-Anweisung 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 . Die Prozedur zeigebrett dient zur Anzeige des momentanen Suchfortschrittes und der Lösungen. Das rekursive Unterprogramm stell_dame 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 . 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 . 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 , dann wird das Flag gefunden gesetzt, wodurch die Suche abgebrochen wird. Anderenfalls wird die nächste Zeile, in der noch keine Dame steht, durchlaufen und nach freien Feldern durchsucht . Wurde eines entdeckt , wird zuerst das übergebene Feld in die Hilfsvariable hilf kopiert . In diese wird die gefundene freie Stelle als von einer Dame besetzt markiert . Nachdem die Anzahl der Damen erhöht wurde , werden im Array hilf auch alle von der neu aufgestellten Dame bedrohten Felder markiert . 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 .
Danach wird die Anzahl der Damen wieder um eins reduziert . 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 im Hauptprogramm müssen zuerst die gewünschte Verzögerung der Suchdarstellung in verz eingegeben 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 .
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;
var anz : integer;
s : string;
ch : char;
suchstring : string;
suchpfad : string;
procedure ausgabe(erg : string; a:byte);
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);
var files : SearchRec;
begin
if not abbruch then begin
FindFirst(verzeichnis+suchstring,anyfile,files);
while (doserror=0) and not abbruch do begin
if ((files.attr and VolumeID)<>VolumeID)
then ausgabe(verzeichnis+files.name, files.attr);
if keypressed then begin
ch:=readkey;
if ch=#27 then abbruch:=true;
end;
findnext(files);
end;
end;
end;
procedure such(verzeichnis:string);
var dirs : SearchRec;
begin
if not abbruch then begin
suchdateien(verzeichnis);
FindFirst(verzeichnis+'*.*',directory,dirs);
while (doserror=0) and not abbruch do begin
if (dirs.attr and directory=directory)
and (dirs.name <>'.')
and (dirs.name <>'..')
then such(verzeichnis+dirs.name+'');
if keypressed then begin
ch:=readkey;
if ch=#27 then abbruch:=true;
end;
findnext(dirs);
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);
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 . 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 . Das Unterprogramm suchdateien 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 . 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 . 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. Nach der Sicherstellung, ob das Suchergebnis nicht der Laufwerksname ist, wird es ausgegeben . Falls die Escape-Taste gedrückt wurde, wird das Flag abbruch gesetzt , was zum Abbruch der while-Schleife und der gesamten Suche führt. Anderenfalls wird die Suche mit dem Befehl FindNext fortgeführt . 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 . Die einzige lokale Variable ist dirs vom Typ SearchRec die für FindFirst und FindNext notwendig ist . Die Prozedur wird nur dann weiter ausgeführt, wenn das Flag abbruch nicht gesetzt ist , und es wird suchdateien mit dem übergebenen Verzeichnis als Parameter aufgerufen, um alle entsprechenden Dateien in diesem Verzeichnis anzuzeigen . Dann wird FindFirst so aufgerufen, daß alle Unterverzeichnisse des übergebenen Verzeichnisses gefunden werden . 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 . 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 . (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 . 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.
Ein weiteres riesiges Anwendungsgebiet der Rekursion ist die Darstellung von Fraktalen am Computer. Unter diesem Punkt sollen aber nicht wie in Punkt 3.1. einfach rekursive Folgen oder Funktionen dargestellt werden. Vielmehr geht es darum, geometrische Formen nach einer Transformation immer wiederholt darzustellen, sodaß sich ein sinnvolles Gebilde ergibt.
Der fraktale Baum ist ein recht einfaches, aber sehr schönes Beispiel. Der Baumstamm besteht aus der Grundform des Baumes, einem Fünfeck (Abbildung 1). Der Benützer definiert das Aussehen dieser Grundform durch die Eingabe des Abstandes der Punkte A und B, sowie zweier Faktoren V1 und V2, die das Verhältnis der beiden Höhen H1 und H2 zur Länge des Vektors AB angeben. Nach dem Zeichnen des Stammes werden rekursiv auf der linken und auf der rechten Seite der Spitze des Fünfecks zwei weitere geometrisch ähnliche gezeichnet. Als Grundlage der Berechnungen dienen die Länge des Vektors A'linksB' beziehungsweise A'rechtsB' sowie abermals die Verhältnisse V1 und V2. Aus den Angaben wird ein neues Fünfeck als Ast gezeichnet. Zuerst zeichnet das Programm die linke Seite, wobei es so lange fortfährt, bis die zuvor eingegebene Rekursionstiefe erreicht worden ist. Dann wird der Vorgang abgebrochen, und es werden, stufenweise vom äußersten Ast zurückgehend, auch die rechten Aste gezeichnet.
Abschließend soll noch die Berechnung der einzelnen Punkte erläutert werden: Auf den Vektor AB werden drei Normale aufgestellt , zwei davon in dessen Begrenzungspunkten mit der Länge AB * V1 und eine in dessen Halbierungspunkt mit der Länge AB * V2. Somit erhält man das gewünschte Fünfeck, dessen Aste nun durch einen zweifachen Selbstaufruf der Prozedur mit den Begrenzungspunkten der schrägen Seiten erzeugt werden. Das folgende Programm arbeitet nach dem eben erklärten Prinzip:
program rekursiver_baum;
uses crt, graph, tools07, grtools2;
var s : integer;
v1, v2 : real;
aa, bb : pointtype;
sstufe : integer;
verz : integer;
ch : char;
procedure baum(a, b : pointtype; stufe : integer);
var p : array[1..6] of pointtype;
xd, yd : real;
begin
if stufe>0 then begin
delay(verz);
xd:=b.x-a.x;
yd:=b.y-a.y;
p[1]:=a;
p[2].x:=a.x+round(v1*yd);
p[2].y:=a.y-round(v1*xd);
p[3].x:=a.x+round(xd/2)+round(v2*yd);
p[3].y:=a.y+round(yd/2)-round(v2*xd);
p[4].x:=b.x+round(v1*yd);
p[4].y:=b.y-round(v1*xd);
p[5]:=b;
p[6]:=a;
fillpoly(6,p);
dec(stufe);
baum(p[2],p[3],stufe);
baum(p[3],p[4],stufe);
end;
end;
begin
repeat
clrscr;
writeln(' REKURSIVER GRAFIKBAUM NACH PROF. HERBERT PAUKERT');
writeln(' programmiert von Stefan Krywult für seine Informatikfachbereichsarbeit 1998');
writeln;
write('Baumhöhe (z.B: 30) : ');
readln(s);
write('Seitliches Höhenverhältnis (z.B: 2) : ');
readln(v1);
write('mittleres Höhenverhältnis (z.B: 2.5) : ');
readln(v2);
write('Rekursionstiefe (am besten zwischen 3 und 12) :');
readln(sstufe);
write('Verzögerung: ');
readln(verz);
graphinit(0,0);
setbkcolor(0);
setcolor(15);
setfillstyle(3,7);
aa.x:=getmaxx div 2;
aa.y:=getmaxy-getmaxy div 4;
bb.x:=aa.x+s;
bb.y:=aa.y;
line(aa.x,aa.y,bb.x,bb.y);
baum(aa,bb,sstufe);
wt;
closegraph;
write('Nocheinmal ?');
ch:=upcase(readkey);
until ch='N';
clrscr;
end.
Zuerst werden die benötigten Variablen deklariert: In v1 und v2 werden die Verhältnisse der Höhen zur Grundlinie in Kommazahlen vom Typ Real gespeichert . Die Variablen aa und bb sind vom Typ PointType, in dem die beiden Koordinaten eines Punktes als ganzzahlige Integerwerte aufbewahrt werden . Sie werden beim Aufruf der rekursiven Prozedur vom Hauptprogramm aus als Startparameter übergeben. Die Variable sstufe bestimmt die Anzahl der Baumverästelungen , und mittels verz kann das Zeichnen des Baumes verzögert werden, um den Vorgang besser beobachten zu können .
Die rekursive Prozedur baum wird mit den Endpunkten der Grundkante des zu zeichnenden Fünfecks in a und b sowie der momentanen Rekursionstiefe in stufe als Parameter aufgerufen . Als lokale Variablen werden das Punktefeld p , in dem das Fünfeck für die Ausgabe gespeichert wird, und die Hilfsvariablen xd und yd vom Fließkommazahlen-Typ Real deklariert .
Zuerst wird in der Prozedur überprüft, ob stufe den Wert 0 hat und die Rekursion somit bereits beendet werden muß. Ist das nicht der Fall, kommen die weiteren Befehle der Prozedur zur Ausführung. Der Programmablauf wird zunächst um die in verz gespeicherte Anzahl von Millisekunden verzögert, dann wird der Vektor von a nach b berechnet und in den Hilfsvariablen xd und yd zwischengespeichert . Mit dessen Hilfe werden die Punkte des Fünfecks nach dem oben erklärten Prinzip berechnet und im Punktefeld p gespeichert , damit das Fünfeck mit dem Befehl FillPoly gezeichnet werden kann . Um das zu ermöglichen, ist es notwendig, einen sechsten Punkt mit den selben Koordinaten wie der erste zu speichern und die Anzahl der Punkte neben dem Punktefeld selbst als Parameter zu übergeben. Nun ist der Ast fertig gezeichnet, und die momentane Rekursionsstufe kann um 1 verringert werden . Und schließlich erfolgt ein zweifacher Selbstaufruf der Prozedur, wobei die Endpunkte der linken und der rechten Seite der Spitze und die neue, verminderte Rekursionstiefe als Argumente übergeben werden.
Im Hauptprogramm werden Baumhöhe, seitliches und mittleres Höhenverhältnis, Rekursionstiefe und die Länge der Verzögerungen zwischen den Zeichenschritten vom Benützer eingegeben . Nach der Initialisierung des Grafikmodus werden die Startpunkte des Baumes aa und bb im Bezug auf die Auflösung berechnet , und schließlich wird die Rekursion mit dem Aufruf der Prozedur baum mit diesen Punkten und der zuvor eingegebenen Rekursionstiefe gestartet .
Die Kochkurve, auch Schneeflockenkurve genannt, wird folgendermaßen gebildet (Abbildunge 2): Eine gegebene Strecke wird in drei gleich lange Teile geteilt. Der mittlere wird herausgelöscht, und es wird über diesem Abschnitt ein gleichseitiges Dreieck konnstruiert, dessen Basiskante auf dem mittleren Streckenstück liegt, die aber nicht gezeichnet wird. Das entstandene Gebilde ist ein Zug aus 4 gleich langen Strecken.
Der eben geschilderte Vorgang wird mit jedem dieser Streckenzüge wiederholt, sodaß nun eine Figur mit 16 gleich langen Strecken entsteht. Die Anzahl der Wiederholungen kann durch die Rekursionstiefe gesteuert werden. Folgendes Programm zeichnet eine Kochkurve:
program koch;
uses crt,graph,tools07,grtools2;
var rektief : integer; i,j,modus : integer;gr,verz : integer; a,b : pointtype;
verzf : real;
procedure frakt(p1,p2:pointtype; rt:integer; f:real);
var p : array[1..6] of tpoint; v : tpoint;
inti : integer;
begin
if (rt=0) or keypressed then exit;
v.x:=(p2.x-p1.x) div 3;
v.y:=(p2.y-p1.y) div 3;
p[1]:=p1;
p[2].x:=p[1].x+v.x;
p[2].y:=p[1].y+v.y;
p[3].x:=p[1].x+round(v.x*3/2 + f*v.y*sqrt(3)/2);
p[3].y:=p[1].y+round(v.y*3/2 - f*v.x*sqrt(3)/2);
p[4].x:=p[1].x+2*v.x;
p[4].y:=p[1].y+2*v.y;
p[5]:=p2;
p[6]:=p1;
if (modus=1) or (rt=1) then begin
line(p[1].x,p[1].y,p[2].x,p[2].y);
line(p[2].x,p[2].y,p[3].x,p[3].y);
line(p[3].x,p[3].y,p[4].x,p[4].y);
line(p[4].x,p[4].y,p[5].x,p[5].y);
delay(verz);
end;
dec(rt);
for inti :=1 to 4 do frakt(p[inti],p[inti+1],rt,f);
end;
begin
clrscr;
writeln(' Programm zum rekursiven Zeichnen der Kochkurve');
writeln(' geschrieben von Stefan Krywult im Rahmen seiner Fachbereichsarbeit ''98');
writeln(' frei nach einer Vorlage aus dem Skriptum 'FRAKTALE STRUKTUREN' ');
writeln;
repeat
write('Bitte geben Sie die Rekursionstiefe ein (4/6/7 empf.):');
readln(rektief);
until rektief>=1;
repeat
write('Bitte geben Sie die Verzögerung ein (333/100/10 empf.):');
readln(verz);
until rektief>=0;
write('Bitte geben Sie den Verzerrungsfaktor ein:');
readln(verzf);
write('Bitte geben Sie den Modus ein (1=alle Linien darstellen):');
readln(modus);
clrscr;
graphinit(0,0);
setcolor(1);
cleardevice;
setcolor(15);
a.x:=mmx div 8;
a.y:=mmy div 2;
b.x:=mmx - a.x;
b.y:=mmy - a.y;
frakt(a, b, rektief, verzf);
wt;
closegraph;
clrscr;
end.
Die wichtigsten Variablen in diesem Programm sind rektief und verz , in denen die vom Benutzer eingegebene Rekursionstiefe bzw. die Verzögerung des Darstellungsprozesses gespeichert wird. In den Variablen a und b vom Typ PointType werden die Endpunkte der ursprünglichen Geraden gespeichert , und verzf speichert einen Verzerrungsfaktor für das Zeichnen der Kurve .
Das Herzstück des Programms, die rekursive Prozedur fakt, berechnet nach dem oben erklärten Verfahren über eine bestimmte Strecke, deren Start- und Endkoordinaten in p1 und p2 übergeben werden, den vierteiligen Streckenzug . Auch ein Verzerrungsfaktor f und die momentane Rekursionstiefe werden der Prozedur übergeben. In der Hilfsvariablen p, die als ein Feld von Punkten deklariert ist, wird der Streckenzug zwischengespeichert . In der PointType-Variable v wird ein Drittel der übergebenen Strecke als Vektor gespeichert, dieser dient als Grundlage für die weiteren Berechnungen . Die Befehle der Prozedur werden aber nur dann ausgeführt, wenn die gewünschte Rekursionstiefe noch nicht erreicht, d.h. rt größer 0 ist und keine Taste gedrückt wurde . Nach dem Aufstellen des Vektors v folgt die Berechnung der einzelnen Punkte . Der erste besitzt die selben Koordinaten wie der übergebene Startpunkt der Strecke, der letzte die selben wie deren Endpunkt. Den zweiten und den vorletzten Punkt des Streckenzuges erhält man durch die Addition von v bzw. dem Doppelten von v zum ersten Punkt. Der mittlere Punkt wird errechnet, indem eine Normale mit der Länge v 3/2 durch den Mittelpunkt der gegebenen Strecke (p1+v*3/2) aufgestellt wird.
Hat der Benutzer 1 als Zeichenmodus eingegeben, wird der Streckenzug bei jedem Prozeduraufruf gezeichnet, sonst nur beim letzten (rt=1) . Nach dem Verringern der momentanen Rekursionstiefe rt um 1 erfolgt in einer Schleife ein vierfacher Selbstaufruf, bei dem die Koordinaten je eines der vier Streckenstücke als Parameter übergeben werden. .
Das Hauptprogramm beschränkt sich auf die Eingabe der Rekursionstiefe, der Verzögerung zwischen den Darstellungsschritten und des Verzerrungsfaktors . Danach wird der Grafikmodus initialisiert , eine bildfüllende Strecke in Abhängigkeit zur Auflösung errechnet . Schließlich wird die rekursive Prozedur frakt mit den entsprechenden Parametern aufgerufen .
Nach dem Zeichnen der Kochkurve wartet das Programm auf einen Tastendruck und schaltet zurück in den Textmodus .
Das Sierpinsky Dreieck entsteht, wenn die Halbierungspunkte der drei Seiten eines gleichseitigen Dreiecks so mit einander verbunden werden, daß vier Dreiecke entstehen. Mit den drei äußeren Dreiecken verfährt man dann nach dem selben Prinzip. Der ganze Vorgang wird so lange fortgesetzt, bis die gewünschte Rekursionstiefe erreicht ist (siehe Abbildung 3).
program sierpins;
uses crt,graph,tools07, grtools2;
var rektief : integer;
gr,verz : integer;
i,j,farbe : integer;
procedure frakt(rt,p1x,p1y,p2x,p2y,p3x,p3y:integer);
begin
if not keypressed then begin
if rt>1 then begin
frakt(rt-1,(p1x+p3x) div 2,(p1y+p3y) div 2,(p1x+p2x) div 2,(p1y+p2y) div 2,p1x,p1y);
frakt(rt-1,(p1x+p2x) div 2,(p1y+p2y) div 2,(p2x+p3x) div 2,(p2y+p3y) div 2,p2x,p2y);
frakt(rt-1,(p2x+p3x) div 2,(p2y+p3y) div 2,(p1x+p3x) div 2,(p1y+p3y) div 2,p3x,p3y);
end;
if farbe=1 then setcolor(rt mod 8+8);
delay(verz);
line(p1x,p1y,p2x,p2y);
line(p2x,p2y,p3x,p3y);
line(p3x,p3y,p1x,p1y);
end;
end;
begin
clrscr;
writeln(' Programm zum rekursiven Zeichnen der SIERPINSKY-DREIECKE');
writeln(' geschrieben von Stefan Krywult im Rahmen seiner Fachbereichsarbeit ''98');
writeln;
write('Bitte geben Sie die Rekursionstiefe ein (6/7 empf.):');
readln(rektief);
write('Bitte geben Sie die Verzögerung ein: (100/10 empf.):');
readln(verz);
write('Farbdarstellung ? (1=Farbe) :');
readln(farbe);
clrscr;
graphinit(0,0);
cleardevice;
setcolor(mmc);
frakt(rektief,0,0,mmx,0,mmx div 2,mmy);
wt;
closegraph;
clrscr;
end.
Als globale Variablen werden wieder rektief und verz zum Speichern der eingegeben Rekursionstiefe und der Verzögerung verwendet. Die Variable farbe ist ein Flag, in dem festgehalten wird, ob der Benützer eine Darstellung mit verschiedenen Farben wünscht . Die rekursive Prozedur frakt benötigt als Parameter die momentane Rekursionstiefe rt und die Koordinaten der Eckpunkte des Dreiecks . Die Deklaration lokaler Variablen ist diesmal nicht notwendig. Auch die Befehle dieser Prozedur werden nur dann ausgeführt, wenn keine Taste gedrückt wurde , was einen sofortigen Abbruch des Zeichenvorganges durch einen Tastendruck ermöglicht. Ist die gewünschte Rekursionstiefe noch nicht erreicht und rt daher größer als 1, ruft sich die Prozedur dreimal selbst auf, wobei die um 1 verringerte Rekursionstiefe und die Eckpunkte der nach dem oben genannten Schema berechneten Dreiecke übergeben werden . Ist das Flag farbe auf 1 gesetzt, wird die Zeichenfarbe in Abhängigkeit zur Rekursionstiefe neu gesetzt , wodurch erkennbar ist, welche Dreiecke im selben Rekursionsschritt gezeichnet wurden. Nach einer Verzögerung um die in verz eingegeben Anzahl an Millisekunden wird ein Dreieck entsprechend der übergebenen Koordinaten gezeichnet . Während die Bildschirmausgabe bei den beiden vorigen Programmen im aufsteigenden Ast der Rekursion stattfand, wird sie hier erst im absteigenden Rekursionsast vollführt, was zur Folge hat, daß nicht zuerst die großen und dann die kleinen Dreiecke, sondern zuerst die kleinen und dann die größeren gezeichnet werden.
Im Hauptprogramm wird der Benutzer gebeten, die Rekursionstiefe rektief, den Verzögerungsfaktor verz und das Farbflag farb einzugeben . Nach der Initialisierung des Grafikmodus wird die Prozedur frakt mit der Rekursionstiefe und den Koordinaten eines bildschirmfüllenden Dreiecks als Parameter aufgerufen . Das Farbflag farb ist global deklariert und somit im gesamten Programm zugänglich. Da es sich auch während der Rekursion nicht verändert, muß es nicht als Parameter übergeben werden. Nach dem Zeichnen der Dreiecke wartet das Programm auf einen Tastendruck und schaltet danach wieder in den Textmodus. Damit endet das Programm.
program rekursion01;
uses crt;
var i : integer;
procedure zaehl(von:integer);
begin
write(von,' ');
if von>0 then zaehl(von-1);
write(von,' ');
end;
begin
clrscr;
write('Rekursionstiefe: ');
readln(i);
zaehl(i);
readln;
clrscr;
end.
program rekursion01tx;
uses crt;
var i : integer;
f : text;
procedure zaehl(von:integer);
begin
writeln(f,'von: Wert:',von,' Adresse:',seg(von),':',ofs(von),' Stackpointer: ',sptr);
if von>0 then zaehl(von-1);
writeln(f,'von: Wert:',von,' Adresse:',seg(von),':',ofs(von),' Stackpointer: ',sptr);
end;
begin
assign(f,'rekprot.txt');
clrscr;
write(' Rekursionstiefe: ');
readln(i);
rewrite(f);
clrscr;
writeln(f,'Vor dem Prozeduraufruf: Stacksegment: ',sseg,' Stackpointer: ',sptr);
writeln(f);
zaehl(i);
writeln(f);
writeln(f,'Nach dem Prozeduraufruf: Stacksegment: ',sseg,' Stackpointer: ',sptr);
writeln('Datei rekprot.txt geschrieben');
close(f);
readln;
clrscr;
end.
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.
program ackermann;
uses crt, tools07;
var a, b : integer;
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;
begin
clrscr;
writeln(' PROGRAMM ZUM BERECHNEN DER ACKERMANNFUNKTION');
writeln(' geschrieben von Stefan Krywult für seine Informatikfachbereichsarbeit ''98');
writeln;
write('Bitte ersten Parameter eingeben (m<4) : ');
readln(a);
write('Bitte zweiten Parameter eingeben (n<10) : ');
readln(b);
writeln;
writeln('ack(',a,',',b,') = ',ack(a,b));
writeln;
writeln('Weiter mit Tastendruck');
wt;
clrscr;
end.
program GGT_Berechnung;
uses crt,tools07;
var a, b : longint;
function ggt(z1, z2 :longint): longint;
begin
if z2=0 then ggt:=z1 else ggt:=ggt(z2, z1 mod z2);
end;
begin
clrscr;
writeln(' PROGRAMM ZUM BERECHNEN DES GRÖSSTEN GEMEINSAMEN TEILERS');
writeln(' ZWEIER ZAHLEN NACH EUKLID');
writeln(' geschrieben von Stefan Krywult für seine Informatikfachbereichsarbeit ''98');
writeln;
write('Bitte erste Zahl eingeben (z1) : ');
readln(a);
write('Bitte zweite Zahl eingeben (z2) : ');
readln(b);
writeln;
writeln('ggt(',a,',',b,') = ',ggt(a,b));
writeln;
writeln('Weiter mit Tastendruck');
wt;
clrscr;
end.
program sorter;
uses crt,tools07,dos;
type bereich = array[1..16000] of integer;
var feld : bereich;
original : bereich;
anz : integer;
k,j : longint;
h,m,s,hs : word;
z1,z2,z3,z4 : longint;
procedure qsort(var fel:bereich;vo,bi:integer);
procedure sort(von,bis:integer);
var h,l,r,d: integer;
begin
inc(k);
l:=von;
r:=bis;
h:=fel[(r+l) div 2];
repeat
while (fel[l]<h) do inc(l);
while (fel[r]>h) do dec(r);
if l<=r then begin
d:=fel[l];
fel[l]:=fel[r];
fel[r]:=d;
inc(l);
dec(r);
inc(j);
end;
until l>=r;
if von<r then sort(von,r);
if bis>l then sort(l,bis);
end;
begin
k:=0;
j:=0;
sort(vo,bi);
end;
procedure eingabe;
var ze,zi : integer;
begin
writeln;
repeat
writeln('Anzahl der zu sortierenden Zahlen ( 1 < z <= 16000): ');
readln(ze);
until (ze>1) and (ze<=16000);
for zi:=1 to ze do original[zi]:=random(10000);
writeln;
writeln('Eingabe beendet.');
anz:=ze;
end;
procedure ausgabe;
var ze : integer;
begin
for ze:=1 to anz do begin
write(feld[ze]:8);
if ze mod 10 = 0 then delay(2);
end;
end;
procedure msort(var fel:bereich;vo,bi:integer);
var l1,l2,dummy : integer;
begin
for l1:=vo to bi-1 do begin
for l2:=l1+1 to bi do begin
if fel[l1]>fel[l2] then begin
inc(j);
dummy:=fel[l1];
fel[l1]:=fel[l2];
fel[l2]:=dummy;
end;
end;
end;
end;
begin
randomize;
clrscr;
writeln(' Programm zum Testen der QICKSORT-Routine');
writeln(' geschrieben von Stefan Krywult im Rahmen seiner Fachbereichsarbeit ''98');
writeln;
writeln('Sortieren mit MINIMUMSORT:');
eingabe;
writeln;
writeln('Es wurden ',anz,' Elemente eingegeben !');
feld:=original;
writeln;
writeln('Unsortierte Ausgabe erfolgt nach Tastendruck');
wt;
ausgabe;
writeln;
writeln('Sortieren mit MINIMUMSORT beginnt bei Tastendruck ');
wt;
clrscr;
j:=0;
k:=1;
writeln('Sortiervorgang mit MINIMUMSORT läuft');
gettime(h,m,s,hs);
z1:=hs+s*100+m*6000+360000*h;
msort(feld,1,anz);
gettime(h,m,s,hs);
z2:=hs+s*100+m*6000+360000*h;
z1:=z2-z1;
writeln;
writeln('Sortieren beendet.');
writeln('Es erfolgten ',k,' Prozedur-Aufrufe und ',j,' Vertauschungsoperationen.');
write('Benötigte Zeit: ');
write(z1 div 360000);
z1:=z1-(z1 div 360000)*360000;
write(':',z1 div 6000);
z1:=z1-(z1 div 6000)*6000;
write(':',z1 div 100);
write(':',z1 mod 100);
writeln;
writeln('Sortierte Ausgabe erfolgt nach Tastendruck');
wt;
ausgabe;
writeln;
writeln('Weiter mit Taste');
wt;
clrscr;
writeln(' Programm zum Testen der QICKSORT-Routine');
writeln(' geschrieben von Stefan Krywult in Turbo Pascal 7.0');
writeln;
writeln('Sortieren mit QUICKSORT:');
feld:=original;
writeln;
writeln('Es wurden ',anz,' Elemente eingegeben !');
writeln;
writeln('Unsortierte Ausgabe erfolgt nach Tastendruck');
wt;
ausgabe;
writeln;
writeln('Sortieren mit QUICKSORT beginnt bei Tastendruck');
wt;
clrscr;
k:=0;
j:=0;
writeln('Sortieren mit QUICKSORT läuft');
gettime(h,m,s,hs);
z3:=hs+s*100+m*6000+360000*h;
qsort(feld,1,anz);
gettime(h,m,s,hs);
z4:=hs+s*100+m*6000+360000*h;
z3:=z4-z3;
writeln;
writeln('Sortieren beendet.');
writeln('Es erfolgten ',k,' Prozedur-Aufrufe und ',j,' Vertauschungsoperationen.');
write('Benötigte Zeit: ');
write(z3 div 360000);
z3:=z3-(z3 div 360000)*360000;
write(':',z3 div 6000);
z3:=z3-(z3 div 6000)*6000;
write(':',z3 div 100);
write(':',z3 mod 100);
writeln;
writeln('Sortierte Ausgabe erfolgt nach Tastendruck');
wt;
ausgabe;
writeln;
writeln('Programm beendet.');
writeln('Weiter mit Taste');
wt;
clrscr;
end.
program Tuerme_von_Hanoi;
uses crt, tools07;
var i,j,k : integer;
schanz : integer;
schritte : integer;
procedure turm(anz,von,uber,nach:integer);
begin
if anz=1 then begin
inc(schritte);
writeln(schritte:6,'.Schritt: Von ',von,' nach ', nach,'.');
if schritte mod 16 = 0 then begin
write('Weiter mit Taste');
wt;
clrscr;
end;
end
else
begin
turm(anz-1,von,nach,uber);
inc(schritte);
writeln(schritte:6,'.Schritt: Von ',von,' nach ', nach,'.');
if schritte mod 16 = 0 then begin
write('Weiter mit Taste');
wt;
clrscr;
end;
turm(anz-1,uber,von,nach);
end;
end;
procedure bildaufbau;
begin
clrscr;
textbackground(0);
textcolor(15);
writeln(' DIE TÜRME VON HANOI');
writeln(' ====================');
writeln;
writeln(' geschrieben von Stefan Krywult für seine Informatikfachbereichsarbeit ''97/''98');
writeln;
writeln;
end;
begin
bildaufbau;
window(2,6,78,24);
color(15,1);
clrscr;
window(4,7,76,23);
repeat
write('Bitte geben Sie die Anzahl der zu verwendenden Scheiben ( Z>0 !) ein: ');
readln(schanz);
until schanz>0;
clrscr;
turm(schanz,1,2,3);
wt;
window(1,1,80,25);
color(7,0);
clrscr;
end.
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),
(2,2,0,0,0,0,2,0,0,0,0,0,0,2,0,2,2,0,2,2),
gefunden : boolean = false;
var lab : feld;
procedure zeigelab;
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);
var a,b : integer;
begin
gotoxy(x*2-1,y);
textcolor(14);
write(#219,#219);
delay(333);
if not gefunden then begin
case lab[x,y] of
3: begin
gefunden:=true;
zeigelab;
end;
2:begin
gotoxy(x*2-1,y);
textcolor(6);
write(#219,#219);;
end;
1:begin
gotoxy(x*2-1,y);
textcolor(4);
write(#219,#219);;
end;
0: begin
lab[x,y]:=1;
zeigelab;
if not gefunden then suchweg(x-1,y);
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;
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.
program labyrinth_alle;
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),
var lab : feld;
losungen : array[1..20] of feld;
lanz, i : integer;
schritte : integer;
lschritte : array[1..20] of integer;
min : integer;
procedure zeigelab;
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
textcolor(10);
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);
var a,b : integer;
begin
case lab[x,y] of
3: begin
inc(lanz);
if lanz <= 20 then begin
losungen[lanz]:=lab;
lschritte[lanz]:=schritte;
if schritte<lschritte[min] then min:=lanz;
end;
end;
2:;
1:;
0: begin
lab[x,y]:=1;
inc(schritte);
suchweg(x-1,y);
suchweg(x+1,y);
suchweg(x,y+1);
suchweg(x,y-1);
dec(schritte);
lab[x,y]:=0;
end;
end;
end;
begin
clrscr;
textcolor(15);
lanz:=0;
min:=1;
writeln(' Programm zum Suchen eines Ausweges aus einem Labyrith');
window(20,3,70,25);
lab:=labnorm;
zeigelab;
writeln('Bitte Enter drücken, um ALLE Auswege zu zeigen');
readln;
clrscr;
writeln('Suche läuft');
suchweg(10,10);
clrscr;
writeln('Suche beendet.');
writeln('Es wurden ',lanz,' verschiedene Auswege gefunden.');
writeln('Der kürzeste ist ',lschritte[min],' Schritte lang.');
writeln;
write('Weiter mit einer Taste');
wt;
for i:= 1 to lanz do begin
lab:=losungen[i];
zeigelab;
writeln(lschritte[i], ' Schritte bis zum Ausgang.');
if i=min then writeln('Dies ist der küzeste Ausweg.');
write('Weiter mit einer Taste');
wt;
clrscr;
end;
window(1,1,80,25);
clrscr;
end.
program weg;
uses crt, tools05;
const ortanz = 7;
type Tortnetz = array[1..ortanz,1..ortanz] of integer;
const ortnetz : Tortnetz = (( 0, 43, 0,12, 0, 54, 0), ( 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;
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);
var k : integer;
begin
weg:=weg+chr(48+ort);
if ort=ziel then begin
writeln(weg);
inc(gefunden);
if gefunden mod 10 = 0 then begin
writeln;
write('Weiter mit irgendeiner Taste');
wt;
clrscr;
end;
if (lang<min) or (min=0) then begin
min:=lang;
kweg:=weg;
end;
end
else
begin
for k:=1 to ortanz do
if (ortnetz[ort,k]>0) and (pos(chr(48+k),weg)=0) then
begin
lang:=lang+ortnetz[ort,k];
gehezu(k);
lang:=lang-ortnetz[ort,k];
end;
end;
weg:=copy(weg,1,length(weg)-1);
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.
program acht_damen;
program acht_damen;
uses crt, tools07;
type Tbrett=array[1..8,1..8] of byte;
var start : Tbrett;
i,ii,verz : integer;
danz, lanz : integer;
gefunden : boolean;
procedure zeigbrett(br:Tbrett);
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);
var ax,ay,b : integer;
test : tbrett;
begin
if (verz >0) and not gefunden then begin
gotoxy(1,1);
zeigbrett(brett);
delay(verz);
end;
if (danz=8) and not gefunden then begin
clrscr;
zeigbrett(brett);
gefunden:=true;
writeln(#7);
wt;
end
else if not gefunden then begin
for ax:=1 to 8 do begin
ay:=danz+1;
if brett[ax,ay]=0 then begin
test:=brett;
test[ax,ay]:=2;
inc(danz);
for b:=1 to 8 do begin
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);
dec(danz);
end;
end;
end;
end;
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): ');
readln(verz);
clrscr;
writeln('Suche läuft');
for i:=1 to 8 do for ii:=1 to 8 do start[i,ii]:=0;
stell_dame(start);
window(1,1,80,25);
clrscr;
end.
program rekfsuch;
uses crt,dos,tools07;
const abbruch : boolean = false;
var anz : integer;
s : string;
ch : char;
suchstring : string;
suchpfad : string;
procedure ausgabe(erg : string; a:byte);
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);
var files : SearchRec;
begin
if not abbruch then begin
FindFirst(verzeichnis+suchstring,anyfile,files);
while (doserror=0) and not abbruch do begin
if ((files.attr and VolumeID)<>VolumeID) then ausgabe(verzeichnis+files.name, files.attr);
if keypressed then begin
ch:=readkey;
if ch=#27 then abbruch:=true;
end;
findnext(files);
end;
end;
end;
procedure such(verzeichnis:string);
var dirs : SearchRec;
begin
if not abbruch then begin
suchdateien(verzeichnis);
FindFirst(verzeichnis+'*.*',directory,dirs);
while (doserror=0) and not abbruch do begin
if (dirs.attr and directory=directory)
and (dirs.name <>'.')
and (dirs.name <>'..')
then such(verzeichnis+dirs.name+'');
if keypressed then begin
ch:=readkey;
if ch=#27 then abbruch:=true;
end;
findnext(dirs);
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);
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.
program rekursiver_baum;
uses crt, graph, tools07, grtools2;
var s : integer;
v1, v2 : real;
aa, bb : pointtype;
sstufe : integer;
verz : integer;
ch : char;
procedure baum(a, b : pointtype; stufe : integer);
var p : array[1..6] of pointtype;
xd, yd : real;
begin
if stufe>0 then begin
delay(verz);
xd:=b.x-a.x;
yd:=b.y-a.y;
p[1]:=a;
p[2].x:=a.x+round(v1*yd);
p[2].y:=a.y-round(v1*xd);
p[3].x:=a.x+round(xd/2)+round(v2*yd);
p[3].y:=a.y+round(yd/2)-round(v2*xd);
p[4].x:=b.x+round(v1*yd);
p[4].y:=b.y-round(v1*xd);
p[5]:=b;
p[6]:=a;
fillpoly(6,p);
dec(stufe);
baum(p[2],p[3],stufe);
baum(p[3],p[4],stufe);
end;
end;
begin
repeat
clrscr;
writeln(' REKURSIVER GRAFIKBAUM NACH PROF. HERBERT PAUKERT');
writeln(' programmiert von Stefan Krywult für seine Informatikfachbereichsarbeit 1998');
writeln;
write('Baumhöhe (z.B: 30) : ');
readln(s);
write('Seitliches Höhenverhältnis (z.B: 2) : ');
readln(v1);
write('mittleres Höhenverhältnis (z.B: 2.5) : ');
readln(v2);
write('Rekursionstiefe (am besten zwischen 3 und 12) :');
readln(sstufe);
write('Verzögerung: ');
readln(verz);
graphinit(0,0);
setbkcolor(0);
setcolor(15);
setfillstyle(3,7);
aa.x:=getmaxx div 2;
aa.y:=getmaxy-getmaxy div 4;
bb.x:=aa.x+s;
bb.y:=aa.y;
line(aa.x,aa.y,bb.x,bb.y);
baum(aa,bb,sstufe);
wt;
closegraph;
write('Nocheinmal ?');
ch:=upcase(readkey);
until ch='N';
clrscr;
end.
program koch;
uses crt,graph,tools07,grtools2;
type Tpoint=record
x:integer;
y:integer;
end;
var rektief : integer;
i,j,modus : integer;
gr,verz : integer;
a,b : tpoint;
verzf : real;
procedure frakt(p1,p2:Tpoint; rt:integer; f:real);
var p : array[1..6] of tpoint;
v : tpoint;
inti : integer;
begin
if (rt=0) or keypressed then exit;
v.x:=(p2.x-p1.x) div 3;
v.y:=(p2.y-p1.y) div 3;
p[1]:=p1;
p[2].x:=p[1].x+v.x;
p[2].y:=p[1].y+v.y;
p[3].x:=p[1].x+round(v.x*3/2 + f*v.y*sqrt(3)/2);
p[3].y:=p[1].y+round(v.y*3/2 - f*v.x*sqrt(3)/2);
p[4].x:=p[1].x+2*v.x;
p[4].y:=p[1].y+2*v.y;
p[5]:=p2;
p[6]:=p1;
if (modus=1) or (rt=1) then begin
line(p[1].x,p[1].y,p[2].x,p[2].y);
line(p[2].x,p[2].y,p[3].x,p[3].y);
line(p[3].x,p[3].y,p[4].x,p[4].y);
line(p[4].x,p[4].y,p[5].x,p[5].y);
delay(verz);
end;
dec(rt);
for inti :=1 to 4 do frakt(p[inti],p[inti+1],rt,f);
end;
begin
clrscr;
writeln(' Programm zum rekursiven Zeichnen der Kochkurve');
writeln(' geschrieben von Stefan Krywult im Rahmen seiner Fachbereichsarbeit ''98');
writeln(' frei nach einer Vorlage aus dem Skriptum 'FRAKTALE STRUKTUREN' ');
writeln;
repeat
write('Bitte geben Sie die Rekursionstiefe ein (4/6/7 empf.):');
readln(rektief);
until rektief>=1;
repeat
write('Bitte geben Sie die Verzögerung ein (333/100/10 empf.):');
readln(verz);
until rektief>=0;
write('Bitte geben Sie den Verzerrungsfaktor ein:');
readln(verzf);
write('Bitte geben Sie den Modus ein (1=alle Linien darstellen):');
readln(modus);
clrscr;
graphinit(0,0);
setcolor(1);
cleardevice;
setcolor(15);
a.x:=mmx div 8;
a.y:=mmy div 2;
b.x:=mmx - a.x;
b.y:=mmy - a.y;
frakt(a, b, rektief, verzf);
wt;
closegraph;
clrscr;
end.
program sierpins;
uses crt,graph,tools07, grtools2;
var rektief : integer;
gr,verz : integer;
i,j,farbe : integer;
procedure frakt(rt,p1x,p1y,p2x,p2y,p3x,p3y:integer);
begin
if not keypressed then begin
if rt>1 then begin
frakt(rt-1,(p1x+p3x) div 2,(p1y+p3y) div 2,(p1x+p2x) div 2,(p1y+p2y) div 2,p1x,p1y);
frakt(rt-1,(p1x+p2x) div 2,(p1y+p2y) div 2,(p2x+p3x) div 2,(p2y+p3y) div 2,p2x,p2y);
frakt(rt-1,(p2x+p3x) div 2,(p2y+p3y) div 2,(p1x+p3x) div 2,(p1y+p3y) div 2,p3x,p3y);
end;
if farbe=1 then setcolor(rt mod 8+8);
delay(verz);
line(p1x,p1y,p2x,p2y);
line(p2x,p2y,p3x,p3y);
line(p3x,p3y,p1x,p1y);
end;
end;
begin
clrscr;
writeln(' Programm zum rekursiven Zeichnen der SIERPINSKY-DREIECKE');
writeln(' geschrieben von Stefan Krywult im Rahmen seiner Fachbereichsarbeit ''98');
writeln;
write('Bitte geben Sie die Rekursionstiefe ein (6/7 empf.):');
readln(rektief);
write('Bitte geben Sie die Verzögerung ein: (100/10 empf.):');
readln(verz);
write('Farbdarstellung ? (1=Farbe) :');
readln(farbe);
clrscr;
graphinit(0,0);
cleardevice;
setcolor(mmc);
frakt(rektief,0,0,mmx,0,mmx div 2,mmy);
wt;
closegraph;
clrscr;
end.
Die Ideen und das Wissen zu den in dieser Arbeit angegebenen Programmen stammt aus folgender Literatur:
Bartenschlager, Georg / Kopp, Petra, Rekursive Programmierung für Pascal, Delphi und C/C++, Franzis-Verlag, Feldkirch, 1997
Paukert, Herbert, Programmieren in Pascal, Programmieren für Einsteiger und Fortgeschrittene, MANZ Verlag, Wien, 1995
Paukert, Herbert, Skriptum: Fraktale Strukturen
Rädle, Klaus, Programmieren lernen, Eine Einführung mit Struktogrammen und Programmbeispielen in Turbo Pascal, Carl Hanser Verlag, München/Wien, 1995
Reichel, Hans-Christian / Müller, Robert / Laub, Josef / Hanisch, Günter, Lehrbuch der Mathematik, Hölder-Pichler-Tempsky Verlag, Wien, 3.Auflage, 1992, 6.Band
Ich erkläre eidesstattlich, daß ich die vorliegende Arbeit selbst geschrieben und keine außer den angegebenen Hilfsmitteln verwendet habe.
Besprechung des Themas der Fachbereichsarbeit, Festlegung des Inhalts und Formulierung des Titels - gemeinsames Ausfüllen des Antrages auf die Fachbereichsarbeit
Konkretisierung des Inhalts, Aufstellen der wesentlichen Punkte, die in der Fachbereichsarbeit behandelt werden sollen
Begutachtung der gesammelten Literatur und Planung des ungefähren Aufbaus der Arbeit
Besprechung des Schemas von Funktions- bzw. Prozeduraufrufen und des Ablaufes von Rekursionen unter Turbo-Pascal anhand des Buches "Programmieren in Pascal" (siehe Literaturverzeichnis)
Aussuchen von rekursiven Programmen, die eventuell in die Arbeit aufgenommen werden sollen
Kontrolle der bisher geschriebenen Programme, Erläuterung der Theorie der ggT-Berechnung nach Euklid und des Spieles 'Die Türme von Hanoi' durch Herrn Prof. Paukert
Besprechung von Backtracking- Algorithmen unter der Verwendung des Programmes "Laby.pas" (siehe "Programmieren in Pascal", Seite 288f.), Tips zum Schreiben der Programme zum Finden des kürzesten Weges in einem Straßennetz und zum Lösen des 8-Damen-Problems, Vorschlag von Anderungen an "laby.pas", um den Suchvorgang für den Zuschauer besser verständlich zu machen. Erklärung des Quicksort-Algorithmus durch Herrn Prof. Paukert
Kontrolle der bisher geschriebenen Programme. Aussuchen von Beispielprogrammen für die rekursive Entwicklung von Grafiken sowie die Besprechung der für diese Programme notwendigen mathematischen Berechnungen. Zusammenstellen einer Auswahl aus verschiedenen rekursiven Folgen für den ersten Teil der Arbeit
Erläuterung der Turbo-Pascal-Befehle "FindFirst" und "FindNext", Wiederholung des Aufbaus des Dateisystems von MS-DOS und anderer Grundlagen für das Programm "rekfsuch.pas"
Hinweise zum Komplettieren der Arbeit und zum Abändern der Programme, sodaß deren Arbeitsvorgang für den Benutzer besser nachvollziehbar wird. Auswahl einiger Programme, die während der Präsentation der Arbeit im Rahmen der mündlichen Prüfung vorgeführt werden sollen.
Abgabe der Arbeit
Haupt | Fügen Sie Referat | Kontakt | Impressum | Nutzungsbedingungen
