Informatiker Board | Theoretische Informatik | Rekursion zu Iteration umwandeln

Informatiker Board » Themengebiete » Theoretische Informatik » Rekursion zu Iteration umwandeln

» Hallo Gast [Anmelden|Registrieren]

Letzter Beitrag | Erster ungelesener Beitrag

Druckvorschau | An Freund senden | Thema zu Favoriten hinzufügen

Rekursion zu Iteration umwandeln

Autor

Beitrag

« Vorheriges Thema | Nächstes Thema »

flawZ
Grünschnabel

Dabei seit: 14.02.2008
Beiträge: 1

Rekursion zu Iteration umwandeln

Zitatantwort auf diesen Beitrag erstellen

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:14

Nehmen Sie flawZ in Ihre Freundesliste auf

ed209
Routinier

Dabei seit: 07.09.2006
Beiträge: 324

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 12:53

Nehmen Sie ed209 in Ihre Freundesliste auf

Tobias
Routinier

Dabei seit: 18.09.2006
Beiträge: 324

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]$

Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von Tobias: 14.02.2008 15:52.

14.02.2008 15:14

Nehmen Sie Tobias in Ihre Freundesliste auf

Baumstruktur | Brettstruktur

Informatiker Board » Themengebiete » Theoretische Informatik » Rekursion zu Iteration umwandeln