In feite zijn de eerste twee Fibonacci-getallen vooraf gedefinieerd. Het eerste Fibonacci-getal is 0 en het tweede Fibonacci-getal is 1. Met op nul gebaseerde indexering en ervan uitgaande dat Fibonacci-getallen in een array staan, dan:
bij index 0 , het Fibonacci-getal is 0 , ( voorgedefinieerd ) ;bij index 1 , het Fibonacci-getal is 1 , ( voorgedefinieerd ) ;
bij index twee , het Fibonacci-getal is 1 = 1 + 0 , ( per definitie ) ;
bij index 3 , het Fibonacci-getal is twee = 1 + 1 , ( per definitie ) ;
bij index 4 , het Fibonacci-getal is 3 = twee + 1 , ( per definitie ) ;
bij index 5 , het Fibonacci-getal is 5 = 3 + twee , ( per definitie ) ;
bij index 6 , het Fibonacci-getal is 8 = 5 + 3 , ( per definitie ) ;
bij index 7 , het Fibonacci-getal is 13 = 8 + 5 , ( per definitie ) ;
bij index 8 , het Fibonacci-getal is eenentwintig = 13 + 8 , ( per definitie ) ;
bij index 9 , het Fibonacci-getal is 3. 4 = eenentwintig + 13 , ( per definitie ) ;
enzovoort.
Bij het programmeren wordt de variabele n, en niet i, gebruikt voor de op nul gebaseerde indexen voor deze Fibonacci-getallen. En daarmee zijn de eerste twaalf Fibonacci-getallen:
| 0 | 1 | 1 | twee | 3 | 5 | 8 | 13 | eenentwintig | 3. 4 | 55 | 89 |
| 0 | 1 | twee | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | elf |
De tweede rij in de tabel geeft de op nul gebaseerde indexen, die elk de variabele n zouden hebben bij het programmeren. De eerste rij geeft de bijbehorende Fibonacci-getallen. Fibonacci-getallen zijn dus niet zomaar getallen. De kerndefinitie begint met 0, voor het eerste Fibonacci-getal en 1 voor het tweede Fibonacci-getal. Van daaruit worden de overige nummers geproduceerd.
Fibonacci-getallen kunnen worden geproduceerd in O(n)-tijd en ook in O(1)-tijd. Voor O(n)-tijd, als n bijvoorbeeld 12 is, zouden de eerste twaalf Fibonacci-getallen worden geproduceerd. Voor O(1) tijd wordt slechts één Fibonacci-getal geproduceerd. Als n bijvoorbeeld 6 is, wordt het Fibonacci-getal 8 geproduceerd.
Dit artikel legt deze twee manieren uit om Fibonacci-getallen in Java te produceren.
Formule voor een Fibonacci-getal
Er is een wiskundige formule voor een Fibonacci-getal. Deze formule kan in drie regels of in één regel worden geschreven. In drie regels wordt het geschreven als:
waar F n is het Fibonacci-getal op de op nul gebaseerde n e inhoudsopgave. Dit is hoe het Fibonacci-getal wordt gedefinieerd.
Fibonacci-getallen produceren in O(n)-tijd
Als Fibonacci-getallen in O (3) tijden moeten worden geproduceerd, zouden de getallen 0, 1, 1 worden geproduceerd; dat zijn de eerste drie Fibonacci-getallen. De laatste op nul gebaseerde n e index hier, is 2. Als Fibonacci-getallen in O (7) keer moeten worden geproduceerd, zouden de getallen 0, 1, 1, 2, 3, 5, 8 worden geproduceerd; dat zijn de eerste zeven Fibonacci-getallen. De laatste op nul gebaseerde n e index hier is 6. Als Fibonacci-getallen in O(n)-tijden moeten worden geproduceerd, zouden de getallen 0, 1, 1, 2, 3, 5, 8 – – - worden geproduceerd; dat zijn de eerste n Fibonacci-getallen. De laatste op nul gebaseerde n e index hier is n-1.
De Java-methode in een klasse om de eerste n Fibonacci-getallen te produceren is:
klas Fibonacci {leegte fibonacci ( int [ ] P ) {
int n = P. lengte ;
als ( n > 0 )
P [ 0 ] = 0 ;
als ( n > 1 )
P [ 1 ] = 1 ;
voor ( int i = twee ; i < n ; i ++ ) { //n=0 en n=2 zijn overwogen
int currNee = P [ i - 1 ] + P [ i - twee ] ;
P [ i ] = currNee ;
}
}
}
De klas, Fibonacci is privé. De fibonacci() methode neemt de array P en retourneert void. De methode begint met het bepalen van de lengte van de array. Deze lengte van n is het aantal benodigde Fibonacci-getallen. De eerste en tweede Fibonacci-getallen worden expliciet bepaald en op de eerste en tweede positie in de array geplaatst.
De rest van de Fibonacci-getallen beginnend bij de derde (index, n = 2) worden bepaald in een for-lus en op hun posities in de array gezet. De functie moet dus void retourneren. De principal-instructie in de for-lus voegt de vorige twee getallen toe.
Voor de duidelijkheid is de indexvariabele i gebruikt in plaats van n.
Een geschikte Java Main-klasse (met de Java-hoofdmethode) is:
openbaar klas Hoofd {openbaar statisch leegte hoofd ( Snaar argumenten [ ] ) {
int m = 12 ;
int [ ] arr = nieuwe int [ m ] ;
Fibonacci obj = nieuwe Fibonacci ( ) ;
obj. fibonacci ( arr ) ;
voor ( int i = 0 ; i < m ; i ++ )
Systeem . uit . afdrukken ( arr [ i ] + ' ' ) ;
Systeem . uit . println ( ) ;
}
}
Nadat de getallen zijn geproduceerd door de fibonacci()-methode, leest de Java-hoofdmethode ze voor.
Eén Fibonacci-getal produceren in constante tijd
Er is een wiskundige formule die kan worden gebruikt om een Fibonacci-getal te produceren, wanneer de bijbehorende op nul gebaseerde index, n, wordt gegeven. De formule is:
waarbij n de op nul gebaseerde index is en Fib n is het corresponderende Fibonacci-getal. Merk op dat aan de rechterkant van de vergelijking niet de vierkantswortel van 5 wordt verheven tot de macht n; het is de uitdrukking tussen haakjes die wordt verheven tot de macht n. Er zijn twee van dergelijke uitdrukkingen.
Als n 0 is, Fib n zou 0 zijn. Als n 1 is, Fib n zou zijn 1. Als n 2 is, Fib n zou zijn 1. Als n 3 is, Fib n zou 2 zijn. Als n 4 is, Fib n zou 3 zijn - enzovoort. De lezer kan deze formule wiskundig verifiëren door verschillende waarden voor n te vervangen en te evalueren.
Wanneer gecodeerd, zou deze formule slechts één Fibonacci-getal voor n opleveren. Als er meer dan één Fibonacci-nummer nodig is, moet de code voor de formule één keer worden aangeroepen voor elk van de verschillende overeenkomstige indexen.
In Java is de methode om slechts één Fibonacci-getal te produceren:
importeren java.lang.* ;klas Jokken {
dubbele fibNee ( int n ) {
dubbele FibN = ( Wiskunde . pow ( ( 1 + Wiskunde . sqrt ( 5 ) ) / twee , n ) – Wiskunde . pow ( ( 1 - Wiskunde . sqrt ( 5 ) ) / twee , n ) ) / Wiskunde . sqrt ( 5 ) ;
opbrengst FibN ;
}
}
Het pakket java.lang.* moest aan het begin van het programma worden geïmporteerd. Dit komt omdat het pakket de klasse Math heeft, die de methoden power (pow) en vierkantswortel (sqrt) heeft. De aangepaste Java-methode implementeert hier de wiskundige formule rechtstreeks.
De tijdcomplexiteit voor deze functie is O(1), constant tam van één hoofdbewerking. Een geschikte Java Main-klasse, met Java-hoofdmethode voor de bovenstaande methode is:
openbaar klas Hoofd {openbaar statisch leegte hoofd ( Snaar argumenten [ ] ) {
int N = elf ;
Fib obj = nieuwe Jokken ( ) ;
dubbele Rechtsaf = obj. fibNee ( N ) ;
Systeem . uit . println ( Rechtsaf ) ;
}
}
De index n = 11 wordt verzonden en het Fibonacci-getal, 89 wordt geretourneerd. De uitvoer is:
89.00000000000003De overbodige decimale cijfers kunnen worden verwijderd, maar dat is een discussie voor een andere keer.
Conclusie
Fibonacci-getallen zijn een bepaalde reeks hele getallen. Om het huidige nummer te verkrijgen, voegt u de twee onmiddellijk voorafgaande corresponderende nummers toe. De eerste twee Fibonacci-getallen, 0 gevolgd door 1, zijn vooraf gedeclareerd, voor de hele reeks. De rest van de Fibonacci-getallen worden van daaruit geproduceerd.
Om Fibonacci-getallen te produceren van index 2 naar die welke overeenkomt met index n-1, gebruikt u een for-lus met de hoofdopdracht:
int currNee = P [ i - 1 ] + P [ i - twee ] ;waarbij currNo het huidige Fibonacci-getal is en P de array is om de n-getallen op te slaan.
Gebruik de wiskundige formule om slechts één Fibonacci-getal te produceren uit een op nul gebaseerde index n:
