Fibonacciho čísla v jazyku Java

V skutočnosti sú prvé dve Fibonacciho čísla preddefinované. Prvé Fibonacciho číslo je 0 a druhé Fibonacciho číslo je 1. Pri indexovaní založenom na nule a za predpokladu, že Fibonacciho čísla sú v poli, potom:

a tak ďalej.

V programovaní sa premenná n a nie i používa pre indexy založené na nule pre tieto Fibonacciho čísla. A s tým je prvých dvanásť Fibonacciho čísel:

Druhý riadok v tabuľke uvádza indexy založené na nule, z ktorých každý by mal pri programovaní premennú n. Prvý riadok obsahuje zodpovedajúce Fibonacciho čísla. Fibonacciho čísla teda nie sú len tak hocijaké. Základná definícia začína 0 pre prvé Fibonacciho číslo a 1 pre druhé Fibonacciho číslo. Odtiaľ sa vyrábajú zvyšné čísla.

Fibonacciho čísla možno vytvoriť v čase O(n) a tiež v čase O(1). Pre čas O(n), ak je n napríklad 12, vznikne prvých dvanásť Fibonacciho čísel. Pre čas O(1) sa vytvorí iba jedno Fibonacciho číslo. Napríklad, ak n je 6, potom sa vytvorí Fibonacciho číslo 8.

Tento článok vysvetľuje tieto dva spôsoby vytvárania Fibonacciho čísel v Jave.

Vzorec pre Fibonacciho číslo

Existuje matematický vzorec pre Fibonacciho číslo. Tento vzorec môže byť napísaný v troch riadkoch alebo v jednom riadku. V troch riadkoch je to napísané takto:

kde F _n je Fibonacciho číslo pri n založenom na nule ^th index. Takto je definované Fibonacciho číslo.

Vytváranie Fibonacciho čísel v O(n) čase

Ak majú byť Fibonacciho čísla produkované v O(3)-krát, budú vytvorené čísla 0, 1, 1; to sú prvé tri Fibonacciho čísla. Posledné n založené na nule ^th index je tu 2. Ak majú byť Fibonacciho čísla produkované v O(7)-krát, boli by vytvorené čísla 0, 1, 1, 2, 3, 5, 8; toto je prvých sedem Fibonacciho čísel. Posledné n založené na nule ^th index je tu 6. Ak majú byť Fibonacciho čísla produkované v O(n)-krát, vytvorili by sa čísla 0, 1, 1, 2, 3, 5, 8 – – -; toto je prvých n Fibonacciho čísel. Posledné n založené na nule ^th index je tu n-1.

Java metóda v triede na vytvorenie prvých n Fibonacciho čísel je:

Trieda Fibonacci je súkromná. The Fibonacci() metóda vezme pole P a vráti void. Metóda začína určením dĺžky poľa. Táto dĺžka n je počet požadovaných Fibonacciho čísel. Prvé a druhé Fibonacciho číslo sa určí explicitne a umiestnia sa na prvú a druhú pozíciu v poli.

Zvyšné Fibonacciho čísla začínajúce od tretiny (index, n = 2) sú určené v slučke for a umiestnené na svoje pozície v poli. Takže funkcia musí vrátiť hodnotu void. Hlavný príkaz v slučke for pridáva predchádzajúce dve čísla.

Premenná index, i, bola použitá namiesto n, kvôli prehľadnosti.

Vhodná trieda Java Main (s hlavnou metódou Java) je:

Po vytvorení čísel metódou fibonacci() ich hlavná metóda Java načíta.

Vytvorenie jedného Fibonacciho čísla v konštantnom čase

Existuje matematický vzorec, ktorý možno použiť na vytvorenie Fibonacciho čísla, keď dostane zodpovedajúci index založený na nule, n. Vzorec je:

kde n je index založený na nule a Fib _n je zodpovedajúce Fibonacciho číslo. Všimnite si, že na pravej strane rovnice to nie je druhá odmocnina z 5, ktorá je umocnená na n; práve výraz v zátvorke je umocnený n. Existujú dva takéto výrazy.

Ak n je 0, Fib _n by bolo 0. Ak n je 1, Fib _n by bolo 1. Ak n je 2, Fib _n by bolo 1. Ak n je 3, Fib _n by bolo 2. Ak n je 4, Fib _n bude 3 – a tak ďalej. Čitateľ môže tento vzorec overiť matematicky, dosadením rôznych hodnôt za n a vyhodnotením.

Pri kódovaní by tento vzorec produkoval iba jedno Fibonacciho číslo pre n. Ak sa vyžaduje viac ako jedno Fibonacciho číslo, kód vzorca sa musí volať raz pre každý z rôznych zodpovedajúcich indexov.

V Jave je metóda na vytvorenie iba jedného Fibonacciho čísla:

Na začiatku programu bolo potrebné importovať balík java.lang.*. Je to preto, že balík má triedu Math, ktorá má metódy mocniny (pow) a druhej odmocniny (sqrt). Vlastná metóda Java tu implementuje matematický vzorec priamo.

Časová zložitosť pre túto funkciu je O(1), konštantná krotka jednej hlavnej operácie. Vhodná trieda Java Main s hlavnou metódou Java pre vyššie uvedenú metódu je:

Pošle sa index n = 11 a vráti sa Fibonacciho číslo 89. Výstupom je:

Nepotrebné desatinné číslice možno odstrániť, ale to je diskusia na inokedy.

Záver

Fibonacciho čísla sú konkrétnou postupnosťou celých čísel. Ak chcete získať aktuálne číslo, pridajte bezprostredne predchádzajúce dve zodpovedajúce čísla. Prvé dve Fibonacciho čísla, 0 nasledovaná 1, sú vopred deklarované pre celú postupnosť. Zvyšok Fibonacciho čísel sa vyrába odtiaľ.

Ak chcete získať Fibonacciho čísla z indexu 2, do toho, čo zodpovedá indexu n-1, použite for-loop s hlavným príkazom:

kde currNo je aktuálne Fibonacciho číslo a P je pole na uloženie n čísel.

Ak chcete vytvoriť iba jedno Fibonacciho číslo z akéhokoľvek indexu n založeného na nule, použite matematický vzorec: