14.3 Fibonacci-Zahlen
Fibonacci-Zahlen Die Fibonacci-Folge hat folgende Gestalt:

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

Man erkennt, dass ein Folgenglied sich dadurch berechnet, dass man seine beiden Vorgänger addiert. Damit dies funktioniert, muss man allerdings wissen, welche Werte die beiden ersten Glieder haben. Die exakte Formulierung der Fibonacci-Folge geschieht durch das folgende Bildungsgesetz:

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

Diese Definition lässt sich nahezu eins zu eins in einen Java-Quellcode übersetzen:

 

FibonacciDemo. java

public static long fib(int a){
  if (a==1||a==2) return 1;
  else return fib(a-1)+fib(a-2);
}

So wie die Methode kgV die Methode ggT benutzt hat, benutzt die Methode fib selbst wieder die Methode fib.

Was passiert, wenn fib(5) bestimmt werden soll? Bevor fib(5) bestimmt werden kann, werden die Aufrufe fib(4) und fib(3) abgearbeitet, wobei z.B. fib(3) erst wieder fib(2) und fib(1) aufrufen, die aber jeweils 1 zurückgeben.

Der erste Teil der Aufruffolge ist also: fib(5) -> fib(4) -> fib(3) -> fib(2), liefert Wert 1. Zurück zu fib(3) weiter auszuwerten fib(3) -> fib(1), liefert 1, zurück an fib(3), fib(3) gibt an fib(4) den Wert 2. Nun kann fib(4) weitermachen, denn es braucht noch fib(2), die 1 zurückliefert. Nun kann fib(4) den Wert  3 an fib(5) liefern, fib(5) benötigt aber noch fib(3) usw.

Deutlich wird: Es entsteht ein komplexe Aufruffolge der Methode und es wird die Methode recht häufig mit den gleichen Parametern aufgerufen, was die Effizienz des Algorithmus schwer beeinträchtigt. Eine nicht rekursive Methode wäre wesentlich schneller und würde weniger Speicherplatz benötigen. Deutlich wird die Problematik, wenn z.B. fib(1000) bestimmen wollte. (vgl. dazu auch die Hausaufgaben)

 

Download:

FibonacciDemo. java

import info1.*;
public class FibonacciDemo{
  public static void main(String[] args){
    StoppUhr stoppUhr1 = new StoppUhr();
    System.out.print("Geben Sie ein Zahl an: ");
    int a = Console.in.readInt();
    stoppUhr1.starten();
    int fib = fibonacci(a);
    stoppUhr1.stoppen();
    System.out.println("fib("+a+") = "+fib);
    System.out.println(stoppUhr1);
  }
  private static int fibonacci(int a){
    if (a==1||a==2) return 1;
    else return fibonacci(a-1)+fibonacci(a-2);
  }
}

In das Programm eingebaut ist wieder eine Stoppuhr. Test mit verschieden große Werte für 'n' zeigen, dass der Algorithmus für größere Zahlen sehr große Rechenzeiten benötigt.  In den Hausaufgaben werden effizientere Algorithmen zur Berechnung von Fibonacci-Zahlen vorgestellt und mit einander verglichen.

zu den Hausaufgaben  
zur Startseite www.pohlig.de (C) MPohlig 2003