Methoden Rekursive Methode in Iterative umschreiben

[DeutscheKartoffel]

Guten Abend,
da ich jetzt schon seit stunden dran sitze und es nicht hinkriege dachte ich mir ich hole mir hier mal Hilfe...
Ich muss eine Funktion TUDO-Zahl iterativ in einer Schleife verwirklichen die sich wie folgt definiert:


[CODE lang="java" title="Rekursiv"]public static long TUDOZahlen_Rekursiv(int n)
{
if (n <= 3 && n >= 0)
{
return n;
}
else
{
return TUDOZahlen_Rekursiv(n - 2) + TUDOZahlen_Rekursiv(n - 4);
}
}[/CODE]
Dies habe ich rekursiv hinbekommen, jedoch muss ich es iterativ umsetzen.
Würde mich über Hilfe freuen...

PS: Brauche die Funktion iterativ um sie damit leichter in asm schreiben zu können wegen der Logik also nicht zum c&p...

MFG
Kartoffel

 

[kneitzel]

Wie würdest du denn vorgehen, wenn du f(10) ausrechnen sollst? Da man selbst meist ein Problem Iterativ löst, ist die Chance sehr groß, dass du direkt eine Lösung dafür findest.

Ein anderer Ansatz, der immer geht, ist die iterative Abbildung des rekursiven Algorithmus. Das, was halt sonst durch Aufrufe auf dem Stack landet, landet dann auf einem dedizierten Stack. Das ist ein Vorgehen, das immer klappt aber den Ansatz würde ich in der Regel nicht verwenden.

 

[DeutscheKartoffel]

Danke mit deinen Ansatz hab ich es gelöst gekriegt war gar nicht so schwer

[CODE lang="java" title="Iterativ"] public static long TUDOZahlen_Iterativ(int n)
{
if (n <= 3 && n >= 0)
{
return n;
}
else
{
long[] Werte = new long[n+1]; //Wegen Null
Werte[0] = 0;
Werte[1] = 1;
Werte[2] = 2;
Werte[3] = 3;

for (int i = 4; i < n+1; i++)
{
Werte = Werte[i-2] + Werte[i-4];
}

return Werte[n];
}
}[/CODE]

 

[kneitzel]

Erst einmal ist das Schöne: ein richtigen Ansatz bezüglich der Aufgabe hatte ich gar nicht gegeben ... nur eine grobe Beschreibung der Herangehensweise.

Daher super, dass du es gelöst bekommen hast - zu 100% Deine Leistung!

Noch ein paar Gedanken, was man noch machen könnte:
Bei sehr großen n kann man darauf verzichten, alle Werte zu speichern. Du brauchst ja nur die letzten paar Werte zu merken. Also sowas wie f(n-1), f(n-2), f(n-3), f(n-4) (da java kein - im Bezeichner erlaubt: fn1 bis fn4)

Damit kannst du den nächsten Wert fn berechnen. Und dann schiebst du alle Werte einmal: fn4 = fn3, fn3 = fn2 und so weiter ... Und dann kannst du das nächste n berechnen.
Und dann braucht du natürlich den Zähler n um zu wissen, für welches n gerade im fn der Wert zu finden ist.

Deutlich weniger Speicherbedarf aber dafür mehr Operationen pro Element (halt das Verschieben kommt dazu).

Das aber nur als eine Alternative- deine Lösung ist korrekt und schneller ... dafür mit mehr Speicherverbrauch.