Fibonacci Algorithmus

AlphaCentauri

Hi!
Ich hab nen rekursiven Algorithmus für Fibonacci-Zahlen:
int fib(int i){
if(i<=1){
return i;
}
return fib(i-1)+fib(i-2);
}
Ich weiß, dass es besser geht
aber mich würde bei dieser Vorgehensweise mal die Anzahl der Additionen interessieren [fib(i-1)+fib(i-2)]. Wie ist die Formel dafür? Kann da jemand helfen?

Shade Of Mine

was verstehst du unter besser?

schneller? zB iterativ oder die rekursion beschleunigen?
dann schau mal hier: http://tutorial.schornboeck.net/los/fibonacci.htm

ansonsten: erklaer mal was du meinst

PS:
mal abgesehn davon, dass dein code fehlerhaft ist.
if(i<=1) return i;
muss
if(i<=2) return 1;

heissen.

denn fib(1) == fib(2) == 1

AlphaCentauri

Wieso fehlerhaft? Deins geht natürlich auch, aber meins geht genauso...
Aber zurück zu meinem Problem:
Wenn ich fib(100) aufrufe, wird immer dann eine Addition durchgeführt, wenn er bei fib(i-1)+fib(i-2) angekommen ist. Meine Frage: Wie oft wird diese Addition bei fib(i) aufgerufen?
Bei fib(2) ist es eine Addition, bei fib(3) sind es 2 Additionen, bei fib(5) sind es 7 Additionen. Die Anzahl der Additionen steigt also schnell, aber welches System steckt dahinter?

musicman

Das ganze ist auf jeden Fall exponentiell, aber AFAIK mit einem nicht gerade ganzzahligen Faktor; genaueres gibt's aber bestimmt im Netz zu finden.

John Doe

Die Darstellung als Formel dürfte ab n > (...?) nicht zu schlagen sein.

#include <stdio.h> 
#include <stdlib.h> 
#include <math.h> 

int main(int argc, char* argv[]) 
{ 
  unsigned int arg = atoi(argv[1]); 
  long double fib = floor(powl((1.0 + powl(5.0, 0.5)) 
                    / 2.0, arg) 
                    / (powl(5.0, 0.5)) + 0.5); 
  printf("Fib(%u): %.lf\n", arg, fib); 

  return 0; 
}

mfg JJ