Faktisk er de to første Fibonacci-tal foruddefinerede. Det første Fibonacci-tal er 0 og det andet Fibonacci-tal er 1. Med nul-baseret indeksering og forudsat at Fibonacci-tal er i en matrix, så:
ved indeks 0 , er Fibonacci-tallet 0 , ( foruddefineret ) ;ved indeks 1 , er Fibonacci-tallet 1 , ( foruddefineret ) ;
ved indeks to , er Fibonacci-tallet 1 = 1 + 0 , ( Per definition ) ;
ved indeks 3 , er Fibonacci-tallet to = 1 + 1 , ( Per definition ) ;
ved indeks 4 , er Fibonacci-tallet 3 = to + 1 , ( Per definition ) ;
ved indeks 5 , er Fibonacci-tallet 5 = 3 + to , ( Per definition ) ;
ved indeks 6 , er Fibonacci-tallet 8 = 5 + 3 , ( Per definition ) ;
ved indeks 7 , er Fibonacci-tallet 13 = 8 + 5 , ( Per definition ) ;
ved indeks 8 , er Fibonacci-tallet enogtyve = 13 + 8 , ( Per definition ) ;
ved indeks 9 , er Fibonacci-tallet 3. 4 = enogtyve + 13 , ( Per definition ) ;
og så videre.
I programmering bruges variablen n, og ikke i til de nul-baserede indekser for disse Fibonacci-tal. Og med det er de første tolv Fibonacci-tal:
| 0 | 1 | 1 | to | 3 | 5 | 8 | 13 | enogtyve | 3. 4 | 55 | 89 |
| 0 | 1 | to | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | elleve |
Den anden række i tabellen giver de nul-baserede indekser, som hver vil have variablen n i programmering. Den første række giver de tilsvarende Fibonacci-tal. Så Fibonacci-tal er ikke hvilke som helst tal. Kernedefinitionen begynder med 0, for det første Fibonacci-tal og 1 for det andet Fibonacci-tal. Resten af numrene er produceret derfra.
Fibonacci-tal kan produceres i O(n)-tid og også i O(1)-tid. For O(n) tid, hvis n er 12 for eksempel, så ville de første tolv Fibonacci-tal blive produceret. For O(1)-tid produceres kun ét Fibonacci-nummer. For eksempel, hvis n er 6, vil Fibonacci-tallet 8 blive produceret.
Denne artikel forklarer disse to måder at producere Fibonacci-tal på i Java.
Formel for et Fibonacci-nummer
Der er en matematisk formel for et Fibonacci-tal. Denne formel kan skrives i tre linjer eller en linje. På tre linjer er det skrevet som:
hvor F n er Fibonacci-tallet ved den nul-baserede n th indeks. Sådan defineres Fibonacci-tallet.
Fremstilling af Fibonacci-tal i O(n)-tid
Hvis Fibonacci-tallene skal produceres i O(3) gange, ville tallene 0, 1, 1 blive produceret; det er de første tre Fibonacci-tal. Den sidste nul-baserede n th indeks her, er 2. Hvis Fibonacci-tallene skal produceres i O(7) gange, ville tallene 0, 1, 1, 2, 3, 5, 8 blive produceret; det er de første syv Fibonacci-tal. Den sidste nul-baserede n th indeks her, er 6. Hvis Fibonacci-tal skal produceres i O(n) gange, ville tallene 0, 1, 1, 2, 3, 5, 8 – – - produceres; det er de første n Fibonacci-tal. Den sidste nul-baserede n th indeks her er n-1.
Java-metoden i en klasse til at producere de første n Fibonacci-tal er:
klasse Fibonacci {ugyldig fibonacci ( int [ ] P ) {
int n = P. længde ;
hvis ( n > 0 )
P [ 0 ] = 0 ;
hvis ( n > 1 )
P [ 1 ] = 1 ;
til ( int jeg = to ; jeg < n ; jeg ++ ) { //n=0 og n=2 er blevet overvejet
int currNo = P [ jeg - 1 ] + P [ jeg - to ] ;
P [ jeg ] = currNo ;
}
}
}
Klassen Fibonacci er privat. Det fibonacci() metode tager arrayet P og returnerer void. Metoden begynder med at bestemme længden af arrayet. Denne længde på n er antallet af Fibonacci-tal, der kræves. Det første og andet Fibonacci-tal bestemmes eksplicit og sættes i den første og anden position i arrayet.
Resten af Fibonacci-tallene begyndende fra den tredje (indeks, n = 2) bestemmes i en for-løkke og sættes i deres positioner i arrayet. Så funktionen skal returnere ugyldig. Hovedsætningen i for-løkken tilføjer de to foregående tal.
Indeksvariablen, i, er blevet brugt i stedet for n, for overskuelighedens skyld.
En passende Java Main-klasse (med Java-hovedmetoden) er:
offentlig klasse Hoved {offentlig statisk ugyldig vigtigste ( Snor args [ ] ) {
int m = 12 ;
int [ ] arr = ny int [ m ] ;
Fibonacci obj = ny Fibonacci ( ) ;
obj. fibonacci ( arr ) ;
til ( int jeg = 0 ; jeg < m ; jeg ++ )
System . ud . Print ( arr [ jeg ] + ' ' ) ;
System . ud . println ( ) ;
}
}
Efter at tallene er blevet produceret med fibonacci()-metoden, læser Java-hovedmetoden dem op.
Producerer ét Fibonacci-nummer i konstant tid
Der er en matematisk formel, der kan bruges til at producere et Fibonacci-tal, når det gives det tilsvarende nul-baserede indeks, n. Formlen er:
hvor n er det nul-baserede indeks og Fib n er det tilsvarende Fibonacci-tal. Bemærk, at på højre side af ligningen er det ikke kvadratroden af 5, der hæves til potensen n; det er udtrykket i parentes, der hæves til potensen n. Der er to af sådanne udtryk.
Hvis n er 0, Fib n ville være 0. Hvis n er 1, Fib n ville være 1. Hvis n er 2, Fib n ville være 1. Hvis n er 3, Fib n ville være 2. Hvis n er 4, Fib n ville være 3 – og så videre. Læseren kan verificere denne formel matematisk ved at erstatte n med forskellige værdier og evaluere.
Når den er kodet, vil denne formel kun producere ét Fibonacci-tal for n. Hvis der kræves mere end ét Fibonacci-nummer, skal koden til formlen kaldes én gang for hvert af de forskellige tilsvarende indekser.
I Java er metoden til kun at producere ét Fibonacci-nummer:
importere java.lang.* ;klasse Fib {
dobbelt fibNr ( int n ) {
dobbelt FibN = ( Matematik . pow ( ( 1 + Matematik . sqrt ( 5 ) ) / to n ) – Matematik . pow ( ( 1 - Matematik . sqrt ( 5 ) ) / to n ) ) / Matematik . sqrt ( 5 ) ;
Vend tilbage FibN ;
}
}
Java.lang.*-pakken skulle importeres i begyndelsen af programmet. Dette skyldes, at pakken har Math-klassen, som har metoderne power (pow) og kvadratrod (sqrt). Den tilpassede Java-metode implementerer her den matematiske formel direkte.
Tidskompleksiteten for denne funktion er O(1), konstant tamning af en hovedoperation. En passende Java Main-klasse med Java-hovedmetode til ovenstående metode er:
offentlig klasse Hoved {offentlig statisk ugyldig vigtigste ( Snor args [ ] ) {
int N = elleve ;
Fib obj = ny Fib ( ) ;
dobbelt ret = obj. fibNr ( N ) ;
System . ud . println ( ret ) ;
}
}
Indekset n = 11 sendes, og Fibonacci-tallet, 89, returneres. Udgangen er:
89.00000000000003De unødvendige decimaler kan fjernes, men det er en diskussion til en anden gang.
Konklusion
Fibonacci-tal er en bestemt sekvens af hele tal. For at få det aktuelle nummer skal du tilføje de umiddelbart foregående to tilsvarende tal. De første to Fibonacci-tal, 0 efterfulgt af 1, er forud-erklæret for hele sekvensen. Resten af Fibonacci-numrene er produceret derfra.
For at producere Fibonacci-tal fra indeks 2 til det, der svarer til indeks n-1, skal du bruge en for-løkke med hovedsætningen:
int currNo = P [ jeg - 1 ] + P [ jeg – to ] ;hvor currNo er det aktuelle Fibonacci-tal og P er arrayet til at gemme de n tal.
For kun at producere ét Fibonacci-tal ud fra et nul-baseret indeks n, skal du bruge den matematiske formel:
