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 |
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: |
|
zu den Hausaufgaben | |
zur Startseite | www.pohlig.de (C) MPohlig 2003 |