Fibonacci-Folge im Java-Algorithmus

Inhaltsverzeichnis

1. Was ist die Fibonacci-Reihe?
2. Algorithmus #1: Fibonacci-Zahlen erstellen
3. Algorithmus #2: Fibonacci-Zahlen liefern

Was ist die Fibonacci-Reihe?

Die Fibonacci-Folge ist eine unendliche Reihe von Zahlen, in der jede Zahl (außer den ersten beiden) die Summe ihrer beiden Vorgänger ist:

0, 1, 1, 2, 3, 5, 8, 13, 21...

In einem Kachelmuster lässt sich die Fibonacci-Reihe grafisch so darstellen:

Daraus lässt sich folgende Formel erstellen, um den Wert jeder beliebigen Fibonacci-Zahl zu berechnen:

fib(n) = fib(n-1) + fib (n-2)

Alles klar? Dann wollen wir jetzt Algorithmen in Java ins Spiel bringen :)

Algorithmus #1: Fibonacci-Zahlen erstellen

Der erste Algorithmus, den wir erstellen, hat folgendes Ziel:

• Speichere eine bestimmte Anzahl von Fibonacci-Zahlen in einem Array.

Klingt doch garnicht so wild, oder? Ist es auch nicht - und hier der Code:

public static void main(String[] args) {

    int laenge = 50;

    long[] fibonacci = new long[laenge];
    fibonacci[0] = 0;
    fibonacci[1] = 1;

    for(int i = 2; i < laenge; i++){
        fibonacci[i] = fibonacci[i-1] + fibonacci[i-2];
    }
}                

Zuerst legen wir die gewünschte Länge der Fibonacci-Reihe in der Variablen laenge fest (hier mit dem Wert 50). Diese Variable ist vom Typ long, weil wir am Ende sehr hohe Fibonacci-Zahlen erhalten und Integer mit einer maximalen Kapazität von 2147483647 nicht ausreicht.

Anschließend wird das Array mit eben dieser Länge definiert. Die ersten beiden Fibonacci-Zahlen (0 und 1) legen wir bereits fest.

Als nächstes verbauen wir unsere Formel von oben in den Schleifenkörper der for-Schleife. Die Schleifenvariable beginnt bei 2 und läuft damit 48 Mal (die ersten beiden Fibonaccis haben wir ja bereits dem Array hinzugefügt).

Auf diese Weise wird das Array mit den restlichen Fibonacci-Zahlen von der zweiten bis zur fünfzigsten gefüllt.

Hier noch der Output:

for(int i  = 0; i < fibonacci.length; i++){
    System.out.println(fibonacci[i] + ", ");
} 

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269, 2178309, 3524578, 5702887, 9227465, 14930352, 24157817, 39088169, 63245986, 102334155, 165580141, 267914296, 433494437, 701408733, 1134903170, 1836311903, 2971215073, 4807526976, 7778742049

Algorithmus #2: Fibonacci-Zahl liefern

Noch spannender ist ein Algorithmus, der uns gezielt eine bestimmte Zahl aus der Fibonacci-Reihe berechnet. Der Job, den der Algorithmus also ausführen soll, lautet:

• Liefere die n-te Fibonacci-Zahl aus der Fibonacci-Reihe zurück.

Hier nochmal die Fibonacci-Zahlen von der "nullten" bis zur achten:

Den passenden Java-Algorithmus designen wir mit einer verzweigten rekursiven Methode:

public class RecursiveFibonacciSequence {

    public static void main(String[] args) {
        int x = getFibonacciNumberAt(5); // 5
        System.out.println(x);
    }

    public static int getFibonacciNumberAt(int n) {
        if (n < 2) {
            return n;
        } else
            return getFibonacciNumberAt(n - 1) + getFibonacciNumberAt(n - 2);
    }
}                

In die Methode getFibonacciNumberAt() geben wir als Argument die gewünschte n-te Fibonacci-Zahl der Reihe ein und erhalten den passenden Wert zurückgeliefert. So hat etwa die fünfte Fibonacci-Zahl den Wert 5.

Die Methode ruft sich dabei jeweils zweimal selbst aufs Neue auf (getFibonacciNumberAt(n - 1) und getFibonacciNumberAt(n - 2)), wobei die Anzahl der Methoden damit exponentiell ansteigt.

Es kommt erst dann zu keinem weiteren Methodenaufruf, wenn die Abbruchbedingung n-2 erfüllt ist. Dann wird der Wert 1oder 0 zurückgeliefert. Die Summe der 0er und 1er ergibt den finalen Rückgabewert der Methode: In unserem Fall ist das 5 - und das ist unsere gesuchte Fibonacci-Zahl.

Grafisch sieht der Ablauf der rekursiven Methodenaufrufe bei getFibonacciNumberAt(5) so aus:

Iterative Alternative

Für die Berechnung kleiner Fibonacci-Zahlen ist der Java-Algorithmus von oben OK! Aber: Wenn wir versuchen, die 40., 50. oder gar 100. Fibonacci-Zahl abzufragen, wird unser Programm enorm lange Zeit für die Ausführung benötigen oder auch abschmieren. Der Grund ist, dass der Aufrufbaum exponentiell anwächst.

Zum Beispiel braucht die Ermittlung der 20. Fibonacci-Zahl (=6765) mit der Methode getFibonacciNumberAt(20) unglaubliche 21891(!) Methodenaufrufe. Eine echte Performance-Katastrophe also.

Wir sollten also eine komplett neue Methode entwickeln, um unseren Algorithmus auch bei etwas höheren Fibonaccis performant zu halten.

Designen wir jetzt einen iterativen Algorithmus mit einer klassischen Schleife:

public class RecursiveFibonacciSequence {

    public static void main(String[] args) {
        int x = getFibonacciNumberAtV3(5); // 8
        System.out.println(x);
    }

    public static int getFibonacciNumberAtV3(int n){
        int last = 0;
        int next = 1;
        for (int i = 0; i < n; i++) {
            int old_last = last;
            last = next;
            next = old_last + next;
        }
        return next;
    }
}                

Die Methode getFibonacciNumberAtV3() wird mit dem Argument 5 ausgeführt und liefert die fünfte Fibonacci-Zahl, nämlich 8 zurück.

Anders als bei der rekursiven Variante oben beginnt die Zählung der Fibonacci-Reihe bei dieser Methode nicht bei 0, sondern bei 1. Deshalb ist die fünfte Fibonacci-Zahl die 8.

Innerhalb der Schleife werden die einzelnen Fibonacci-Zahlen durch die Addition von old_last und last last zu next gebildet.

Nach der Schleife wird die letzte berechnete Fibonacci-Zahl (d.h. der letzte Wert der Variable next) mit return zurückgeliefert. Das ist die n-te Fiboncci-Zahl, die wir suchen.

Die schrittweise Veränderung der Variablen im Algorithmus siehst du in dieser Verlaufstabelle: