Induktionsformel schaffen < Folgen und Reihen < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 01:37 Di 03.11.2009 | | Autor: | laco |
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
Hallo,
die Anzahl der rekursiven Aufrufe bei den Tribonaccizahlen soll mit Induktion bewiesen werden.
Folge der Aufrufe sieht wie folgt aus für n>3:
3, 6, 9, 12 etc. Also: 3*(n-3)
Wie geht man am besten vor, wenn man das mit Induktion beweisen will?
für n= 4 (ist das erste Glied der Folge) ist es wahr.
Wie genau setze ich jetzt aber (n+1)?
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 02:40 Di 03.11.2009 | | Autor: | Fulla |
Hallo laco,
kannst du die Aufgabenstellung noch genauer angeben? Wie sind die Tribonacci-Zahlen definiert? Und was ist die Anzahl der rekursiven Aufrufe?
Lieben Gruß,
Fulla
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 19:12 Di 03.11.2009 | | Autor: | laco |
Die Tribonacci-Zahlen sind so definiert: f(n) = f(n-1) + f(n-2) + f(n-3)
Rekursiver Auruf ist, wenn vorher bereits berechnete Werte erneut berechtnet bzw. benutzt werden.
f(4) = f(3) + f(2) + f(1)
Hast Du eine Idee?
|
|
|
| |
|
Hallo laco, etwas verspätet noch ein ![[willkommenmr]](/images/smileys/willkommenmr.png "[willkommenmr]")
> Folge der Aufrufe sieht wie folgt aus für n>3:
> 3, 6, 9, 12 etc.
Wie kommst Du denn darauf?
Für [mm] a_4 [/mm] wird die Formel einmal aufgerufen.
Für [mm] a_5 [/mm] einmal und einmal rekursiv für [mm] a_4, [/mm] also zweimal.
Für [mm] a_6 [/mm] einmal und zweimal für [mm] a_5 [/mm] (s.o.) und einmal für [mm] a_4, [/mm] also viermal.
Schon hier stellt sich die Frage, wie der Algorithmus denn programmiert wird. Natürlich ist es nicht effektiv, [mm] a_4 [/mm] für die Berechnung von [mm] a_5 [/mm] zu bestimmen und dann noch einmal separat, wenn [mm] a_4 [/mm] benötigt wird.
Trotzdem müssen wir (wegen der vorausgesetzten Rekursivität) ja annehmen, dass für jedes neue [mm] a_n [/mm] nur die Bildungsregel und die Werte [mm] a_1, a_2, a_3 [/mm] existieren, also keine weiteren [mm] a_i [/mm] zwischengespeichert werden. Das würde in der Praxis natürlich niemand so machen, zumal es genügt, die jeweils letzten drei Werte vorher zu speichern!
Gehen wir nun aber trotzdem davon aus, dass für die Berechnung von [mm] a_n [/mm] (mit n>3) [mm] a_{n-1}, a_{n-2} [/mm] und [mm] a_{n-3} [/mm] jeweils nur einmal bestimmt werden müssen (sofern Du das programmieren kannst). Das ließe sich anders annehmen, aber dann mit anderen Ergebnissen.
Am besten skizzierst Du also erst einmal Deine Rekursionsstruktur; sonst ist die Anzahl der Aufrufe nicht allgemein zu bestimmen!
lg
reverend
|
|
|
|
