rekursive Funktion zur Berechnung der Fibonacci-Zahl
-
Ich habe gerade folgende übung und brauche dringend hilfe:
Die Fibonacci-Zahlen sind wie folgt definiert:
F0 = 0
F1 = 1
Fn = Fn-1 + Fn-2 für n>1
Daraus ergibt sich die folgende Zahlenreihe:
F0=0
F1=1
F2=1
F3=2
F4=3
F5=5
Die Fibonacci-Zahl zum Index 4 ist somit beispielsweise F4 = 3.
a. Schreiben Sie eine rekursive Funktion zur Berechnung der Fibonacci-Zahl zum Index n.
b. Entwickeln Sie ein nicht-interaktives Testprogramm, mit dem Sie die Rechenzeit und die Anzahl der rekursiven Funktionsaufrufe für n = 1, 2, … ermitteln. Bis zu welchen n wird das Ergebnis in weniger als 60 Sekunden ermittelt?
c. Entwickeln Sie eine iterative Funktion zur Berechnung der Fibonacci-Zahl zum Index n und vergleichen Sie deren Laufzeit für große n mit der der rekursiven Variante.Hinweis: Laufzeitmessungen können wie folgt durchgeführt werden:
#include <time.h>
…
clock_t tm1, tm2;
tm1 = clock();
/* Programm */
tm2 = clock();
printf("Dauer: %.2f Sekunden\n", (double)(tm2-tm1)/CLOCKS_PER_SEC);
-
Was hast du? Woran hakts?
-
was meinst du ?
ich brauche hilfe
-
maxim2050 schrieb:
was meinst du ?
ich brauche hilfeWobei?
-
Das schöne bei der rekursiven Lösung ist, dass man ziemlich genau die Definition:
maxim2050 schrieb:
F0 = 0
F1 = 1
Fn = Fn-1 + Fn-2 für n>1umsetzen kann... einfache eine Funktion mit einem Parameter und entsprechend der Definition den richtigen Wert zurückgeben...
