Fibonacci-Serie in Java

1. Übersicht

In diesem Tutorial sehen wir uns die Fibonacci-Serie an.

Insbesondere werden wir drei Methoden implementieren, um den n-ten Term der Fibonacci-Reihe zu berechnen , wobei die letzte eine zeitkonstante Lösung ist.

2. Fibonacci-Serie

Die Fibonacci-Reihe ist eine Reihe von Zahlen, bei denen jeder Begriff die Summe der beiden vorhergehenden Begriffe ist . Die ersten beiden Begriffe sind 0 und 1 .

Beispielsweise sind die ersten 11 Terme der Reihe 0, 1, 1, 2, 3, 5, 8, 13, 21, 34 und 55 .

In mathematischen Begriffen wird die Folge S n der Fibonacci-Zahlen durch die Wiederholungsrelation definiert:

S(n) = S(n-1) + S(n-2), with S(0) = 0 and S(1) = 1

Schauen wir uns nun an, wie der n-te Term der Fibonacci-Reihe berechnet wird . Die drei Methoden, auf die wir uns konzentrieren werden, sind rekursiv, iterativ und verwenden die Binet-Formel.

2.1. Rekursive Methode

Lassen Sie uns für unsere erste Lösung einfach die Wiederholungsrelation direkt in Java ausdrücken:

public static int nthFibonacciTerm(int n) { if (n == 1 || n == 0) { return n; } return nthFibonacciTerm(n-1) + nthFibonacciTerm(n-2); }

Wie wir sehen können, prüfen wir, ob n gleich 0 oder 1 ist. Wenn es wahr ist, geben wir diesen Wert zurück. In jedem anderen Fall rufen wir die Funktion rekursiv auf, um den (n-1) -ten Term und den (n-2) -ten Term zu berechnen und ihre Summe zurückzugeben.

Obwohl die rekursive Methode einfach zu implementieren ist, sehen wir, dass diese Methode viele wiederholte Berechnungen durchführt. Um beispielsweise den 6. Term zu berechnen , rufen wir an, um den 5. und den 4. Term zu berechnen . Darüber hinaus ruft der Aufruf zur Berechnung des 5. Terms dazu auf, den 4. Term erneut zu berechnen . Aufgrund dieser Tatsache erledigt die rekursive Methode viel redundante Arbeit.

Wie sich herausstellt, ist die zeitliche Komplexität dadurch exponentiell. O (Φn) um genau zu sein.

2.2. Iterative Methode

Bei der iterativen Methode können wir die wiederholten Berechnungen vermeiden, die bei der rekursiven Methode durchgeführt werden. Stattdessen berechnen wir die Terme der Serie und speichern die beiden vorherigen Terme, um die nächsten zu berechnen.

Werfen wir einen Blick auf die Implementierung:

public static int nthFibonacciTerm(int n) { if(n == 0 || n == 1) { return n; } int n0 = 0, n1 = 1; int tempNthTerm; for (int i = 2; i <= n; i++) { tempNthTerm = n0 + n1; n0 = n1; n1 = tempNthTerm; } return n1; }

Zunächst prüfen wir, ob der zu berechnende Term der 0. Term oder der 1. Term ist. In diesem Fall geben wir die Anfangswerte zurück. Ansonsten berechnen wir den 2. Term mit n0 und n1 . Dann modifizieren wir die Werte der Variablen n0 und n1 , um den 1. Term bzw. den 2. Term zu speichern . Wir iterieren so lange, bis wir den erforderlichen Term berechnet haben.

Die iterative Methode vermeidet sich wiederholende Arbeiten, indem die letzten beiden Fibonacci-Terme in Variablen gespeichert werden. Die zeitliche Komplexität und räumliche Komplexität des iterativen Verfahrens beträgt O (n) bzw. O (1) .

2.3. Binets Formel

Wir haben nur die n-te Fibonacci-Zahl in Bezug auf die beiden vorher definiert. Nun werden wir uns Binets Formel ansehen, um die n-te Fibonacci-Zahl in konstanter Zeit zu berechnen .

Die Fibonacci-Begriffe behalten ein Verhältnis bei, das als goldener Schnitt bezeichnet wird und mit Φ bezeichnet wird , dem griechischen Zeichen, das als "Phi" ausgesprochen wird .

Schauen wir uns zunächst an, wie der Goldene Schnitt berechnet wird:

Φ = ( 1 + √5 )/2 = 1.6180339887...

Schauen wir uns nun Binets Formel an :

Sn = Φⁿ–(– Φ⁻ⁿ)/√5

Eigentlich bedeutet dies, dass wir in der Lage sein sollten, die n-te Fibonacci-Zahl mit nur etwas Arithmetik zu erhalten.

Lassen Sie uns dies in Java ausdrücken:

public static int nthFibonacciTerm(int n) { double squareRootOf5 = Math.sqrt(5); double phi = (1 + squareRootOf5)/2; int nthTerm = (int) ((Math.pow(phi, n) - Math.pow(-phi, -n))/squareRootOf5); return nthTerm; }

Wir berechnen zuerst squareRootof5 und phi und speichern sie in Variablen. Später wenden wir die Binet-Formel an, um den erforderlichen Begriff zu erhalten.

Da es sich hier um irrationale Zahlen handelt, erhalten wir nur eine Annäherung. Folglich müssen wir mehr Dezimalstellen für höhere Fibonacci-Zahlen beibehalten, um Rundungsfehler zu berücksichtigen.

Wir sehen, dass die obige Methode den n-ten Fibonacci-Term in konstanter Zeit oder O (1) berechnet .

3. Fazit

In diesem kurzen Artikel haben wir uns die Fibonacci-Serie angesehen. Wir haben uns eine rekursive und eine iterative Lösung angesehen. Dann haben wir die Binet-Formel angewendet, um eine zeitkonstante Lösung zu erstellen.

Wie immer ist der vollständige Quellcode der Arbeitsbeispiele auf GitHub verfügbar.