Tino
 
Beiträge: 9839
Erhaltene Danke: 45
Windows 8.1
Delphi XE4
|
Verfasst: Di 11.06.02 10:57
Algorithmen
Autor: Tomac
E-Mail: tomac@gmx.at
Quelle: www.coder-area.de
ALGORITHMEN -- TEIL 1
Dies soll eine kleine Einführung werden, wie man mit Algorithmen arbeiten kann. Nun zu den verschiedenen Arten von Algorithmen:
- ITERATIVE Algorithmen
Iterative Algorithmen dienen dazu, Probleme mit Hilfe einer Schleifenkonstruktion zu lösen. Die Lösung erhält man dadurch, indem eine Schleife etliche Male durchalufen wurd, wobei es sich aber entweder um eine von den Durchläufen (=Iterationen) her endliche Schleife oder um eine Schleife mit einer Abbruchbedingung handeln kann. Man kann also sagen, dass alle Probleme mit eine Schleife gelöst werden können, allerdings ist das in manchen Fällen relativ umständlich. Und aus diesem Grund verwendet man andere Methoden.
Fibonacci-Zahlen
Die Fibonacci-Zahlen sind eine Zahlenkette, bei er das nächste Element jeweils aus der Summe der beiden Vorgänger- Elemente berechnet wird.
Die Fibonacci-Zahlen sind ein gutes Beispiel für eine Schleifenfunktion, weil man gut sehen kann, wie Probleme auf verschiedene Arten angegangen werden können.
Die Reihe sieht also so aus:
  Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
| x1 = 0
x2 = 1
x3 = x1+x2 = 0+1 = 1
x4 = x2+x3 = 1+1 = 2
x5 = x3+x4 = 1+2 = 3
x6 = x4+x5 = 3+2 = 5
x7 = x5+x6 = 5+3 = 8 |
Die resultierende Reihe sieht folgendermaßen aus:
Delphi-Quelltext
1:
| 0-1-1-2-3-5-8-13-21-34-55-89-144-... |
Unser Problem ist nun, die ersten 20 Zahlen dieser Kette darzustellen. Die ersten beiden Glieder (0, 1) sind von vornherein vorgegeben. So ist es ganz einfach, die Fibonacci-Zahlen mittels einer Schleife zu berechnen:
Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
| procedure FibonacciIter(Anzahl: integer);
var
Fib: array of integer;
j: integer;
Begin
SetLength(Fib, Anzahl);
Fib[0]:=0;
Fib[1]:=1;
For j:= 2 to Anzahl-1 do
Fib[j]:=Fib[j-1]+Fib[j-2];
End; |
So wird das Problem also iterativ gelöst. Diese Lösung ist im Vergleich zur rekursiven (Wird weiter unten besprochen) Lösung eindeutig die bessere.
- REKURSIVE Algorithmen
Man kann dieses Problem auch anders angehen, nämlich indem man eine rekursive Lösung programmiert. Rekursiv bedeutet, die Funktion wird solange aufgerufen, bis der Endwert erreicht ist. Rekursive Funktionen rufen sich selbst auf, es werden innerhalb der Funktion oder Prozedur Werte berechnet, die dann der Prozedur beim Aufruf übergeben
werden. Da die Werte bei jedem Aufruf dieser Prozedur/ Funktion verändert werden, wird irgendwann ein Wert erreicht, der dem endgültigen Ergebnis entspricht - Die rekursive Schleife wird verlassen!
Doch es gibt dabei eine Gefahr, auf die man achten muss. Und zwar die Abbruchbedingung. Es muss wirklich sicher sein, dass sie auch wirklich aufgerufen wird, ansonsten gerät man in eine Endlosschleife, und ihr wisst ja sicher alle, was das bedeuten würde.
Um noch mal auf die Fibonacci- Zahlen zurückzukommen, unser Problem ist nun, diese Zahlen in eine rekursive Form zu bringen. Mathematisch sieht das ganze ja so aus:
Delphi-Quelltext
1:
| f(x) = f(x-1) + f(x-2) mit f(1) = 0 und f(2) = 1 |
Die rekursive Funktion sieht daher so aus:
Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
| Function TForm1.Fiboncci(Index: integer): integer;
Begin
if Index < 2 then
result:=Index else
result:=Fibonacci(Index-1)+Fibonacci(Index-2);
End; |
ALGORITHMEN -- TEIL 2
- BACKTRACKING
Backtracking- Algorithmen sind eine völlig andere Art von Algorithmen.
Sie arbeiten nach einem interessanten Prinzip, welches vergleichbar mit der Lernfähigkeit von Affen ist *g*, sie arbeiten mit Versuch und Irrtum .
Dennoch ist es eine einfache Möglichkeit, alle möglichen vorkommenden Aspekte eines Problems durchzuspielen.
Jetzt wird's interessant. Ich gehe jetzt das Dame-Problem an.
Das Dame-Problem
Zuerst eine Kurze Beschreibung: Es geht darum, auf einem Schachbrett acht Damen so zu platzieren, dass keine Dame eine andere bedroht. Nebenbei kann man auch noch herausfinden, wie viele Lösungsmöglichkeiten es git.
Wenn ihr euch das mal durch den Kopf gehen lasst, werdet ihr merken, dass es doch eigentlich relativ einfach zu lösen ist. Denn wenn keine Dame die andere bedrohen darf, dürfen sie nicht übereinander oder nebeneinander stehen. Das Schachbrett hat acht Spalten, es darf also nur je eine Dame in einer Spalte sein, dann muss überprüft werden, ob sie eine andere bedroht (In diesem Fall wird sie eine Zeile weitergezogen) und dann muss die nächste kontrolliert werden. Ist aber eine Dame schon ganz unten am Schachbrett, ohne dass es eine Position ohne Bedrohung gab, muss die vorherige Dame eins weiter gezogen und konntrolliert werden.
So muss es irgendwann zu einer Lösung kommen, wie schon erwähnt durch Versuch und Irrtum.
So, fürs erste genug erklärt. Hier die Funktion, weiter unten werde ich sie dann genauer Besprechen:
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
| TYPE
TDameArray = ARRAY[1..8] OF Byte;
Procedure TForm1.Dame;
Var
Damen: TDameArray;
i: integer;
act_Dame: Byte;
Begin
For i:= 1 to 8 do
Damen[i.] := 0;
act_Dame := 1; Loesung := 0; REPEAT;
REPEAT;
inc(Damen[Act_Dame]);
IF Damen[Act_Dame]<9 THEN
BEGIN;
IF NoCollision(Damen,Act_Dame) THEN
IF Act_Dame<8 THEN
inc(Act_Dame)
ELSE
inc(Loesung); END;
UNTIL Damen[Act_Dame]>8; Damen[Act_Dame] := 0;
Dec(Act_Dame);
UNTIL (Act_Dame=0); END; |
Ich möchte nun zuerst auf die Funktionsweise der Funktion eingehen. Zuerst werden alle Werte auf einen Grundwert gesetzt. Die erste Dame, die bearbeitet wird, ist Dame Nummer 1. Die Anzahl der Lösungen wird auf 0 gesetzt, ebenso die Position aller Damen.
Der Algorithmus selbst arbeitet folgendermaßen, wie oben schon kurz erklärt: Es wird mit der ersten Dame begonnen und sie wird auf das erste Feld ihrer Spalte gesetzt. Wenn es keine Bedrohung gibt, wird die nächste Dame genommen und auf ein Feld gesetzt. Nun wird ihr Feld so lange erhöht, bis keine Bedrohung mehr vorhanden ist oder sie auf dem letzten Feld landet. Gibt es keine Bedrohung einer Dame, wird natürlich wieder die
nächste genommen...
Ist eine Dame auf dem letzten Feld angekommen und es gab in allen Positionen eine Bedrohung, wird bei der Vorgängerdame eine Position verändert. In diesem Fall wird die Position unserer Dame wieder auf Null gesetzt, damit sie von oben anfangen kann. Die Position der Vorgängerdame wird so lange um 1 erhöht, bis es keine Kollision mehr gibt oder sie auf dem letzten Feld angekommen ist. Gibt es keine Kollision, wird zur nächsten Dame gesprungen und sie wird ein Feld weitergesetzt. Gibt es eine Kollision, naja, dann beginnt das ganze von vorne!
Am einfachsten zu verstehen ist das ganze, wenn ihr es zu Hause auf einem echten Schachbrett ausprobiert.
ALGORITHMEN -- TEIL 3
Das ist nun der letzte Teil dieses "Kurses". Es geht jetzt nur noch um die Kontrolle der Kollisionen bei der Programmierung des Dame Problems. Wer möchte, dem kann ich ein Beispielprogramm schicken!
Die Kontrolle der Kollisionen
Zuerst mal der Code:
Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
| FUNCTION TForm1.collision(Damen: TDameArray; Anz: Integer): boolean;
var
i:integer;
BEGIN
Result:=true;
if Anz>1 then begin
For i:=Anz-1 downto 1 do
if (Damen[i.]=Damen[Anz]) then
result:=false;
end;
if Result and (Anz>1) then begin
for i:=Anz-1 downto 1 do
if abs(Damen[i.]-Damen[Anz])= abs(i-anz) then
result:=false;
end;
end; |
Eigentlich sollte diese Funktion für die meisten kein Problem darstellen. Übergeben wird das Array mit den Positionen der Damen und die Variable Anz, die angibt, wieviele Damen kontrolliert werden müssen.
In der Funktion wird kontrolliert, ob es eine Kollision in horizontaler oder diagonaler Richtung gibt. Vertikal braucht man nicht zu prüfen, da ja sowieso jede Dame in einer eigenen Spalte sitzt. Im Falle einer Kollision gibt die Funktion false zurück, wenn es keine gibt, true.
|
