Tegelikult on kaks esimest Fibonacci numbrit eelnevalt määratletud. Esimene Fibonacci arv on 0 ja teine Fibonacci arv on 1. Nullpõhise indekseerimise korral ja eeldades, et Fibonacci numbrid on massiivis, siis:
indeksi juures 0 , on Fibonacci arv 0 , ( eelmääratletud ) ;indeksi juures 1 , on Fibonacci arv 1 , ( eelmääratletud ) ;
indeksi juures kaks , on Fibonacci arv 1 = 1 + 0 , ( definitsiooni järgi ) ;
indeksi juures 3 , on Fibonacci arv kaks = 1 + 1 , ( definitsiooni järgi ) ;
indeksi juures 4 , on Fibonacci arv 3 = kaks + 1 , ( definitsiooni järgi ) ;
indeksi juures 5 , on Fibonacci arv 5 = 3 + kaks , ( definitsiooni järgi ) ;
indeksi juures 6 , on Fibonacci arv 8 = 5 + 3 , ( definitsiooni järgi ) ;
indeksi juures 7 , on Fibonacci arv 13 = 8 + 5 , ( definitsiooni järgi ) ;
indeksi juures 8 , on Fibonacci arv kakskümmend üks = 13 + 8 , ( definitsiooni järgi ) ;
indeksi juures 9 , on Fibonacci arv 3. 4 = kakskümmend üks + 13 , ( definitsiooni järgi ) ;
ja nii edasi.
Programmeerimisel kasutatakse nende Fibonacci numbrite nullpõhiste indeksite jaoks muutujat n, mitte i. Ja sellega on esimesed kaksteist Fibonacci numbrit:
| 0 | 1 | 1 | kaks | 3 | 5 | 8 | 13 | kakskümmend üks | 3. 4 | 55 | 89 |
| 0 | 1 | kaks | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | üksteist |
Tabeli teisel real on nullpõhised indeksid, millest igaühel oleks programmeerimisel muutuja n. Esimene rida annab vastavad Fibonacci numbrid. Niisiis, Fibonacci numbrid ei ole lihtsalt suvalised numbrid. Tuuma määratlus algab 0-ga esimese Fibonacci arvu ja 1-ga teise Fibonacci arvu puhul. Ülejäänud numbrid toodetakse sealt.
Fibonacci arve saab toota O(n) aja ja ka O(1) aja jooksul. O(n) aja puhul, kui n on näiteks 12, saadakse esimesed kaksteist Fibonacci arvu. O(1) aja jaoks saadakse ainult üks Fibonacci arv. Näiteks kui n on 6, siis saadakse Fibonacci arv 8.
See artikkel selgitab neid kahte viisi Fibonacci numbrite loomiseks Javas.
Fibonacci arvu valem
Fibonacci arvu jaoks on olemas matemaatiline valem. Selle valemi saab kirjutada kolmes reas või ühes reas. Kolmes reas on see kirjutatud järgmiselt:
kus F n on Fibonacci arv nullipõhise n juures th indeks. Nii defineeritakse Fibonacci arv.
Fibonacci arvude tootmine O(n) ajas
Kui Fibonacci arvud genereerida O(3) korda, saadakse arvud 0, 1, 1; need on kolm esimest Fibonacci numbrit. Viimane nullipõhine n th indeks siin on 2. Kui Fibonacci arvud genereerida O(7) korda, saadakse arvud 0, 1, 1, 2, 3, 5, 8; need on esimesed seitse Fibonacci numbrit. Viimane nullipõhine n th indeks siin on 6. Kui Fibonacci arvud genereerida O(n) korda, saadakse arvud 0, 1, 1, 2, 3, 5, 8 – – -; need on esimesed n Fibonacci numbrit. Viimane nullipõhine n th indeks siin on n-1.
Java-meetod klassis esimese n Fibonacci numbri saamiseks on järgmine:
klass Fibonacci {tühine fibonacci ( int [ ] P ) {
int n = P. pikkus ;
kui ( n > 0 )
P [ 0 ] = 0 ;
kui ( n > 1 )
P [ 1 ] = 1 ;
jaoks ( int i = kaks ; i < n ; i ++ ) { //n=0 ja n=2 on arvesse võetud
int CurrNo = P [ i - 1 ] + P [ i - kaks ] ;
P [ i ] = CurrNo ;
}
}
}
Klass, Fibonacci, on privaatne. The fibonacci () meetod võtab massiivi P ja tagastab void. Meetod algab massiivi pikkuse määramisega. See n pikkus on vajalike Fibonacci arvude arv. Esimene ja teine Fibonacci arv määratakse selgesõnaliselt ja asetatakse massiivi esimesse ja teise positsiooni.
Ülejäänud Fibonacci arvud, mis algavad kolmandast (indeks, n = 2), määratakse for-tsüklis ja asetatakse nende asukohtadesse massiivi. Seega peab funktsioon tühiseks tagastama. For-tsükli põhilause lisab kaks eelmist arvu.
Selguse huvides on n asemel kasutatud indeksi muutujat i.
Sobiv Java põhiklass (Java põhimeetodiga) on:
avalik klass Peamine {avalik staatiline tühine peamine ( String args [ ] ) {
int m = 12 ;
int [ ] arr = uus int [ m ] ;
Fibonacci obj = uus Fibonacci ( ) ;
obj. fibonacci ( arr ) ;
jaoks ( int i = 0 ; i < m ; i ++ )
Süsteem . välja . printida ( arr [ i ] + ' ' ) ;
Süsteem . välja . println ( ) ;
}
}
Kui arvud on fibonacci() meetodiga loodud, loeb Java põhimeetod need ette.
Ühe Fibonacci numbri tootmine pideva aja jooksul
On olemas matemaatiline valem, mida saab kasutada Fibonacci arvu saamiseks, kui sellele on antud vastav nullipõhine indeks n. Valem on:
kus n on nullipõhine indeks ja Fib n on vastav Fibonacci arv. Pange tähele, et võrrandi paremal küljel ei ole 5 ruutjuur, mis on tõstetud astmeni n; see on sulgudes olev avaldis, mis tõstetakse astmeni n. Selliseid väljendeid on kaks.
Kui n on 0, siis Fib n oleks 0. Kui n on 1, siis Fib n oleks 1. Kui n on 2, siis Fib n oleks 1. Kui n on 3, siis Fib n oleks 2. Kui n on 4, Fib n oleks 3 – ja nii edasi. Lugeja saab seda valemit matemaatiliselt kontrollida, asendades n-i erinevate väärtustega ja hinnates.
Kodeerituna annaks see valem n jaoks ainult ühe Fibonacci arvu. Kui nõutakse rohkem kui ühte Fibonacci numbrit, tuleb valemi kood välja kutsuda üks kord iga erineva vastava indeksi jaoks.
Javas on meetod ainult ühe Fibonacci numbri saamiseks:
importida java.lang.* ;klass Fib {
kahekordne fibNo ( int n ) {
kahekordne FibN = ( matemaatika . pow ( ( 1 + matemaatika . sqrt ( 5 ) ) / kaks , n ) – matemaatika . pow ( ( 1 - matemaatika . sqrt ( 5 ) ) / kaks , n ) ) / matemaatika . sqrt ( 5 ) ;
tagasi FibN ;
}
}
Programmi alguses tuli importida pakett java.lang.*. Seda seetõttu, et paketil on matemaatikaklass, millel on võimsuse (pow) ja ruutjuure (sqrt) meetodid. Kohandatud Java-meetod rakendab matemaatika valemit otse.
Selle funktsiooni ajaline keerukus on O(1), ühe põhitehte konstantne taltsutamine. Ülaltoodud meetodi jaoks sobiv Java põhiklass koos Java põhimeetodiga on:
avalik klass Peamine {avalik staatiline tühine peamine ( String args [ ] ) {
int N = üksteist ;
Fib obj = uus Fib ( ) ;
kahekordne õige = obj. fibNo ( N ) ;
Süsteem . välja . println ( õige ) ;
}
}
Indeks n = 11 saadetakse ja Fibonacci arv 89 tagastatakse. Väljund on:
89.00000000000003Mittevajalikud kümnendkohad saab eemaldada, kuid see on mõne muu korra arutelu.
Järeldus
Fibonacci numbrid on teatud täisarvude jada. Praeguse numbri saamiseks lisage vahetult eelnevad kaks vastavat numbrit. Esimesed kaks Fibonacci numbrit, 0, millele järgneb 1, on kogu jada jaoks eelnevalt deklareeritud. Ülejäänud Fibonacci numbrid toodetakse sealt.
Fibonacci arvude saamiseks indeksist 2 numbrini, mis vastab indeksile n-1, kasutage for-tsüklit koos põhilausega:
int CurrNo = P [ i - 1 ] + P [ mina – kaks ] ;kus currNo on praegune Fibonacci arv ja P on massiiv n arvu salvestamiseks.
Mis tahes nullpõhisest indeksist n ainult ühe Fibonacci arvu saamiseks kasutage matemaatilist valemit:
