Teilermenge ermitteln

[alzaimar]

Jeder rekursive Algorithmus ist nichts anderes als eine Schleife + Stack als Zwischenspeicher (vereinfacht ausgedrückt), also kannst Du dein Ackermännchen doch einfach mit Arrays lösen, oder nicht?

Aber ob es iterative Algorithmen gibt, die sich partout nicht rekusriv formulieren lassen....?

[BlackJack]

Zitat:

Zitat von alzaimar

Jeder rekursive Algorithmus ist nichts anderes als eine Schleife + Stack als Zwischenspeicher (vereinfacht ausgedrückt), also kannst Du dein Ackermännchen doch einfach mit Arrays lösen, oder nicht?

naja das ist sehr stark vereinfacht, ich wüsste z.b. nicht, wie man so eine doppelte Rekursion a la
f := f(f(x)) lösen sollte.

edit:
ich bin mir ziemlich sicher dass es so ist wie ich es eingangs gesagt hatte:
Iterativ -> Rekursiv: immer möglich
Rekursiv -> Iterativ: manchmal, aber nicht immer möglich

[alzaimar]

Zitat:

Zitat von BlackJack

Iterativ -> Rekursiv: immer möglich
Rekursiv -> Iterativ: manchmal, aber nicht immer möglich

Jedes Rekursive Programm lässt sich nunmal mit einer Schleife und einem Stack iterativ formulieren. Warum? Weil es der Kompiler doch genauso macht. Der einzige klitzekleine Unterschied ist der (rekursive) Aufruf der Funktion selbst, aber das ist doch nichts Anderes als eine Verzweigung. Und das widerum ist im Endeffekt nichts anderes als eine Schleife.

Und wenn dich das nicht überzeugt, dann denk dir einfach, das die CPU per se iterativ arbeitet und jeden noch so rekursiven Mist als einfache Abfolge von Sprüngen (ok, ein bisserl gerechnet wird auch) abarbeitet. Insofern ist es -ich sags nochmal- banal. Aber: Sich für jede rekursive Funktion eine entsprechende Iterative auszudenken, ist schwierig, da stimme ich Dir zu. Von der Seite aus gesehen würde ich das auch anzweifeln.

Dein Beispiel f:= f(f(x)) ist auch rekursiv nicht lösbar (-> Endlosschleife).

[Phistev]

Dann liefer doch mal eine iterative Lösung für folgendes Problem:

Du hast eine Menge mit n Elementen und möchtest alle Kombinationen mit 1,2,3,...,n-1 Elementen erhalten

Rekursiv geht relativ einfach, iterativ (fast) unmöglich, oder?

[marabu]

Hi folks,

im Informatikstudium lernt man, dass Iteration und Rekursion äquivalente Lösungsverfahren sind. Das eine lässt sich stets in das andere umwandeln. Während der Weg Iteration nach Rekursion trivial ist (z.B. tail recursion) ist der umgekehrte Weg mitunter haarig, unsinnig, sinnverschleiernd - aber auf jeden Fall möglich.

Grüße vom marabu

[dizzy]

Gibt es denn mittlerweile eine rein iterative Lösung zun den "Türmen von Hanoi"? Zu meiner Schulzeit jedenfalls war imho noch keine bekannt. (Zumindest meinte dies unserer (entgegen der landläufigen Üblichkeit) relativ gute Info-Lehrer...)

[marabu]

Hi dizzy,

die Towers of Hanoi sind ein relativ altes Kinderspielzeug. Ich habe jetzt keine Geschichtsforschung betrieben, aber möchte trotzdem behaupten, dass jede rekursive Implementierung des Lösungsalgorithmus jünger ist als die iterative, deren Existenz die Informatiker postulieren.

Mir persönlich reicht die Gewissheit, dass es geht, aber wer genügend Zeit für zweckfreies Tun erübrigen kann, der kann sich ja an der Implementierung der iterativen Lösung versuchen. Der Algorithmus wird z.B. von Eric Lippert beschrieben.

Grüße vom marabu

[ichbins]

Ist doch ganz einfach:

Delphi-Quellcode:

for i:=1 to zahl do
  if zahl mod i=0 then
  begin
    {Wenn du die Teiler in einem Array of integer brauchtst:}
    setlength(teilerarray,length(teilerarray)+1);
    teilerarray[length(teilerarray)]:=i;
    {oder als Liste:}
    teilerliste.add(i);
  end;

[Khabarakh]

Informatiker wollen's aber nicht einfach, sondern schnell :wink: . Und in diesem Fall ist eine Primfaktorzerlegung sicher schneller.

PS: Du solltest dein Array zur Performancesteigerung lieber um 172% vergrößern *g* .

[alzaimar]

Zitat:

Zitat von Phistev

Dann liefer doch mal eine iterative Lösung für folgendes Problem:

Du hast eine Menge mit n Elementen und möchtest alle Kombinationen mit 1,2,3,...,n-1 Elementen erhalten

Rekursiv geht relativ einfach, iterativ (fast) unmöglich, oder?

Nö:

Delphi-Quellcode:

Procedure Permutations (aString : String);
Var
  d : Array Of Integer;
  g, j, i, n, v : Integer;
  p,c : String;

Begin
  n := Length (aString);
  setlength (d,n+1);
  d[1] := 1;
  For i := 2 to n do
    d[i] := i * d[i-1];
  For i := 0 to d[n]-1 do begin
    c := aString;
    p := '';
    v := i;
    for j:=n-1 downto 1 do begin
      g := j - (v div d[j]) + 1;
      p := p + c[g];
      delete (c, g, 1);
      v := v mod d[j];
      End;
    p := p + c;
    memo1.lines.Add (p);
    End;
End;

Nachtrag:
Man kann den Algorithmus auch so umschreiben, das man direkt die N.te Permutation ausrechnet:

Delphi-Quellcode:

Function NthPermutation (aString : String; aCount : Integer) : String;
Var
  d : Array Of Integer;
  g, i, n : Integer;

Begin
  n := Length (aString);
  setlength (d, n);
  d[1] := 1;
  For i := 2 to n - 1 do d[i] := i * d[i-1];
  Result := '';
  for i := n-1 downto 1 do begin
    g := (aCount div d[i]) + 1;
    Result  := Result  + aString[g];
    delete (aString, g, 1);
    aCount := aCount mod d[i];
    End;
  Result := Result  + aString;
End;

Nicht sonderlich rekursiv, aber trotzdem schnell. Basiert im Übrigen auf der Inversen und Graycodes.