Sondieren - Rekursion < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 11:35 So 04.11.2007 | | Autor: | Haase |
| Aufgabe | a)
Die Fibonacci-Zahlen sind definiert als
f(n) = {
0,
1,
f(n-1) + f(n-2), n>=2}
Finden Sie(z.B. durch Sondieren) eine Formel für die Anzahl Aufrufe der Methode zur rekursiven Berechnung und beweisen Sie mit voll. Indukt.
b)
Ermitteln Sie die Lösung der folgenden Rekursion:
(a) T(1) = 0
(b) T(n) = T(n/2) +1 |
Guten Tag Allerseits,
wäre nett wenn Ihr mir bei 2 Aufgabe helfen würdet.
Zu a)
Als erstes habe ich Sondiert:
fn = f(n-1) + f(n-2)
= f(n-2) + 2*f(n-3)+f(n-4)
= f(n-3) + 3*( f(n-4) + f(n-5) ) + f(n-6)
Wie gehe ich weiter vor?
Zu b)
Ich habe als erstes die Zweierpotenzen eingesetzt:
T(1) = 0
T(2) = T(1) +1 = 1
T(4) = T(2) +1 = 2
T(8) = T(4) +1 = 3
T(16) = T(8) +1 = 4
Durch raten bin ich auf die Formel : log2(n) gekommen, die auch funktioniert. Nur wie komme ich zu log2(n)?
Vielen Dank im Voraus,
Gruß Haase
|
|
| |
|
Hallo,
ich beginne mal mit der zweiten Aufgabe, indem ich deine Notizen etwas anders schreibe:
[mm] T(2^0) [/mm] = 0
[mm] T(2^1) [/mm] = T(1) +1 = 1
[mm] T(2^2) [/mm] = T(2) +1 = 2
[mm] T(2^3) [/mm] = T(4) +1 = 3
[mm] T(2^4) [/mm] = T(8) +1 = 4
vermutlich also (was zu beweisen wäre!):
[mm] T(2^n) [/mm] = n
Jetzt nur noch nach n auflösen.
Zur ersten Aufgabe:
Sondiere doch mal für mehrere feste n, z.B. für n=2,3,4,5, und zwar so lange, bis du bei 1 oder 0 angekommen bist, die ja feste Werte haben.
Ich zeige mal, was ich meine:
T(4) = T(2) + T(3) = (T(0) + T(1)) + (T(1) + T(2)) = (T(0) + T(1)) + (T(1) + (T(0) + T(1)))
Wir können von T(0) = T(1) ausgehen, weil f(0) und f(1) Konstanten sind, die nicht weiter berechnet werden müssen, dann kommen wir auf:
T(4) = 5*T(5)
Wenn du das für mehrere n machst, dann findest du ein Muster, das du dann beweisen musst.
Gruß
Martin
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 16:26 So 04.11.2007 | | Autor: | Haase |
Danke Dir Martin. Die zweite Aufgabe habe ich gelöst.
Bei der ersten Aufgabe habe ich noch eine Frage.
Du hast T(4) = 5 * T(5) raus.
Den Multiplizierten Faktor "5",weil ich 5 Additionen(T(1)+T(0)+T(1)+T(1)+T(0)) habe?
Wie kommst du auf die 5 in T()?
Wenn ich davon ausgehe, das die 5 die anzahl T's(anzahl additionen) für die Bildung zu T(4) ist, dann komme ich bei T(2),T(3),T(4) zu:
T(2) = 2*T(2)
T(3) = 3*T(3)
T(4) = 5*T(5)
Wie verfahre ich fort?
|
|
|
| |
|
Hallo,
ich habe einen klitzekleinen Fehler gemacht. Es sollten ja die Aufrufe gezählt werden, nicht die Terme. Also:
Für 0 und 1 bekommen wir die Werte sofort, also ist kein Aufruf nötig (oder zählen wir das als Aufruf? Wie auch immer, das ist eine Sache der Festlegung.)
T(0) = T(1) = 0
f(2) = f(1) + f(0)
2 Aufrufe + die Aufrufe, die wir für f(0) und f(1) benötigen (hier trivial):
T(2) = 2 + T(1) + T(0) = 2 + 0 + 0 = 2
f(3) = f(2) + f(1)
2 Aufrufe + die Aufrufe, die wir für f(1) und f(2) benötigen:
T(3) = 2 + T(2) + T(1) = 2 + 2 + 0 = 4
f(4) = f(3) + f(2)
2 Aufrufe + die Aufrufe, die wir für f(2) und f(3) benötigen:
T(4) = 2 + T(3) + T(2) = 2 + 4 + 2 = 8
usw.
Wir sehen, dass das aufgrund der rekursiven Definition wohl auch mit den Fibonacci-Zahlen zusamenhängt, nur wie?
Berechne vielleicht noch die nächsten vier Glieder und vergleiche mit der F-Folge.
Gruß
Martin
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 10:18 Mo 05.11.2007 | | Autor: | Haase |
Danke Dir. Ich werde mal rumprobieren.
|
|
|
|
