Fibonaccizahlen Aufwand berechnen

[FinalFantasy]

Hallo,

hab mir ein Programm geschrieben, die Fibonacci-Zahlen berechnet. Das Programm läuft rekursiv.

Jetzt bin ich auf einer Suche nach einer Formel, oder einem Weg, wie ich berechnen kann, wieviele Rekursionen ich machen muss, um zu dem Ergebnis zu gelangen.

Habe bis jetzt nur eine Möglichkeit gefunden, nur um mit dieser Möglichkeit den Aufwand zu berechnen hat den selben Aufwand, als gleich die Zahl zu berechnen.

Fibonacci:

f(1) = 1

f(0) = 0;

f(x) = f(x-1) + f(x-2);

[nic_power]

Hallo,

dazu gibts es im Netz (google) mehr als genug Fundstellen, da es sich um eine beliebte Aufgabe handelt:

http://www.intellektik.informatik.tu-darmstadt.de/~klausvpp/Java2002/Uebungen/3/sld006.htm

Nic

[FinalFantasy]

Hm, hab mir die Seite angeschaut, aber die bringt mich auch nicht weiter, da die Formel zur Aufwandsberechnung den gleichen Aufwand hat, wie die Zahl selber auszurechnen. Folglich wäre es absoluter Unsinn erst den Aufwand auszurechnen!

[Schachcomputerfreak]

Original geschrieben von FinalFantasy

Hallo,

hab mir ein Programm geschrieben, die Fibonacci-Zahlen berechnet. Das Programm läuft rekursiv.

Jetzt bin ich auf einer Suche nach einer Formel, oder einem Weg, wie ich berechnen kann, wieviele Rekursionen ich machen muss, um zu dem Ergebnis zu gelangen.

Habe bis jetzt nur eine Möglichkeit gefunden, nur um mit dieser Möglichkeit den Aufwand zu berechnen hat den selben Aufwand, als gleich die Zahl zu berechnen.

Fibonacci:

f(1) = 1

f(0) = 0;

f(x) = f(x-1) + f(x-2);

OK, die Formel kenn ich ja, aber wie darf ich die Frage verstehen? Du willst eine Formel um zu berechnen wieviele Rekursionen Du machen musst um zum Ergebnis zu gelangen. Aber von welchem Ergebnis reden wir hier? Hast Du eine Zahl gegeben die Du auf Fibonacci prüfen willst und willst die Rekursionstiefe ermitteln (ohne die Rekursion durchführen zu müssen) oder wie ist die Frage jetzt gemeint?

[FinalFantasy]

Ich übergebe der Funktion eine Zahl x, und die Funktion soll mir die Fibonaccizahl auf dieser eben x-ten Stufe zurückgeben.

Ich möchte jetzt wissen, wie oft sich die Funktion wieder selber aufrufen muss, um an dieses Ergebniss zu gelangen.

[Schachcomputerfreak]

Original geschrieben von FinalFantasy

Ich übergebe der Funktion eine Zahl x, und die Funktion soll mir die Fibonaccizahl auf dieser eben x-ten Stufe zurückgeben.

Ich möchte jetzt wissen, wie oft sich die Funktion wieder selber aufrufen muss, um an dieses Ergebniss zu gelangen.

Naja, eigentlich doch ganz einfach. Gehen wir das mal durch

1. Für f(0) und f(1) findet keine weitere Rekursion statt, da hier Festwerte vorliegen

2. Für f(2) stößt man auf die Festwerte für f(1) und f(0) also auch keine Rekursion

3. Für f(3) stößt man auf f(2)+f(1) Hier ist die 1. Rekursion

4. für f(4) berechnet man f(3)+f(2) das sind 2 rekursive Aufrufe. f(3) ruft eine weitere Rekursion auf, macht Aufwand 3

5. f(5) = f(4)+f(3) (2 Rekursionen) = f(3)+f(2)+f(2)+f(1) (3 Rekursionen und ein Festwert) = f(2)+lauter Festwerte (1 Rekursion) also insgesamt 6 Rekursionen

Macht man das logisch so weiter kommt man bei f(6) auf 10 Rekursionen, bei f(7) auf 15, etc. (nur die schreib ich jetzt nicht mehr hin. Probier es einfach aus..) Das ist eine Summenfunktion. Für x >=3 errechnet sich die Anzahl der Rekursionen als Summe der Zahlen von 1 bis x-2. Macht man die Probe so siehst Du im Fall f(3), die Summe der Zahlen von 1 bis 1 ist 1. Im Fall f(4) ist die Summe der Zahlen von 1 bis 2 die 3. Im Fall f(5) ist die Summe 1+2+3=6 usw.

Berechnen kannst Du das entweder innerhalb einer Schleife (aufwendig) oder aber durch einen einfachen Trick. Summiert man nämlich die Summe der Zahlen von 1 bis n, so kann man die Summe errechnen durch n*(n+1)/2

Im Fall f(6) also ist n=4 und damit 4*5/2 = 10

Im Fall f(7) ist n=5 und damit 5*6/2 = 30/2 = 15

Und da sag mal einer Mathe wäre nicht was schönes...

[FinalFantasy]

Stimmt, jetzt wo ichs les.

Ich hab nie behauptet, Mathe sei nicht schön.

Ich find sogar sehr interessant.

Grad solche kleinen Probleme. *gg*

[Tapeman]

Wenn mich nicht alles irrt,

brauch man um die n-te Fibonaccizahl zu berechnen ca 1,6^n Funktionsaufrufe.

1,6 steht hier für den Goldenen Schnitt 1/(x+1)=x.

Gruß Tapeman

[Tapeman]

Warum löst das Problem eigentlich rekursiv und nicht iterativ?

[FinalFantasy]

Weil ich einen Parktikanten hatte, und ihm zeigen wollte, was rekursive Funktionen sind.

Und imo ist es das Problem für einen Anfänger Rekursiv noch leichter verständlich als iterativ, wenns auch um vieles langsamer ist.

[Tapeman]

Gut, dann habe ich nichts gesagt. :-)