3. stack dynamisch vergrößern

stack dynamisch vergrößern

  • T

    äh.. danke für die info mein ich

    0
  • T

    hab mitlerweile einen anderen algorithmus im internet gefunden. Und die Rekursion war wirklich nicht zu lösen. Aber vielen dank für die Mühe

    0
  • P

    OT: *gruebel* gabs nichtmal irgendeinen Beweis, dass jede Rekusrion auch iterativ loesbar ist?

    0
  • C

    pumuckl schrieb:

    OT: *gruebel* gabs nichtmal irgendeinen Beweis, dass jede Rekusrion auch iterativ loesbar ist?

    Ja, die allgemeine Lösung läuft darauf hinaus, den Callstack der rekursiven Aufrufe in den Algorithmus zu integrieren 😉

    @Tom: Was war denn das für ein Algorithmus?

    0
  • A

    pumuckl schrieb:

    OT: *gruebel* gabs nichtmal irgendeinen Beweis, dass jede Rekusrion auch iterativ loesbar ist?

    Mag sein. Aber ich löse ehrlich gesagt rekursive Aufgaben besser rekursiv. Das geht Gehirnmäßig einfacher, als wenn man eine rekursive Aufgabe in iterativ umdenken muß.

    Aber der Beweis würde mich schon interessieren, keine Frage.

    0
  • ?

    was gibts da viel zu beweisen. bei jedem rekursiven funktionsaufruf werden lokale variablen und parameter auf den (call)stack gelegt. das macht man einfach selber, also (while)schleife und bei jedem durchgang die benötigten parameter auf einen eigenen stack.

    0
  • T

    @CStoll

    Das war ein Algorithmus zur Berechnung einer convexen Hülle für eine Menge von Messwerten. Das Problem war folgender Code:

    protected static void quicksort(int lo, int hi)
    {
        int i=lo, j=hi;
        Point q=p[(lo+hi)/2];
        while (i<=j)
        {
            while (p[i].isLess(q)) i++;
            while (q.isLess(p[j])) j--;
            if (i<=j) exchange(i++, j--);
        }
        if (lo<j) quicksort(lo, j);
        if (i<hi) quicksort(i, hi);
    }

    Mir ist für diesen Fall leider keine Lösung mit einer Schleife eingefallen.
    Und recursiver Code kommt nicht in Frage, weil die Anzahl der Messwerte nicht begrenzt ist. Können also auch viele Tausend sein.

    mfg Tom

    0
  • B

    Zum Glück ist Quicksort recht populär, da hat sich jemand schon Gedanken zu gemacht 🙂

    //Quicksort iterativ   (im Vergleich zur rekursiven Funktion ganz schön kompliziert)
procedure sortieren(var aa:array of real;von,bis:integer);
   var p,i,j:integer;
begin
  p:=bis;
  while p> 1 do Begin
    p:=p div 2;
    i:=von;
    repeat
      if aa[i+p]<aa[i] then BEgin
        tausche(aa[i],aa[i+p]);
        j:=i;
        while j-p>=von do BEGin
          if aa[j]<aa[j-p] then bEgin
             tausche(aa[j],aa[j-p]);
             j:=pred(j)
          eNd  else j:=0;
        END;
      ENd;
      i:=succ(i)
    until i+p>bis
  End;
end;

    Ist in Delphi und einfach von hier kopiert, vielleicht gehts ja.. Aber du musst wirklich viele Datensätze haben, ich hatte bei Quicksort noch nie einen Stack-Überlauf 😕

    0
  • H

    Es geht jetzt nicht ernsthaft ums sortieren ... 😮

    0
  • A

    Öhm, also ich hab jetzt eher an eine Baumstruktur gedacht, die ich durchlaufen muß oder so. Bei sowas kommt bei mir Rekursion höchstens zum Einsatz. Ach ja, zum Sortieren, benutze ich die Standardlib. 😉

    0
  • T

    Nein Stop. So wie ich das sehe ist das nicht der quicksort zum auf- oder absteigenden sortieren von Zahlen. Dieser Code hier sortiert glaub irgendwie anders. Der Sortiert irgendwie die Werte relativ zu irgend einem anderen Wert.

    0
  • P

    TomTom85 schrieb:

    Nein Stop. So wie ich das sehe ist das nicht der quicksort zum auf- oder absteigenden sortieren von Zahlen. Dieser Code hier sortiert glaub irgendwie anders. Der Sortiert irgendwie die Werte relativ zu irgend einem anderen Wert.

    Stimmt, das ist einfach quicksort im Sinne von Point::isLess() - was sich im Grunde aufs gleiche rauskommt. Im Klartext: Wo normalerweise ein "if (a < b)" steht, steht hier ein "if a.isLess(b)" - vom Sinn her ists genau das selbe wie Zahlen sortieren.

    0
Anmelden zum Antworten