Fibonacciho čísla v jazyce Java

Ve skutečnosti jsou první dvě Fibonacciho čísla předdefinována. První Fibonacciho číslo je 0 a druhé Fibonacciho číslo je 1. S indexováním na nule a za předpokladu, že Fibonacciho čísla jsou v poli, pak:

a tak dále.

V programování se proměnná n a ne i používá pro indexy založené na nule pro tato Fibonacciho čísla. A s tím je prvních dvanáct Fibonacciho čísel:

Druhý řádek v tabulce uvádí indexy založené na nule, z nichž každý by měl při programování proměnnou n. První řádek uvádí odpovídající Fibonacciho čísla. Fibonacciho čísla tedy nejsou jen tak ledajaká čísla. Základní definice začíná 0 pro první Fibonacciho číslo a 1 pro druhé Fibonacciho číslo. Zbytek čísel se vyrábí odtud.

Fibonacciho čísla lze vytvářet v čase O(n) a také v čase O(1). Pro čas O(n), je-li n například 12, pak bude vytvořeno prvních dvanáct Fibonacciho čísel. Pro čas O(1) se vytvoří pouze jedno Fibonacciho číslo. Například, jestliže n je 6, pak by bylo vytvořeno Fibonacciho číslo 8.

Tento článek vysvětluje tyto dva způsoby vytváření Fibonacciho čísel v Javě.

Vzorec pro Fibonacciho číslo

Pro Fibonacciho číslo existuje matematický vzorec. Tento vzorec lze napsat na tři řádky nebo jeden řádek. Na třech řádcích je napsáno takto:

kde F _n je Fibonacciho číslo na n založeném na nule ^čt index. Takto je definováno Fibonacciho číslo.

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

Jestliže Fibonacciho čísla mají být produkována v O(3) časech, čísla, 0, 1, 1 by byla produkována; to jsou první tři Fibonacciho čísla. Poslední n založený na nule ^čt index je zde 2. Pokud mají být Fibonacciho čísla vytvořena v O(7) časech, budou vytvořena čísla 0, 1, 1, 2, 3, 5, 8; to je prvních sedm Fibonacciho čísel. Poslední n založený na nule ^čt index je zde 6. Pokud mají být Fibonacciho čísla vytvořena v O(n) časech, budou vytvořena čísla 0, 1, 1, 2, 3, 5, 8 – – -; to je prvních n Fibonacciho čísel. Poslední n založený na nule ^čt index je zde n-1.

Java metoda ve třídě pro vytvoření prvních n Fibonacciho čísel je:

Třída, Fibonacci, je soukromá. The Fibonacci() metoda vezme pole P a vrátí void. Metoda začíná určením délky pole. Tato délka n je počet požadovaných Fibonacciho čísel. První a druhé Fibonacciho číslo se určí explicitně a umístí se na první a druhou pozici v poli.

Zbytek Fibonacciho čísel počínaje třetí (index, n = 2) se určí ve smyčce for a umístí se na své pozice v poli. Takže funkce musí vrátit void. Hlavní příkaz ve smyčce for sčítá předchozí dvě čísla.

Pro srozumitelnost byla místo n použita proměnná index i.

Vhodná třída Java Main (s metodou Java main) je:

Po vytvoření čísel metodou fibonacci() je hlavní metoda Java načte.

Vytváření jednoho Fibonacciho čísla v konstantním čase

Existuje matematický vzorec, který lze použít k vytvoření Fibonacciho čísla, pokud je mu přiřazen odpovídající index n na nule. Vzorec je:

kde n je index založený na nule a Fib _n je odpovídající Fibonacciho číslo. Všimněte si, že na pravé straně rovnice to není druhá odmocnina z 5, která je umocněna n; právě výraz v závorce je umocněn n. Existují dva takové výrazy.

Jestliže n je 0, Fib _n by bylo 0. Pokud n je 1, Fib _n by bylo 1. Pokud n je 2, Fib _n by bylo 1. Pokud n je 3, Fib _n by bylo 2. Pokud n je 4, Fib _n bude 3 – a tak dále. Čtenář může tento vzorec ověřit matematicky, dosazením různých hodnot za n a vyhodnocením.

Když je tento vzorec zakódován, vytvořil by pouze jedno Fibonacciho číslo pro n. Pokud je požadováno více než jedno Fibonacciho číslo, kód vzorce musí být volán jednou pro každý z různých odpovídajících indexů.

V Javě je metoda k vytvoření pouze jednoho Fibonacciho čísla:

Balíček java.lang.* musel být naimportován na začátku programu. Je to proto, že balíček má třídu Math, která má metody power (pow) a druhé odmocniny (sqrt). Vlastní metoda Java zde implementuje matematický vzorec přímo.

Časová složitost této funkce je O(1), konstantní zkrocení jedné hlavní operace. Vhodná třída Java Main s hlavní metodou Java pro výše uvedenou metodu je:

Je odeslán index n = 11 a vráceno Fibonacciho číslo 89. Výstup je:

Zbytečné desetinné číslice lze odstranit, ale to je diskuse na jindy.

Závěr

Fibonacciho čísla jsou zvláštní posloupnost celých čísel. Chcete-li získat aktuální číslo, přidejte bezprostředně předchozí dvě odpovídající čísla. První dvě Fibonacciho čísla, 0 následovaná 1, jsou předem deklarována pro celou sekvenci. Zbytek Fibonacciho čísel se vyrábí odtud.

Chcete-li získat Fibonacciho čísla z indexu 2, do toho, který odpovídá indexu n-1, použijte for-loop s hlavním příkazem:

kde currNo je aktuální Fibonacciho číslo a P je pole pro uložení n čísel.

Chcete-li vytvořit pouze jedno Fibonacciho číslo z jakéhokoli indexu n založeného na nule, použijte matematický vzorec: