Entwickler-Ecke
Delphi Language (Object-Pascal) / CLX - Rekursion abrechen
Stauch - Mo 04.11.02 12:58
Titel: Rekursion abrechen
Ich nutze eine Rekursive Prozedur um einen Eintrag zu finden. Wie kann ich die suche komplett abbrechen, wenn der gesuchte Eintrag gefunden wurde?
wwerner - Mo 04.11.02 13:39
Lies dir deine Frage noch mal durch. Sie ist so allgemein gehalten, das es darauf nur die Antwort geben kann: In dem du ein Endeflag hast
Stauch - Mo 04.11.02 13:45
Was ist ein EndFlag?
wwerner - Mo 04.11.02 13:49
Irgend eine Variable oder eine Bedingung, die sagt, das die Rek. beendet werden soll
Stauch - Mo 04.11.02 14:38
Alles Klar. Ich hatte gehofft, sowas ähnliches wie exit verwenden zu können, um damit alle Aufrufbäume zu beenden.
Mein Pseudocode sieht so aus
Quelltext
1:
2:
3:
4:
5:
| if (not gefunden) then
if (wort=suchwort) then gefunden:=true
else
if (not gefunden) and (...) then rek. aufruf1
if (not gefunden) and (...) then rek. aufruf2 |
Ich möchte die sache halt etwas beschleunigen
MfG C.
Anonymous - Mo 04.11.02 17:47
Z.B. so:
Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
| var
Form1: TForm1;
i: Word = 0;
implementation
{$R *.DFM}
procedure Test;
begin
if i > 10 then Exit;
Inc(i);
Test;
end;
procedure TForm1.Button1Click(Sender: TObject);
begin
Test;
ShowMessage(IntToStr( i ));
end; |
Für jeden rekursiven Aufruf muß auch ein mal ein Exit stehen. Wenn also die Prozedur 10 mal aufgerufen wird, dann wird auch weitere 10 mal if i > 10 then aufgerufen (zusammen also 20mal).
Klabautermann - Mo 04.11.02 18:09
Hallo,
ich finde es übersichtlicher, wenn man die Abbruchbedingung direckt mit dem Rekursiven Aufruf verbindet.
Popov's procedure sähe dann so aus:
Quelltext
1:
2:
3:
4:
| if (i < 10) then begin
Inc(i);
Test(i);
end; |
Gruß
Klabautermann
Stauch - Di 05.11.02 10:52
Öhm, ja ... bilde mir ein eure Beispiele zu verstehen, aber sehe nicht so richtig, wie mir das weiter hilft. Vielleicht doch mal der Code:
Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
| procedure check(wort:string;nr:integer);
begin
if (not gefunden) then
begin
if (wort=pwd) then begin
gefunden:=true;
showMessage(wort);
exit;
end
else begin
if (length(wort)< max) and (not gefunden) then check(wort+Mzeichen[0],0);
end;
if (nr<maxnr) and (not gefunden) then begin
wort[length(wort)]:=Mzeichen[nr+1];
check(wort,nr+1);
end;
end;
end; |
Dabei ist MZeichen ein Array of char (der Zeichenvorrat) und gefunden eine boolsche Variable.
Ich würde gern die Anzahl der Bedingungen verringern, um die Suchgeschwindigkeit zu erhöhen, aber die Rekursion soll auch sofort abbrechen, wenn das Suchwort gefunden wurde.
MfG C.
Udontknow - Do 07.11.02 12:02
Bringe einen weiteren Parameter Tiefe ins Spiel. Den übergibst du bei jedem Aufruf der Prozedur Check um 1 erhöht. Sobald er bspw. >10 ist, kannst du gefunden auf true setzen und exit aufrufen.
Quelltext
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:
| procedure check(wort:string;nr:integer;Tiefe:Integer=0);
begin
if Tiefe=10 then
begin
gefunden:=True;
exit;
end;
if (not gefunden) then
begin
if (wort=pwd) then begin
gefunden:=true;
showMessage(wort);
exit;
end
else begin
if (length(wort)< max) and (not gefunden) then check(wort+Mzeichen[0],0,Tiefe+1);
end;
if (nr<maxnr) and (not gefunden) then begin
wort[length(wort)]:=Mzeichen[nr+1];
check(wort,nr+1,Tiefe+1);
end;
end;
end; |
Cu,
Udontknow
Stauch - Do 07.11.02 14:50
So scheints zu gehen. Vielen Dank an alle :D
C.
Entwickler-Ecke.de based on phpBB
Copyright 2002 - 2011 by Tino Teuber, Copyright 2011 - 2024 by Christian Stelzmann Alle Rechte vorbehalten.
Alle Beiträge stammen von dritten Personen und dürfen geltendes Recht nicht verletzen.
Entwickler-Ecke und die zugehörigen Webseiten distanzieren sich ausdrücklich von Fremdinhalten jeglicher Art!