Teilermenge ermitteln

[Nicolai1234]

Hallo,
in meinem aktuellen Projekt benötge ich die Teilermengen von Zahlen.
Also z. B. T9={1,3,9}

Klar kann ich diese mit einer Schleife errechnen; das finde ich aber nicht so schön bzw. Schleifen dauern bei großen Zahlen einfach zu lang...
Ich habe schon gesucht, aber nichts gefunden:
Gibt es ein rechnerisches Verfahren, um die Teilermengen bzw. deren Anzahl zu berechen?

Besonders die Anzahl ist mir wichtig.

Vielen Dank im voraus

[Phistev]

Bisher gibt es keine besseren Verfahren, ansonsten könnte RSA u. ä. einpacken, da die darauf basieren, dass man eine Zahl nur per Brute-Force faktorisieren (in die Teiler zerlegen) kann. Nützlich könnten hier Lookup-Tables oder Primfaktorzerlegung sein (dazu denk ich mir noch was aus).

[Nicolai1234]

Ich habe heute nochmal meinen Mathelehrer gefragt und er redete auch etwas über Primfaktorzerlegung.
Genaueres konnte er mir aber auch nicht sagen...

[Phistev]

Bei der PFZ zerlegt man eine Zahl in die Primfaktoren. Am Ende steht dann in etwa 12=2*2*3. Die Teiler der Zahl sind die Primzahlen selber und alle Produkte aus den Primzahlen. Die Produkte per Function auszurechnen, das ist das Interessante (Frage am Rande: Wie erhalte ich das erste Element eines Arrays, welches dann auch entfernt wird?)... Vorteil (oder auch nicht) der PFZ gegenüber der direkten Bestimmung der Teiler: Laufzeit sqrt(n)+Produktbildung gegen n/2

[Eichhoernchen]

wie wäre es mit Rekursion, so haben wir das in der Schule gemacht!

[BlackJack]

Zitat:

Zitat von Eichhoernchen

wie wäre es mit Rekursion, so haben wir das in der Schule gemacht!

naja, sagen wir so, jedes Iterativ lösbare Problem lässt sich auch rekursiv lösen, von daher: Ja. ;)

[CLRS530]

Das ist schonmal total falsch, du kannst jede rekursive Lösung iterativ machen (teilweise ziemlich umständlich, z. B. beim durchgehen der Ordner auf der Festplatte oder alle Wurzeln eines Trees).

Aber iterative Lösungen kannst du absolut nicht alle zu einer rekursiven machen.

[alzaimar]

Zitat:

Zitat von CLRS530

Das ist schonmal total falsch, du kannst jede rekursive Lösung iterativ machen (teilweise ziemlich umständlich, z. B. beim durchgehen der Ordner auf der Festplatte oder alle Wurzeln eines Trees).

Aber iterative Lösungen kannst du absolut nicht alle zu einer rekursiven machen.

Bitte zu letzter Aussage ein Beispiel.

[jfheins]

@CLRS530:

Delphi-Quellcode:

for i := 1 to 5 do
  maches (i);

=

Delphi-Quellcode:

procedure recurse (i: integer)
begin
  maches (i);
  if i < 5 then
    recurse (i + 1);
end;

recurse (1)

;)

[BlackJack]

Zitat:

Zitat von CLRS530

Das ist schonmal total falsch, du kannst jede rekursive Lösung iterativ machen (teilweise ziemlich umständlich, z. B. beim durchgehen der Ordner auf der Festplatte oder alle Wurzeln eines Trees).

Aber iterative Lösungen kannst du absolut nicht alle zu einer rekursiven machen.

Dann zeig mir bitte mal eine rein Iterative Variante der Ackermann-Funktion, das sollte deiner Meinung nach ja auf jeden Fall möglich sein.

Und wenn du schon dabei bist, dann zeig mir auch bitte eine Iterative Funktion, die sich nicht in eine Rekursion umwandeln lässt.

[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.

[Eichhoernchen]

da sagt man einmal rekusion und schon hat man ne Welle losgetreten!

Ich weiß zwar nicht warum, aber mein Info lehrer will fast immer das wir Probleme rekursiv lösen!

Gibt es einen Vorteil wenn man es über Wiederaufrufe macht?

[marabu]

Als Faustregel kann man formulieren: rekursiv definierte Probleme lassen sich über rekursive Algorithmen sehr elegant lösen, performanter ist in der Regel der iterative Algorithmus.

marabu

[BlackJack]

Zitat:

Zitat von alzaimar

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

naja war ja nur ein Beispiel, man muss da halt noch code mit abbruchkriterien drumrum schreiben.

@marabu: wieder was dazu gelehrnt. gibt es denn ein standardverfahren, wie man eine rekursive implementierung in eine iterative umwandelt?

[marabu]

Hi BlackJack,

ein einziges Standardverfahren kann es nicht geben, da die Rekursion selbst Varianten kennt - nicht jede Rekursion ist linear und selbst die linearen weisen nicht ausnahmslos eine tail recursion auf. Die Schematisierung des Transformationsprozesses interessiert die Informatiker auch heute noch, z.B. bei der Implementierung funktionaler Sprachen (Lisp, Hope, Miranda, Haskell).

Magst du einen kleinen Einblick? Klick

marabu

[negaH]

Jede rekursive Funktion wird und muß in eine iterative umwandelbar sein.
Es gibt aber iterative Funktionen die nicht rekursiv gelösst werden können.

Die rekursive Schreibweise ist nur eine andere Form eines iterativen Verfahrens. Der einzigste Unterschied liegt in der meist einfacheren Begreiflichkeit der rekursiven Verfahren für den Menschen.

Für ds oben angesprochene Problem der Kombinatorik hätte sich auch ein Blick in die CodeLib gelohnt. Dort findest du bestimmt einige Sourcen.

Gruß Hagen

[Robert Marquardt]

Zitat:

Zitat von 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...)

Ja es gibt.
http://de.wikipedia.org/wiki/T%C3%BCrme_von_Hanoi

[marabu]

Hallo Hagen,

Zitat:

Zitat von negaH

Es gibt aber iterative Funktionen die nicht rekursiv gelösst werden können.

mit diesem Satz widersprichst du einigen Koryphäen auf dem Gebiet der Informatik. Prof. David Gries (damals Cornell University) schreibt in seinem Buch "The Science of Programming" (Chapter 18 - Using Iteration Instead of Recursion):

Zitat:

... in theory at least, any recursive program can be written iteratively (and vice versa), ...

Spricht aus deinen Worten eine innere Überzeugung (wie "die Erde ist eine Scheibe") oder ist deine Aussage missverständlich, weil ungenau? Zielst du vielleicht auf die von mir angedeutete Grundhaltung, dass nicht jeder Versuch, die "Korrektheit" eines durch vollständige Induktion untermauerten Algorithmus gegen einen kleinen prozentualen Performanzgewinn durch iterative Implementierung einzutauschen, vernünftig ist?

Freundliche Grüße vom marabu


@BlackJack: In dem von mir hier zitierten Buch versucht der Autor einige Vorgehensweisen zur Schematisierung der Transformation zu vermitteln.

[BlackJack]

Zitat:

Zitat von marabu

@BlackJack: In dem von mir hier zitierten Buch versucht der Autor einige Vorgehensweisen zur Schematisierung der Transformation zu vermitteln.

naja so sehr wollte ich mich in die materie eigentlich nicht einarbeiten, aber das pdf von dir war schon echt interessant (auch wenn mir der C++ -(und Haskel?) Code manchmal einige schwierigkeiten bereitet hat). :D