AGB  ·  Datenschutz  ·  Impressum  







Anmelden
Nützliche Links
Registrieren
Zurück Delphi-PRAXiS Programmierung allgemein Programmieren allgemein Theorie: Rekursive Funktion Abbrechen und Fortsetzen
Thema durchsuchen
Ansicht
Themen-Optionen

Theorie: Rekursive Funktion Abbrechen und Fortsetzen

Ein Thema von Meflin · begonnen am 23. Okt 2005 · letzter Beitrag vom 28. Okt 2005
Antwort Antwort
Seite 4 von 4   « Erste     234   
Benutzerbild von Meflin
Meflin

Registriert seit: 21. Aug 2003
4.856 Beiträge
 
#31

Re: Theorie: Rekursive Funktion Abbrechen und Fortsetzen

  Alt 27. Okt 2005, 14:03
Zitat von alzaimar:
Ist der Algorithmus geheim? Vielleicht können wir ihn ja iterativ umformulieren?
nein: http://www.delphipraxis.net/internal...ct.php?t=62161

Delphi-Quellcode:
procedure BruteForceFunc(const init, str: string);
  var i: integer;
      npw: string;
  begin
    if slResult.Count >= BatchSize then begin
      if Assigned (KeyList) then KeyList.AddStrings(slResult);
      csThreadCounter.Enter;
      Progress := Progress + slResult.Count;
      csThreadCounter.Leave;
      slResult.Clear;
    end;

    for i := 1 to Length (str) do begin
      npw := init + str[i];
      if Length (npw) >= fStartLength then begin
        slResult.Add(npw);
        ThreadInfo[arrayID].Progress := ThreadInfo[arrayID].Progress + 1;
      end;
      if Length (npw) < fEndLength then BruteForceFunc (npw, str);
    end;
  end;
ist das herzstück

  Mit Zitat antworten Zitat
alzaimar
(Moderator)

Registriert seit: 6. Mai 2005
Ort: Berlin
4.956 Beiträge
 
Delphi 2007 Enterprise
 
#32

Re: Theorie: Rekursive Funktion Abbrechen und Fortsetzen

  Alt 27. Okt 2005, 14:38
Na, super, fast eine Endrekursion.
Einfach einen Stack, bestehend aus 2 Strings erzeugen (Ich hab das als TStringlist gemacht, nicht perfekt, reicht aber).

Am Anfang schiebst Du 'init' und 'str' auf rauf. Anstatt rekursiv aufzurufen, schiebst Du die Parameter, mit der Du dich sonst rekursiv aufrufen würdest, einfach auf den Stack. Ich gehe mal davon aus, das Du das Ergebnis des rekursiven Aufrufes in der For-Schleife nicht benötigst. Ich sehe auch einige globale Variablen, aber das checkst Du bestimmt selbst.

Delphi-Quellcode:
procedure IterativeBruteForceFunc(const init, str: string);
var i: integer;
    npw: string;
    StackedInit, StackedStr : TStringlist;

begin
  StackedInit := TStringList.Create;
  StackedStr := TStringlist.Create;
  StackedInit.Add (init);
  StackedStr.Add (Str);
  While StackedInit.Count > 0 do begin
(****************************************)
    Init := StackedInit [StackedInit.Count -1];
    Str := StackedStr[StackedStr.count - 1];
    StackedInit.Delete (StackedInit.Count - 1);
    StackedStr.Delete (StackedStr.Count - 1);
(****************************************)
    if slResult.Count >= BatchSize then begin
      if Assigned (KeyList) then KeyList.AddStrings(slResult);
      csThreadCounter.Enter;
      Progress := Progress + slResult.Count;
      csThreadCounter.Leave;
      slResult.Clear;
    end;

    for i := 1 to Length (str) do begin
      npw := init + str[i];
      if Length (npw) >= fStartLength then begin
        slResult.Add(npw);
        ThreadInfo[arrayID].Progress := ThreadInfo[arrayID].Progress + 1;
      end;
      if Length (npw) < fEndLength then Begin
(*****************************************)
        StackedInit.Add (Npw); // BruteForceFunc (npw, str);
        StackedStr.Add (Str);
(*****************************************)
      end;
    end;
  End;
End;
"Wenn ist das Nunstruck git und Slotermeyer? Ja! Beiherhund das Oder die Flipperwaldt gersput!"
(Monty Python "Joke Warefare")
  Mit Zitat antworten Zitat
dimo

Registriert seit: 28. Okt 2005
22 Beiträge
 
#33

Re: Theorie: Rekursive Funktion Abbrechen und Fortsetzen

  Alt 28. Okt 2005, 13:52
PS: Habe gerade gesehen, dass diesen Vorschlag schon existiert.

Der Prozeduraufruf wird mit Stack implementiert.
Dies kannst Du auch selber nachmachen - dafür steht die Klasse TStack zur Verfügung. Natürlich ist normalerweise eine rekursive Funktion kürzer und einfacher zu programieren.
Ein schematischer Beispiel, der alle Dateien rekursiv (d.h. auch in Unterverzeichnisse) anzeigt:
Delphi-Quellcode:
procedure recurse_dirs(path : string);
var   sr : TSearchRec;
begin
   if FindFirst(path+PathDelim+'*.*', faAnyFile, sr) = 0 then begin
      repeat
         if (sr.Attr and faDirectory) = faDirectory then begin
            if (sr.Name <> '.') and (sr.Name<>'..') then
               recurse_dirs(path+PathDelim+sr.Name);
         end else begin
            showmessage(path+PathDelim+sr.Name);
         end;
      until FindNext(sr) <> 0;
      FindClose(sr);
   end;
end;
Kann folgendermassen ohne Rekursion geändert werden:
Delphi-Quellcode:
procedure iterate_dirs(startpath : string);
var   sr : TSearchRec;
   stack : TStack;
   path : PAnsiChar;
   subdir : PAnsiChar;
begin
   stack:= TStack.Create;

   path:= StrAlloc(length(startpath)+1);
   StrPCopy(path, startpath);
   stack.Push(path);

   while stack.Count>0 do begin
      path:= stack.pop;
      if FindFirst(path+PathDelim+'*.*', faAnyFile, sr) = 0 then begin
         repeat
            if ((sr.Attr and faDirectory) = faDirectory) then begin
               if (sr.Name <> '.') and (sr.Name<>'..') then begin
                  subdir:= StrAlloc(Length(path+PathDelim+sr.Name)+1);
                  StrPCopy(subdir, (path+PathDelim+sr.Name));
                  stack.push(subdir);
               end;
            end else begin
               showmessage(path+PathDelim+sr.Name);
            end;
         until FindNext(sr) <> 0;
         FindClose(sr);
      end;
      StrDispose(path);
   end;
   stack.Free;
end;
Natürlich ist die Ausgabereihenfolge unterschiedlich, die ist aber bei vielen Aufgaben egal. Hört sich an wie Breiten vs. Tiefensuche Ist es auch dasselbe in dem Fall.

Zustand speichern in diesem Fall wäre einfach den Stack speichern... Das ist das Gute an dieser Methode.
Grüße,
Dimo
  Mit Zitat antworten Zitat
Antwort Antwort
Seite 4 von 4   « Erste     234   


Forumregeln

Es ist dir nicht erlaubt, neue Themen zu verfassen.
Es ist dir nicht erlaubt, auf Beiträge zu antworten.
Es ist dir nicht erlaubt, Anhänge hochzuladen.
Es ist dir nicht erlaubt, deine Beiträge zu bearbeiten.

BB-Code ist an.
Smileys sind an.
[IMG] Code ist an.
HTML-Code ist aus.
Trackbacks are an
Pingbacks are an
Refbacks are aus

Gehe zu:

Impressum · AGB · Datenschutz · Nach oben
Alle Zeitangaben in WEZ +1. Es ist jetzt 18:29 Uhr.
Powered by vBulletin® Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2023 by Daniel R. Wolf, 2024 by Thomas Breitkreuz