Rekursion zu Iteration umwandeln

14.02.2008, 12:14

flawZ

Rekursion zu Iteration umwandeln

Hallo allerseits!

Und zwar habe ich große Probleme bei Aufgaben des folgenden Typs:

Seien f, g Funktionen von N --> N mit

f(0) = 1; f(1) = 2; h(1) = 2;

f(n + 1) = 2 * h(n + 1) + f(n - 1);
h(n + 1) = h(n) + 3 * f(n)

Nun soll das iterative Verfahren iter zur Berechnung von f(n) aufstellen.

Als Lösung muss folgendes herauskommen:

Setze a = f(n - 1); b = f(n - 2); c = h(n - 1);

Beginne mit f(n) = iter(n,2,1,2).

iter(n,a,b,c) = iter(n - 1, 6a + 2c + b, a, 3a + c);
iter(0,a,b,c) = b

Nun stehe ich hier total auf dem Schlauch, weiß nicht, warum und wie
ich was wähle, wie ich hier überhaupt vorgehe.

Es wäre echt prima, wenn mir jemand wenigstens den Ansatz bei der
Vorgehensweise bei solchen Aufgaben nennen könnte, denn ich
komm hier echt nicht weiter..

Vielen Dank schonmal!

14.02.2008, 12:53

Auf diesen Beitrag antworten »

ed209

Mit deiner Lösung kann ich momentan überhaupt nichts anfangen, mir ist die SChreibweise völlig unbekannt.

Ich würde Dir vorschlagen erstmal aufzuschreiben, wie du vorgehen würdest, wenn du die nächsten 3 f(n) per Hand ausrechnen würdest und dann mal guckst, ob Du ein System entdeckst.

Gruß,
ED

14.02.2008, 15:14

Auf diesen Beitrag antworten »

Tobias

Die Lösung steht da doch schon. Du musst sie nur noch abschreiben:

code:
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15:	a = 2 b = 1 c = 2 Wiederhole n mal: tmp_a = 6a + 2c + b b = a c = 3*a + c a = tmp_a Gib b zurück.

Die Idee dazu ist folgende:

Zuerst einmal setzen wir die Rekursionsvorschriften in f(n) ein:

$[latex]f(n) = 2h(n) + f(n-2) = 2\left(h(n-1) + 3f(n-1)\right) + f(n-2) = 2h(n-1) + 6f(n-1) + f(n-2)[/latex]$

Wenn wir also f(n-2), f(n-1) und h(n-1) kennen würden, könnten wir f(n) ganz einfach mit obiger Formel berechnen. Die Formel nennen wir mal $[latex]\phi(a, b, c) = 6a + b + 2c[/latex]$ .

$[latex]f(n) = \phi\big(f(n-1), f(n-2), h(n-1) \big) = \phi(a, b, c)[/latex]$

$[latex]f(n+1) = \phi\big(f(n), f(n-1), h(n) \big) = \phi\big(\phi(a, b, c), a, 3a+c \big)[/latex]$

Der Trick ist nun, die Rekursion durch sukkzessivem Berechnen von f(2), f(3), ... aufzulösen:

$[latex]f(2) = \phi\big(f(1), f(0), h(1) \big) = \phi(2, 1, 2) = 12 + 1 + 4 = 17[/latex]$
$[latex]f(3) = \phi\big(f(2), f(1), h(2) \big) = \phi(\phi(2, 1, 2), 2, 3f(1) + h(1)) = ...[/latex]$

Neue Frage »

Antworten »

Rekursion zu Iteration umwandeln

Verwandte Themen