Itse asiassa kaksi ensimmäistä Fibonacci-lukua ovat ennalta määritettyjä. Ensimmäinen Fibonacci-luku on 0 ja toinen Fibonacci-luku on 1. Nollapohjaisella indeksillä ja olettaen, että Fibonacci-luvut ovat taulukossa, niin:
indeksissä 0 , Fibonacci-luku on 0 , ( ennalta määritetty ) ;indeksissä 1 , Fibonacci-luku on 1 , ( ennalta määritetty ) ;
indeksissä kaksi , Fibonacci-luku on 1 = 1 + 0 , ( määritelmän mukaan ) ;
indeksissä 3 , Fibonacci-luku on kaksi = 1 + 1 , ( määritelmän mukaan ) ;
indeksissä 4 , Fibonacci-luku on 3 = kaksi + 1 , ( määritelmän mukaan ) ;
indeksissä 5 , Fibonacci-luku on 5 = 3 + kaksi , ( määritelmän mukaan ) ;
indeksissä 6 , Fibonacci-luku on 8 = 5 + 3 , ( määritelmän mukaan ) ;
indeksissä 7 , Fibonacci-luku on 13 = 8 + 5 , ( määritelmän mukaan ) ;
indeksissä 8 , Fibonacci-luku on kaksikymmentäyksi = 13 + 8 , ( määritelmän mukaan ) ;
indeksissä 9 , Fibonacci-luku on 3. 4 = kaksikymmentäyksi + 13 , ( määritelmän mukaan ) ;
ja niin edelleen.
Ohjelmoinnissa näiden Fibonacci-lukujen nollaperusteisiin indekseihin käytetään muuttujaa n, ei i:tä. Ja sen myötä ensimmäiset kaksitoista Fibonaccin numeroa ovat:
| 0 | 1 | 1 | kaksi | 3 | 5 | 8 | 13 | kaksikymmentäyksi | 3. 4 | 55 | 89 |
| 0 | 1 | kaksi | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | yksitoista |
Taulukon toisella rivillä on nollapohjaiset indeksit, joista jokaisella olisi ohjelmoinnissa muuttuja n. Ensimmäinen rivi antaa vastaavat Fibonacci-luvut. Joten Fibonacci-luvut eivät ole mitä tahansa numeroita. Ydinmäärittely alkaa 0:lla ensimmäiselle Fibonacci-luvulle ja 1:llä toiselle Fibonacci-luvulle. Loput numerot tuotetaan sieltä.
Fibonacci-luvut voidaan tuottaa O(n) ajassa ja myös O(1) ajassa. O(n) ajalle, jos n on esimerkiksi 12, tuotetaan ensimmäiset kaksitoista Fibonacci-lukua. O(1)-ajalle tuotetaan vain yksi Fibonacci-luku. Esimerkiksi jos n on 6, niin Fibonacci-luku 8 tuotetaan.
Tämä artikkeli selittää nämä kaksi tapaa tuottaa Fibonacci-lukuja Javassa.
Fibonacci-luvun kaava
Fibonacci-luvulle on olemassa matemaattinen kaava. Tämä kaava voidaan kirjoittaa kolmella rivillä tai yhdellä rivillä. Kolmella rivillä se kirjoitetaan seuraavasti:
missä F n on Fibonaccin luku nollaperusteisessa n:ssä th indeksi. Näin Fibonacci-luku määritellään.
Fibonacci-lukujen tuottaminen O(n) ajassa
Jos Fibonacci-luvut tuotetaan O(3) kertaa, luvut 0, 1, 1 tuotetaan; nämä ovat kolme ensimmäistä Fibonaccin numeroa. Viimeinen nollapohjainen n th indeksi tässä on 2. Jos Fibonacci-luvut tuotetaan O(7) kertaa, luvut 0, 1, 1, 2, 3, 5, 8 tuotetaan; nämä ovat ensimmäiset seitsemän Fibonaccin numeroa. Viimeinen nollapohjainen n th indeksi tässä on 6. Jos Fibonacci-luvut tuotetaan O(n) kertaa, luvut, 0, 1, 1, 2, 3, 5, 8 – – -, tuotetaan; nämä ovat ensimmäiset n Fibonacci-lukua. Viimeinen nollapohjainen n th indeksi tässä on n-1.
Luokan Java-menetelmä ensimmäisten n Fibonacci-luvun tuottamiseksi on:
luokkaa Fibonacci {mitätön fibonacci ( int [ ] P ) {
int n = P. pituus ;
jos ( n > 0 )
P [ 0 ] = 0 ;
jos ( n > 1 )
P [ 1 ] = 1 ;
varten ( int i = kaksi ; i < n ; i ++ ) { //n=0 ja n=2 on otettu huomioon
int CurrNo = P [ i - 1 ] + P [ i - kaksi ] ;
P [ i ] = CurrNo ;
}
}
}
Luokka, Fibonacci, on yksityinen. The fibonacci () menetelmä ottaa taulukon P ja palauttaa void. Menetelmä alkaa määrittämällä taulukon pituus. Tämä n:n pituus on tarvittavien Fibonacci-lukujen lukumäärä. Ensimmäinen ja toinen Fibonacci-luku määritetään eksplisiittisesti ja asetetaan taulukon ensimmäiseen ja toiseen paikkaan.
Loput Fibonacci-luvuista alkaen kolmannesta (indeksi, n = 2) määritetään for-silmukassa ja asetetaan paikoilleen taulukossa. Joten funktion on palautettava void. For-silmukan päälause lisää kaksi edellistä numeroa.
Indeksimuuttujaa i on käytetty n:n sijaan selkeyden vuoksi.
Sopiva Java-pääluokka (Java-päämenetelmällä) on:
julkinen luokkaa Main {julkinen staattinen mitätön pää ( merkkijono args [ ] ) {
int m = 12 ;
int [ ] arr = Uusi int [ m ] ;
Fibonacci obj = Uusi Fibonacci ( ) ;
obj. fibonacci ( arr ) ;
varten ( int i = 0 ; i < m ; i ++ )
Järjestelmä . ulos . Tulosta ( arr [ i ] + ' ' ) ;
Järjestelmä . ulos . println ( ) ;
}
}
Kun luvut on tuotettu fibonacci()-menetelmällä, Java-päämenetelmä lukee ne.
Yhden Fibonacci-luvun tuottaminen jatkuvassa ajassa
On olemassa matemaattinen kaava, jolla voidaan tuottaa Fibonacci-luku, kun sille annetaan vastaava nollapohjainen indeksi, n. Kaava on:
missä n on nollaperusteinen indeksi ja Fib n on vastaava Fibonacci-luku. Huomaa, että yhtälön oikealla puolella ei ole 5:n neliöjuuri, joka korotetaan potenssiin n; se on suluissa oleva lauseke, joka nostetaan potenssiin n. Tällaisia ilmaisuja on kaksi.
Jos n on 0, Fib n olisi 0. Jos n on 1, Fib n olisi 1. Jos n on 2, Fib n olisi 1. Jos n on 3, Fib n olisi 2. Jos n on 4, Fib n olisi 3 – ja niin edelleen. Lukija voi tarkistaa tämän kaavan matemaattisesti korvaamalla n:n eri arvoilla ja arvioimalla.
Koodattuna tämä kaava tuottaisi vain yhden Fibonacci-luvun n:lle. Jos tarvitaan useampi kuin yksi Fibonacci-luku, kaavan koodi on kutsuttava kerran jokaiselle vastaavalle indeksille.
Javassa tapa tuottaa vain yksi Fibonacci-luku on:
tuonti java.lang.* ;luokkaa Fib {
kaksinkertainen fibNo ( int n ) {
kaksinkertainen FibN = ( Matematiikka . pow ( ( 1 + Matematiikka . sqrt ( 5 ) ) / kaksi , n ) – Matematiikka . pow ( ( 1 - Matematiikka . sqrt ( 5 ) ) / kaksi , n ) ) / Matematiikka . sqrt ( 5 ) ;
palata FibN ;
}
}
Paketti java.lang.* piti tuoda ohjelman alussa. Tämä johtuu siitä, että paketissa on Math-luokka, jossa on teho (pow) ja neliöjuuri (sqrt) menetelmät. Tässä mukautettu Java-menetelmä toteuttaa matemaattisen kaavan suoraan.
Tämän funktion aikamonimutkaisuus on O(1), yhden pääoperaation vakio kesto. Sopiva Java-pääluokka, jossa on Java-päämenetelmä yllä olevalle menetelmälle, on:
julkinen luokkaa Main {julkinen staattinen mitätön pää ( merkkijono args [ ] ) {
int N = yksitoista ;
Fib obj = Uusi Fib ( ) ;
kaksinkertainen oikein = obj. fibNo ( N ) ;
Järjestelmä . ulos . println ( oikein ) ;
}
}
Indeksi n = 11 lähetetään ja Fibonacci-luku 89 palautetaan. Lähtö on:
89.00000000000003Tarpeettomat desimaaliluvut voidaan poistaa, mutta siitä keskustellaan toisella kertaa.
Johtopäätös
Fibonacci-luvut ovat tietty kokonaislukujen sarja. Saat nykyisen numeron lisäämällä välittömästi edellistä vastaavaa numeroa. Kaksi ensimmäistä Fibonacci-lukua, 0 ja 1, on ennalta ilmoitettu koko sarjalle. Loput Fibonacci-luvut tuotetaan sieltä.
Jos haluat tuottaa Fibonacci-lukuja indeksistä 2, joka vastaa indeksiä n-1, käytä for-silmukkaa päälauseen kanssa:
int CurrNo = P [ i - 1 ] + P [ minä – kaksi ] ;missä currNo on nykyinen Fibonacci-luku ja P on taulukko n luvun tallentamiseen.
Jos haluat tuottaa vain yhden Fibonacci-luvun mistä tahansa nollapohjaisesta indeksistä n, käytä matemaattista kaavaa:
