Tiesą sakant, pirmieji du Fibonačio skaičiai yra iš anksto nustatyti. Pirmasis Fibonačio skaičius yra 0, o antrasis Fibonačio skaičius yra 1. Indeksuojant nuliu pagrindu ir darant prielaidą, kad Fibonačio skaičiai yra masyve, tada:
prie indekso 0 , Fibonačio skaičius yra 0 , ( iš anksto nustatytas ) ;prie indekso 1 , Fibonačio skaičius yra 1 , ( iš anksto nustatytas ) ;
prie indekso du , Fibonačio skaičius yra 1 = 1 + 0 , ( pagal apibrėžimą ) ;
prie indekso 3 , Fibonačio skaičius yra du = 1 + 1 , ( pagal apibrėžimą ) ;
prie indekso 4 , Fibonačio skaičius yra 3 = du + 1 , ( pagal apibrėžimą ) ;
prie indekso 5 , Fibonačio skaičius yra 5 = 3 + du , ( pagal apibrėžimą ) ;
prie indekso 6 , Fibonačio skaičius yra 8 = 5 + 3 , ( pagal apibrėžimą ) ;
prie indekso 7 , Fibonačio skaičius yra 13 = 8 + 5 , ( pagal apibrėžimą ) ;
prie indekso 8 , Fibonačio skaičius yra dvidešimt vienas = 13 + 8 , ( pagal apibrėžimą ) ;
prie indekso 9 , Fibonačio skaičius yra 3. 4 = dvidešimt vienas + 13 , ( pagal apibrėžimą ) ;
ir taip toliau.
Programuojant kintamasis n, o ne i naudojamas šių Fibonačio skaičių nuliniams indeksams. Taigi pirmieji dvylika Fibonačio skaičių yra:
| 0 | 1 | 1 | du | 3 | 5 | 8 | 13 | dvidešimt vienas | 3. 4 | 55 | 89 |
| 0 | 1 | du | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | vienuolika |
Antroje lentelės eilutėje pateikiami nuliu pagrįsti indeksai, kurių kiekvienas programuojant turėtų kintamąjį n. Pirmoje eilutėje pateikiami atitinkami Fibonačio skaičiai. Taigi, Fibonačio skaičiai nėra bet kokie skaičiai. Pagrindinis apibrėžimas prasideda 0, jei tai pirmasis Fibonačio skaičius, o 1 - antrasis Fibonačio skaičius. Likę numeriai gaunami iš ten.
Fibonačio skaičiai gali būti sukurti per O (n) laiką ir O (1) laiką. O (n) laikui, jei, pavyzdžiui, n yra 12, tada būtų sukurti pirmieji dvylika Fibonačio skaičių. O (1) laikui sukuriamas tik vienas Fibonačio skaičius. Pavyzdžiui, jei n yra 6, tada būtų gautas Fibonačio skaičius 8.
Šiame straipsnyje paaiškinami šie du Fibonačio numerių kūrimo Java programoje būdai.
Fibonačio skaičiaus formulė
Yra matematinė Fibonačio skaičiaus formulė. Šią formulę galima parašyti trimis eilutėmis arba viena eilute. Trimis eilutėmis jis parašytas taip:
kur F n yra Fibonačio skaičius ties nuliu pagrįstu n th indeksas. Taip apibrėžiamas Fibonačio skaičius.
Fibonačio skaičių generavimas per O(n) laiką
Jei Fibonačio skaičiai turi būti sudaryti iš O(3) kartų, būtų sudaryti skaičiai 0, 1, 1; tai yra pirmieji trys Fibonačio skaičiai. Paskutinis nulinis n th indeksas čia yra 2. Jei Fibonačio skaičiai turi būti sudaryti O(7) kartų, būtų gauti skaičiai 0, 1, 1, 2, 3, 5, 8; tai yra pirmieji septyni Fibonačio skaičiai. Paskutinis nulinis n th indeksas čia yra 6. Jei Fibonačio skaičiai būtų pagaminti O(n) kartų, būtų gauti skaičiai 0, 1, 1, 2, 3, 5, 8 – – -; tai yra pirmieji n Fibonačio skaičiai. Paskutinis nulinis n th indeksas čia yra n-1.
„Java“ metodas klasėje pirmiesiems n Fibonačio skaičiams sukurti yra:
klasė Fibonacci {tuštuma Fibonacci ( tarpt [ ] P ) {
tarpt n = P. ilgio ;
jeigu ( n > 0 )
P [ 0 ] = 0 ;
jeigu ( n > 1 )
P [ 1 ] = 1 ;
dėl ( tarpt i = du ; i < n ; i ++ ) { //n=0 ir n=2 buvo atsižvelgta
tarpt CurrNr = P [ i - 1 ] + P [ i - du ] ;
P [ i ] = CurrNr ;
}
}
}
Fibonacci klasė yra privati. The Fibonacci () metodas paima masyvą P ir grąžina void. Metodas prasideda nustatant masyvo ilgį. Šis n ilgis yra reikalingas Fibonačio skaičių skaičius. Pirmasis ir antrasis Fibonačio skaičiai nustatomi aiškiai ir dedami į pirmąją ir antrąją masyvo pozicijas.
Likę Fibonačio skaičiai, prasidedantys nuo trečiojo (indeksas, n = 2), nustatomi for-kilpoje ir pateikiami masyve į savo vietas. Taigi funkcija turi būti tuščia. Pagrindinis teiginys for-cikloje prideda ankstesnius du skaičius.
Aiškumo sumetimais vietoj n buvo naudojamas indekso kintamasis i.
Tinkama Java pagrindinė klasė (su pagrindiniu Java metodu) yra:
viešas klasė Pagrindinis {viešas statinis tuštuma pagrindinis ( Styga args [ ] ) {
tarpt m = 12 ;
tarpt [ ] arr = naujas tarpt [ m ] ;
Fibonačio obj = naujas Fibonacci ( ) ;
obj. Fibonacci ( arr ) ;
dėl ( tarpt i = 0 ; i < m ; i ++ )
Sistema . išeiti . spausdinti ( arr [ i ] + ' ' ) ;
Sistema . išeiti . println ( ) ;
}
}
Sukūrus skaičius fibonačio () metodu, pagrindinis Java metodas juos nuskaito.
Vieno Fibonačio skaičiaus generavimas pastoviu laiku
Yra matematinė formulė, kurią galima naudoti Fibonačio skaičiui gauti, kai pateikiamas atitinkamas nulinis indeksas n. Formulė yra tokia:
kur n yra nulinis indeksas ir Fib n yra atitinkamas Fibonačio skaičius. Atkreipkite dėmesį, kad dešinėje lygties pusėje ne kvadratinė šaknis iš 5 yra pakelta į laipsnį n; tai skliausteliuose esanti išraiška pakeliama iki laipsnio n. Yra dvi tokios išraiškos.
Jei n yra 0, Fib n būtų 0. Jei n yra 1, Fib n būtų 1. Jei n yra 2, Fib n būtų 1. Jei n yra 3, Fib n būtų 2. Jei n yra 4, Fib n būtų 3 – ir taip toliau. Skaitytojas gali patikrinti šią formulę matematiškai, pakeisdamas n skirtingomis reikšmėmis ir įvertindamas.
Kai ši formulė užkoduota, n gautų tik vieną Fibonačio skaičių. Jei reikia daugiau nei vieno Fibonačio skaičiaus, formulės kodas turi būti iškviestas vieną kartą kiekvienam iš skirtingų atitinkamų indeksų.
„Java“ programoje būdas sukurti tik vieną Fibonačio skaičių yra toks:
importuoti java.lang.* ;klasė Fib {
dvigubai fibNr ( tarpt n ) {
dvigubai FibN = ( Matematika . pow ( ( 1 + Matematika . kv ( 5 ) ) / du , n ) – Matematika . pow ( ( 1 - Matematika . kv ( 5 ) ) / du , n ) ) / Matematika . kv ( 5 ) ;
grąžinti FibN ;
}
}
Paketas java.lang.* turėjo būti importuotas programos pradžioje. Taip yra todėl, kad paketas turi matematikos klasę, kuri turi galios (pow) ir kvadratinės šaknies (sqrt) metodus. Pasirinktinis Java metodas čia tiesiogiai įgyvendina matematikos formulę.
Šios funkcijos laiko sudėtingumas yra O(1), pastovus vienos pagrindinės operacijos prijaukinimas. Tinkama pagrindinė Java klasė su pagrindiniu Java metodu aukščiau nurodytam metodui:
viešas klasė Pagrindinis {viešas statinis tuštuma pagrindinis ( Styga args [ ] ) {
tarpt N = vienuolika ;
Fib obj = naujas Fib ( ) ;
dvigubai teisingai = obj. fibNr ( N ) ;
Sistema . išeiti . println ( teisingai ) ;
}
}
Išsiunčiamas indeksas n = 11 ir grąžinamas Fibonačio skaičius 89. Išvestis yra:
89.00000000000003Nereikalingus dešimtainius skaitmenis galima pašalinti, tačiau tai bus aptariama kitą kartą.
Išvada
Fibonačio skaičiai yra tam tikra sveikųjų skaičių seka. Norėdami gauti dabartinį numerį, pridėkite du ankstesnius atitinkamus skaičius. Pirmieji du Fibonačio skaičiai, 0 ir 1, yra iš anksto deklaruoti visai sekai. Likę Fibonačio skaičiai gaminami iš ten.
Norėdami gauti Fibonačio skaičius iš 2 indekso iki indeksą n-1 atitinkančio skaičiaus, naudokite for-ciklą su pagrindiniu teiginiu:
tarpt CurrNr = P [ i - 1 ] + P [ aš - du ] ;kur currNo yra dabartinis Fibonačio skaičius, o P yra masyvas, kuriame saugomi n skaičiai.
Norėdami gauti tik vieną Fibonačio skaičių iš bet kurio nulinio indekso n, naudokite matematinę formulę:
