Fibonacci Zahlen
Fibonacci-Zahlen lassen sich in Java (wie in fast jeder Programmiersprache) sehr leicht berechnen. Da der Algorithmus für die Fibonacci-Folge an sich schon recht einfach ist, sind Fibonacci-Zahlen generell ein schönes Beispiel zur Programmierung von Algorithmen. Dieser Artikel zeigt, wie es in Java geht.
Fibonacci-Zahlen sind eine (unendliche) Folge von Zahlen, wobei sich jeder weitere Zahl aus der Addition der beiden Vorgänger ergibt. Gestartet wird mit null und eins. Die nächste Fibonacci-Zahl ist deren Summe, also wieder die eins. Jetzt ergibt die Summe der beiden letzten (Fibonacci-)Zahlen zwei (eins plus eins). Die nächste ist dann die drei (eins plus zwei), dann kommt die fünf (zwei plus drei), dann acht (drei plus fünf) usw. Für den Laien überraschend ist dabei, wie schnell die Zahlen irgendwann deutlich größer werden, obwohl die Sprünge zu Beginn noch recht klein sind.
Bevor wir uns den Java-Code zur Berechnung von Fibonacci-Zahlen anschauen, hier zunächst eine etwas längere Folge von solchen Zahlen (Fibonacci-Reihe bis zu einer Million):
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
Zur Wiederholung: jede Zahl in dieser Liste ergibt sich durch Addition ihrer beiden Vorgänger.
Der Algorithmus in Java
Das folgende Java-Programm gibt die Fibonacci-Zahlen bis zu einer vorgegebenen Obergrenze aus. Zu beachten ist, daß hier der Einfachheit wegen der Datentyp long verwendet wird, so daß das Programm nur mit Zahlen bis 2^63 arbeiten kann. Wer mit größeren Zahlen arbeiten will, sollte auf die Klasse BigInteger ausweichen - damit lassen sich im Prinzip beliebig große Zahlen verarbeiten (Einschränkungen dann nur noch durch vorhandenen Speicherplatz und Rechenzeit)./**
* Berechnet Fibonacci-Zahlen und gibt die Folge aus.
* @param args[0] Limit, bis wohin Fibonacci-Zahlen berechnet werden sollen; default = 1000000.
* @param args[1] Trenner zur Ausgabe, z. B. ", "; default = <Zeilenumbruch>
*/
public static void main(final String[] args) {
long endValue = 1000000;
String trenner = System.getProperty("line.separator");
try {
endValue = Long.parseLong(args[0]);
trenner = args[1];
} catch (Exception ignore) {
}
long fib1 = 0;
long fib2 = 1;
System.out.print(fib1);
while (fib2 <= endValue) {
System.out.print(trenner);
System.out.print(fib2);
long newFib = fib1 + fib2;
fib1 = fib2;
fib2 = newFib;
}
System.out.println();
}
}
Beispiel:
Rufen wir das Programm auf mit
java Fibonacci 1000000
So erhalten wir als Ausgabe alle Fibonacci-Zahlen bis zu einer Million:
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
Auf Erweiterungs- und Optimierungsmöglichkeiten möchte ich an dieser Stelle nicht eingehen. Ziel dieses Artikels war, zu zeigen, wie man in Java grundsätzlich einfache Algorithmen implementieren kann und wie dies anhand des Beispiels von Fibonacci-Zahlen aussieht.
Fibonacci rekursiv: fib(n)
Eine Besonderheit der Fibonacci-Zahlen ist, daß deren Ermittlung mit Hilfe eines rekursiven Algorithmus außergewöhnlich einfach ist, mit der Besonderheit, daß ein solcher Algorithmus bereits bei relativ kleinen Zahlen für praktische Zwecke unbrauchbar langsam wird.Um dies zu verdeutlichen, implementieren wir einen rekursiven Algorithmus, der uns die n. Fibonacci-Zahl liefert, in dem er sich selbst zweimal aufruft (mit n-1 und n-2) und diese Summe zurückgibt. Wir müssen dazu noch den Anker implementieren, nämlich daß die ersten beiden Fibonacci-Zahlen jeweils die eins sind (und die nullte die Null) - negative Argumente interpretieren wir der Einfachheit wegen einfach zur Null um:
if (n <= 2) {
return (n > 0) ? 1 : 0;
}
return fib(n - 1) + fib(n - 2);
}
So einfach und smart dieser Algorithmus auch aussehen mag: wenn Sie damit herumspielen, werden Sie feststellen, daß die Berechnung z. B. schon für die fünfzigste Fibonacci-Zahl ewig lange dauert. Das liegt daran, daß pro Zahl zwei rekursive Aufrufe nötig werden und durch diese Verdoppelung sehr schnell (auf den ersten Blick) unglaublich viele Aufrufe entstehen.
Warum ist fib(n) so langsam?
Genau genommen summiert sich einfach die Berechnungszeit für die beiden vorausgehenden Fibonacci-Zahlen, d.h. die Berechnungsdauer des rekursiven Algorithmusses verhält sich genauso wie die Fibonacci-Zahlen selbst.Es gilt: fib(n) = fib(n-1) + fib(n-2)
Und gleichzeitig: Berechnungsdauer(fib(n)) = Berechnungsdauer(fib(n-1)) + Berechnungsdauer(fib(n-2)).
Exemplarisch sei erwähnt, daß die Berechnung der fünfzigsten Fibonacci-Zahl auf meinem Rechner schon circa zwei Minuten dauert, während die vierzigste nur circa eine Sekunde benötigt. Die sechzigste ist mit dieser (rekursiven) Methode praktisch nicht mehr berechenbar, während der zuerst vorgestellte (sequenzielle) Algorithmus die ersten sechzig Fibonacci-Zahlen im Millisekundenbereich berechnen kann.
fib(n) iterativ berechnen
Nun haben wir zwei Algorithmen: den schnellen iterativen, der alle Fibonacci-Zahlen bis zu einer vorgegebenen Obergrenze berechnet, und den rekursiven, bei großen Zahlen unverwendbar langsamen Algorithmus, der uns gezielt zum Beispiel die 35. Fibonacci-Zahl berechnen kann.Wir implementieren nun eine Funktion, welche - genau wie die rekursive Variante - eine bestimmte (zum Beispiel die zehnte) Fibonacci-Zahl iterativ (und damit schnell) ermittelt:
if (n <= 2) {
return (n > 0) ? 1 : 0;
}
long fib1 = 0;
long fib2 = 1;
for (int i = 1; i < n; i++) {
final long newFib = fib1 + fib2;
fib1 = fib2;
fib2 = newFib;
}
return fib2;
}
Damit haben wir einen schnellen Algorithmus, der uns gezielt eine Fibonacci-Zahl mit vorgegebener Ordnungsnummer berechnet. Die langsame, wenn auch im Programmcode schöner lesbare, rekursive Variante benötigen wir dazu also nicht.
Rufen wir diese Funktion zum Beispiel für die 30. Fibonacci-Zahl auf:
Sytstem.out.println(fib(30));
so erhalten wir schnell und korrekt:
832040
Beachte: mit dem Datentyp long kann maximal die 92. Fibonacci-Zahl (7540113804746346429) korrekt berechnet werden. Für größere Fibonacci-Zahlen reicht der Datentyp long nicht mehr aus.
fib(n) für sehr große Zahlen
Wer mit diesem Algorithmus und sehr großen Zahlen herumspielen will, die nicht mehr mit dem Datentyplong darstellbar sind, weicht am besten auf die dafür vorgesehene Klasse BigInteger aus:private static final BigInteger INT_1 = new BigInteger("1");
public static BigInteger fib(final int n) {
if (n <= 2) {
return (n > 0) ? INT_1 : INT_0;
}
BigInteger fib1 = INT_0;
BigInteger fib2 = INT_1;
for (int i = 1; i < n; i++) {
final BigInteger newFib = fib1.add(fib2);
fib1 = fib2;
fib2 = newFib;
}
return fib2;
}
Jetzt können wir auch riesige Fibonacci-Zahlen schnell berechnen:
Sytstem.out.println(fib(1000));
ergibt in Sekundenschnelle:
43466557686937456435688527675040625802564660517371780402481729089536555417949051
89040387984007925516929592259308032263477520968962323987332247116164299644090653
3187938298969649928516003704476137795166849228875
Und bei der 1000. Fibonacci-Zahl ist mit diesem Algorithmus noch lange nicht Schluß. Viel Spaß beim Experimentieren!
Ein weiterer Artikel, der zeigt, wie man in Java einfache Algorithmen programmieren kann, behandelt das Thema Primzahltest.
| Nach oben, Inhaltsverzeichnis, Impressum |
Admin: Artikel editieren |