Fibonaccijeva števila v jeziku Java

Pravzaprav sta prvi dve Fibonaccijevi števili vnaprej določeni. Prvo Fibonaccijevo število je 0, drugo Fibonaccijevo število pa 1. Z indeksiranjem na osnovi nič in ob predpostavki, da so Fibonaccijeva števila v nizu, potem:

in tako naprej.

V programiranju se spremenljivka n in ne i uporablja za indekse na osnovi nič za ta Fibonaccijeva števila. In s tem je prvih dvanajst Fibonaccijevih števil:

Druga vrstica v tabeli podaja indekse na osnovi nič, od katerih bi vsak imel spremenljivko n pri programiranju. Prva vrstica podaja ustrezna Fibonaccijeva števila. Fibonaccijeva števila torej niso poljubna števila. Osnovna definicija se začne z 0, za prvo Fibonaccijevo število in 1 za drugo Fibonaccijevo število. Ostale številke so proizvedene od tam.

Fibonaccijeva števila je mogoče ustvariti v O(n) času in tudi v O(1) času. Za čas O(n), če je n na primer 12, bi bilo proizvedenih prvih dvanajst Fibonaccijevih števil. Za čas O(1) se ustvari samo eno Fibonaccijevo število. Na primer, če je n 6, bi nastalo Fibonaccijevo število 8.

Ta članek pojasnjuje ta dva načina izdelave Fibonaccijevih števil v Javi.

Formula za Fibonaccijevo število

Obstaja matematična formula za Fibonaccijevo število. Ta formula je lahko zapisana v treh ali eni vrstici. V treh vrsticah je zapisano:

kjer F _n je Fibonaccijevo število pri n na osnovi nič ^th kazalo. Tako je definirano Fibonaccijevo število.

Izdelava Fibonaccijevih števil v O(n) času

Če bi Fibonaccijeva števila proizvedli v O(3)-kratnikih, bi bila proizvedena števila 0, 1, 1; to so prva tri Fibonaccijeva števila. Zadnji n ^th indeks tukaj je 2. Če bi Fibonaccijeva števila proizvedli v O(7)-krat, bi bila proizvedena števila 0, 1, 1, 2, 3, 5, 8; to je prvih sedem Fibonaccijevih števil. Zadnji n ^th tukaj je indeks 6. Če bi Fibonaccijeva števila proizvedli v O(n)-krat, bi bila proizvedena števila 0, 1, 1, 2, 3, 5, 8 – – -; to je prvih n Fibonaccijevih števil. Zadnji n ^th indeks tukaj je n-1.

Metoda Java v razredu za izdelavo prvih n Fibonaccijevih števil je:

Razred, Fibonacci je zaseben. The fibonacci() metoda vzame matriko P in vrne void. Metoda se začne z določitvijo dolžine niza. Ta dolžina n je zahtevano število Fibonaccijevih števil. Prvo in drugo Fibonaccijevo število sta eksplicitno določena in postavljena na prvo in drugo mesto v nizu.

Preostala Fibonaccijeva števila, ki se začnejo s tretjim (indeks, n = 2), se določijo v for-zanki in postavijo na svoje položaje v nizu. Torej mora funkcija vrniti vrednost void. Glavni stavek v for-zanki sešteje prejšnji dve številki.

Indeksna spremenljivka i je bila zaradi jasnosti uporabljena namesto n.

Primeren glavni razred Java (z glavno metodo Java) je:

Ko so številke izdelane z metodo fibonacci(), jih glavna metoda Jave prebere.

Izdelava enega Fibonaccijevega števila v konstantnem času

Obstaja matematična formula, ki jo lahko uporabimo za izdelavo Fibonaccijevega števila, če dobimo ustrezen indeks, ki temelji na ničli, n. Formula je:

kjer je n indeks na osnovi ničle in Fib _n je ustrezno Fibonaccijevo število. Upoštevajte, da na desni strani enačbe kvadratni koren iz 5 ni dvignjen na potenco n; to je izraz v oklepaju, ki je dvignjen na potenco n. Obstajata dva taka izraza.

Če je n 0, Fib _n bi bil 0. Če je n 1, Fib _n bi bil 1. Če je n 2, Fib _n bi bil 1. Če je n 3, Fib _n bi bilo 2. Če je n 4, Fib _n bi bil 3 – in tako naprej. Bralec lahko to formulo matematično preveri tako, da zamenja različne vrednosti za n in oceni.

Ko bi bila kodirana, bi ta formula ustvarila samo eno Fibonaccijevo število za n. Če je potrebnih več kot eno Fibonaccijevo število, je treba kodo za formulo poklicati enkrat za vsakega od različnih ustreznih indeksov.

V Javi je metoda za izdelavo samo enega Fibonaccijevega števila:

Paket java.lang.* je bilo treba uvoziti na začetku programa. To je zato, ker ima paket razred Math, ki ima metode moči (pow) in metode kvadratnega korena (sqrt). Metoda Java po meri tukaj izvaja matematično formulo neposredno.

Časovna zahtevnost za to funkcijo je O(1), konstanta krotljivosti ene glavne operacije. Primeren glavni razred Java z glavno metodo Java za zgornjo metodo je:

Poslan je indeks n = 11 in vrnjeno je Fibonaccijevo število 89. Rezultat je:

Nepotrebne decimalne številke je mogoče odstraniti, a o tem bomo razpravljali kdaj drugič.

Zaključek

Fibonaccijeva števila so določeno zaporedje celih števil. Za pridobitev trenutne številke seštejte neposredno prejšnji dve ustrezni številki. Prvi dve Fibonaccijevi števili, 0, ki ji sledi 1, sta vnaprej deklarirani za celotno zaporedje. Preostala Fibonaccijeva števila so proizvedena od tam.

Za izdelavo Fibonaccijevih števil od indeksa 2 do tistega, ki ustreza indeksu n-1, uporabite zanko for z glavnim stavkom:

kjer je currNo trenutno Fibonaccijevo število in P je polje za shranjevanje n števil.

Če želite ustvariti samo eno Fibonaccijevo število iz katerega koli indeksa n, ki temelji na ničli, uporabite matematično formulo: