• FibFacQueen

Die sogenannten Fibonacci-Zahlen stellen das 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 zum Beispiel 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 eingangs gegebener 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 zum Beispiel 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