| Die letzten 3 Beiträge |
| 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 = 6*a + 2*c + 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]](http://www.matheboard.de/latex2png/latex2png.php?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))
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]](http://www.matheboard.de/latex2png/latex2png.php?\phi(a, b, c) = 6a + b + 2c) .
![[latex]f(n) = \phi\big(f(n-1), f(n-2), h(n-1) \big) = \phi(a, b, c)[/latex]](http://www.matheboard.de/latex2png/latex2png.php?f(n) = \phi\big(f(n-1), f(n-2), h(n-1) \big) = \phi(a, b, c))
![[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]](http://www.matheboard.de/latex2png/latex2png.php?f(n+1) = \phi\big(f(n), f(n-1), h(n) \big) = \phi\big(\phi(a, b, c), a, 3a+c \big))
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]](http://www.matheboard.de/latex2png/latex2png.php?f(2) = \phi\big(f(1), f(0), h(1) \big) = \phi(2, 1, 2) = 12 + 1 + 4 = 17)
![[latex]f(3) = \phi\big(f(2), f(1), h(2) \big) = \phi(\phi(2, 1, 2), 2, 3f(1) + h(1)) = ...[/latex]](http://www.matheboard.de/latex2png/latex2png.php?f(3) = \phi\big(f(2), f(1), h(2) \big) = \phi(\phi(2, 1, 2), 2, 3f(1) + h(1)) = ...) |
| 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 |
| 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! |
|
|
