Rekursiv zu Iterativ?

Hallo WM,

die Formel steht schon da (2*berechne(i-1)-berechne(i-2)+1), Du musst nur alles von unten aufbauen. D.h. Du berechnest zuerst das, was für berechne(1) entstehen würde, dann darauf aufbauend berechne(2) usw bis Du bei berechne(i) angelangt bist.

Dafür benötigst Du Variablen, die das letzte ( berechne(i-1) ) und vorletzte ( berechne(i-2) ) Ergebnis speichern.

Mögliche Lösung:

public int berechne(int n){

int erg = 3;

int vorletztes=3;

for(int i = 3; i<=n; i++){

int ergneu = 2*erg - vorletztes + 1;

vorletztes = erg;

erg = ergneu;

}

return erg;

}

erg fungiert in der Zeile "int ergneu = 2*erg - vorletztes + 1;" als berechne(i-1), da es zu diesem Zeitpunkt noch das letzte Ergebnis aus dem vorherigen Schleifendurchlauf enthält. Das letzte Ergebnis ist bei der nächsten Berechnung natürlich das vorletzte Ergebnis, darum wird es anschließend in "vorletztes = erg;" gespeichert und mit "erg = ergneu" das eigentliche Ergebnis dieses Schleifendurchlaufs an erg übergeben.

Die Schleife selbst kann in diesem Fall erst bei i = 3 beginnen, weil alle berechne(i) für i<3 das Ergebnis 3 auswerfen sollen. Die Schleife kann also für i<3 übersprungen werden.

Grüße

Lösungsansatz:

Du schaust dir an, wie die Rekursion definiert ist, vorallem auf welche bereits berechneten Elemente sie aufbaut.

a[i] = 3, für i<3

a[i] = 2*a[i-1] - a[i-2] + 1, sonst

In diesem Fall sind das der Vorgänger und der Vorvorgänger von a[i]

Du brauchst also 2 zusätzliche Hilfsvariablen in denen du diese beiden zwischenspeicherst und in jedem Iterationsschritt um eine Stelle verschiebst.

public int berechne(int n)

{

int temp1 = 0; // = berechne(i-1)

int temp2 = 0; // = berechne(i-2)

int result = 0; // = berechne(i)

for (int i = 0; i <= n; i++)

{

// Zwischenergebnisse aus vorigem Iterationsschritt verschieben

temp2 = temp1;

temp1 = result;

// neues Ergebnis berechnen

if (i < 3) result = 3;

else result = 2 * temp1 - temp2 + 1;

}

return result;

}