Fibonacci

Berechnung von Fibonacci-Zahlen.

Feb 04
Fibonacci Joachim Christ


Die sog. Fibonacci-Zahlen stellen den Wachstum einer Population dar. Die ersten Fibonacci-Zahlen sind: 1 1 2 3 5 8 13 21 34 …

Jede weitere Fibonacci-Zahl ergibt sich aus der Summe der beiden Vorgänger-Zahlen, also z. B. 5 + 8 = 13. Aus dieser Definition lässt sich ein linearer Algorithmus ableiten.

last = 0;
fib = 1;
for (i = 2; i <= n; i++) {
  next = last + fib;
  last = fib;
  fib = next;
}


Aus der eingangs gegebenen Definition der Fibonacci-Zahlen kann eine rekursive Berechnung abgeleitet werden.

int fib( int n )
{
  if (n <= 2)
     return 1;
   else
      return fib( n - 1 ) + fib( n - 2 );
}


Man erkennt, dass z. B. bei der Berechnung der 4. Fibonacci-Zahl auf die 2. und 3. Zahl zurück gegriffen wird. Zur Berechnung der 3. Zahl wird erneut die 2. Zahl benötigt. Daraus ergibt sich ein recht schlechter Aufwand der Berechnung, da die identischen Berechnungen mehrfach ausgeführt werden.


Eine Demo für die Berechnung von Fibonacci-Zahlen, bei der eine Langzahl-Arithmetik mit einer beliebigen Stellenzahl benutzt wird.

↵
 

Bitte geben Sie die Zahl ein, die bestimmt, die wievielte Fibonacci-Zahl berechnet werden soll, und starten Sie die Berechnung durch '↵' oder durch Klicken des Icons.

Voriger Beitrag Nächster Beitrag