Tatsächlich sind die ersten beiden Fibonacci-Zahlen vordefiniert. Die erste Fibonacci-Zahl ist 0 und die zweite Fibonacci-Zahl ist 1. Mit nullbasierter Indizierung und der Annahme, dass sich Fibonacci-Zahlen in einem Array befinden, dann:
am Index 0 , die Fibonacci-Zahl ist 0 , ( vordefiniert ) ;am Index 1 , die Fibonacci-Zahl ist 1 , ( vordefiniert ) ;
am Index zwei , die Fibonacci-Zahl ist 1 = 1 + 0 , ( per Definition ) ;
am Index 3 , die Fibonacci-Zahl ist zwei = 1 + 1 , ( per Definition ) ;
am Index 4 , die Fibonacci-Zahl ist 3 = zwei + 1 , ( per Definition ) ;
am Index 5 , die Fibonacci-Zahl ist 5 = 3 + zwei , ( per Definition ) ;
am Index 6 , die Fibonacci-Zahl ist 8 = 5 + 3 , ( per Definition ) ;
am Index 7 , die Fibonacci-Zahl ist 13 = 8 + 5 , ( per Definition ) ;
am Index 8 , die Fibonacci-Zahl ist einundzwanzig = 13 + 8 , ( per Definition ) ;
am Index 9 , die Fibonacci-Zahl ist 3. 4 = einundzwanzig + 13 , ( per Definition ) ;
usw.
Bei der Programmierung wird die Variable n und nicht i für die nullbasierten Indizes für diese Fibonacci-Zahlen verwendet. Und damit lauten die ersten zwölf Fibonacci-Zahlen:
| 0 | 1 | 1 | zwei | 3 | 5 | 8 | 13 | einundzwanzig | 3. 4 | 55 | 89 |
| 0 | 1 | zwei | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | elf |
Die zweite Zeile in der Tabelle gibt die nullbasierten Indizes an, von denen jeder die Variable n in der Programmierung haben würde. Die erste Reihe gibt die entsprechenden Fibonacci-Zahlen an. Fibonacci-Zahlen sind also nicht irgendwelche Zahlen. Die Kerndefinition beginnt mit 0 für die erste Fibonacci-Zahl und 1 für die zweite Fibonacci-Zahl. Der Rest der Nummern wird von dort produziert.
Fibonacci-Zahlen können in O(n)-Zeit und auch in O(1)-Zeit erzeugt werden. Für die Zeit O(n), wenn n beispielsweise 12 ist, würden die ersten zwölf Fibonacci-Zahlen erzeugt. Für die Zeit O(1) wird nur eine Fibonacci-Zahl erzeugt. Wenn zum Beispiel n 6 ist, dann würde die Fibonacci-Zahl 8 produziert werden.
Dieser Artikel erklärt diese beiden Möglichkeiten, Fibonacci-Zahlen in Java zu erzeugen.
Formel für eine Fibonacci-Zahl
Es gibt eine mathematische Formel für eine Fibonacci-Zahl. Diese Formel kann in drei Zeilen oder in einer Zeile geschrieben werden. In drei Zeilen wird es geschrieben als:
wo f n ist die Fibonacci-Zahl beim nullbasierten n th Index. So ist die Fibonacci-Zahl definiert.
Produzieren von Fibonacci-Zahlen in O(n)-Zeit
Wenn Fibonacci-Zahlen in O(3)-mal erzeugt werden sollen, würden die Zahlen 0, 1, 1 erzeugt werden; das sind die ersten drei Fibonacci-Zahlen. Das letzte nullbasierte n th Index ist hier 2. Wenn Fibonacci-Zahlen in O(7)-mal erzeugt werden sollen, würden die Zahlen 0, 1, 1, 2, 3, 5, 8 erzeugt; das sind die ersten sieben Fibonacci-Zahlen. Das letzte nullbasierte n th Index ist hier 6. Wenn Fibonacci-Zahlen in O(n)-mal erzeugt werden sollen, würden die Zahlen 0, 1, 1, 2, 3, 5, 8 – – - erzeugt; das sind die ersten n Fibonacci-Zahlen. Das letzte nullbasierte n th Index ist hier n-1.
Die Java-Methode in einer Klasse zum Erzeugen der ersten n Fibonacci-Zahlen lautet:
Klasse Fibonacci {Leere fibonacci ( int [ ] P ) {
int n = P. Länge ;
wenn ( n > 0 )
P [ 0 ] = 0 ;
wenn ( n > 1 )
P [ 1 ] = 1 ;
zum ( int ich = zwei ; ich < n ; ich ++ ) { //n=0 und n=2 wurden berücksichtigt
int aktuelleNr = P [ ich - 1 ] + P [ ich - zwei ] ;
P [ ich ] = aktuelleNr ;
}
}
}
Die Klasse Fibonacci ist privat. Das fibonacci() Die Methode nimmt das Array P und gibt void zurück. Das Verfahren beginnt mit der Bestimmung der Länge des Arrays. Diese Länge von n ist die Anzahl der erforderlichen Fibonacci-Zahlen. Die erste und zweite Fibonacci-Zahl werden explizit bestimmt und an die erste und zweite Position im Array gesetzt.
Die restlichen Fibonacci-Zahlen ab der dritten (Index, n = 2) werden in einer for-Schleife ermittelt und an ihren Positionen im Array abgelegt. Die Funktion muss also void zurückgeben. Die Hauptanweisung in der for-Schleife addiert die beiden vorherigen Zahlen.
Der Übersichtlichkeit halber wurde anstelle von n die Indexvariable i verwendet.
Eine geeignete Java-Hauptklasse (mit der Java-Hauptmethode) ist:
Öffentlichkeit Klasse Hauptsächlich {Öffentlichkeit statisch Leere hauptsächlich ( Schnur Argumente [ ] ) {
int m = 12 ;
int [ ] Arr = Neu int [ m ] ;
Fibonacci-Obj = Neu Fibonacci ( ) ;
obj. fibonacci ( Arr ) ;
zum ( int ich = 0 ; ich < m ; ich ++ )
System . aus . drucken ( Arr [ ich ] + ' ' ) ;
System . aus . println ( ) ;
}
}
Nachdem die Zahlen durch die Methode fibonacci() erzeugt wurden, liest die Java-Hauptmethode sie aus.
Produzieren einer Fibonacci-Zahl in konstanter Zeit
Es gibt eine mathematische Formel, die verwendet werden kann, um eine Fibonacci-Zahl zu erzeugen, wenn der entsprechende nullbasierte Index n gegeben ist. Die Formel lautet:
wobei n der nullbasierte Index und Fib n ist die entsprechende Fibonacci-Zahl. Beachten Sie, dass auf der rechten Seite der Gleichung nicht die Quadratwurzel von 5 mit n potenziert wird; es ist der Ausdruck in Klammern, der mit n potenziert wird. Es gibt zwei solcher Ausdrücke.
Wenn n 0 ist, Fib n wäre 0. Wenn n 1 ist, Fib n wäre 1. Wenn n 2 ist, Fib n wäre 1. Wenn n 3 ist, Fib n wäre 2. Wenn n 4 ist, Fib n wäre 3 – und so weiter. Der Leser kann diese Formel mathematisch überprüfen, indem er verschiedene Werte für n einsetzt und auswertet.
Bei der Codierung würde diese Formel nur eine Fibonacci-Zahl für n ergeben. Wenn mehr als eine Fibonacci-Zahl benötigt wird, muss der Code für die Formel einmal für jeden der verschiedenen entsprechenden Indizes aufgerufen werden.
In Java ist die Methode, um nur eine Fibonacci-Zahl zu erzeugen, wie folgt:
importieren java.lang.* ;Klasse Flunkerei {
doppelt fibNr ( int n ) {
doppelt FibN = ( Mathematik . pow ( ( 1 + Mathematik . quadrat ( 5 ) ) / zwei , n ) – Mathematik . pow ( ( 1 - Mathematik . quadrat ( 5 ) ) / zwei , n ) ) / Mathematik . quadrat ( 5 ) ;
Rückkehr FibN ;
}
}
Das Paket java.lang.* musste zu Beginn des Programms importiert werden. Das liegt daran, dass das Paket über die Math-Klasse verfügt, die über die Methoden Potenz (pow) und Quadratwurzel (sqrt) verfügt. Die benutzerdefinierte Java-Methode hier implementiert die mathematische Formel direkt.
Die Zeitkomplexität für diese Funktion ist O(1), konstante Zahl einer Hauptoperation. Eine geeignete Java-Hauptklasse mit Java-Hauptmethode für die obige Methode ist:
Öffentlichkeit Klasse Hauptsächlich {Öffentlichkeit statisch Leere hauptsächlich ( Schnur Argumente [ ] ) {
int N = elf ;
Fib-Obj = Neu Flunkerei ( ) ;
doppelt Rechts = obj. fibNr ( N ) ;
System . aus . println ( Rechts ) ;
}
}
Der Index n = 11 wird gesendet und die Fibonacci-Zahl 89 zurückgegeben. Die Ausgabe ist:
89.00000000000003Die unnötigen Dezimalstellen können entfernt werden, aber das ist eine Diskussion für ein anderes Mal.
Fazit
Fibonacci-Zahlen sind eine bestimmte Folge ganzer Zahlen. Um die aktuelle Nummer zu erhalten, addieren Sie die unmittelbar vorhergehenden zwei entsprechenden Nummern. Die ersten beiden Fibonacci-Zahlen, 0 gefolgt von 1, sind für die gesamte Sequenz vordeklariert. Der Rest der Fibonacci-Zahlen wird von dort erzeugt.
Um Fibonacci-Zahlen von Index 2 zu dem zu erzeugen, der Index n-1 entspricht, verwenden Sie eine for-Schleife mit der Hauptanweisung:
int aktuelleNr = P [ ich - 1 ] + P [ ich - zwei ] ;wobei currNo die aktuelle Fibonacci-Zahl und P das Array zum Speichern der n Zahlen ist.
Um nur eine Fibonacci-Zahl aus einem beliebigen nullbasierten Index n zu erzeugen, verwenden Sie die mathematische Formel:
