Liczby fibonacciego w języku Java
W rzeczywistości pierwsze dwie liczby Fibonacci są predefiniowane. Pierwsza liczba Fibonacciego to 0, a druga liczba Fibonacciego to 1. Przy indeksowaniu zerowym i zakładaniu, że liczby Fibonacciego są w tablicy, następnie:
W indeksie 0 liczba Fibonacciego wynosi 0, (predefiniowana);W indeksie 1 liczba Fibonacciego wynosi 1 (predefiniowana);
W indeksie 2 liczba Fibonacciego wynosi 1 = 1 + 0, (z definicji);
W indeksie 3 liczba Fibonacciego wynosi 2 = 1 + 1, (z definicji);
W indeksie 4 liczba Fibonacciego wynosi 3 = 2 + 1, (z definicji);
W indeksie 5 liczba Fibonacciego wynosi 5 = 3 + 2, (z definicji);
W indeksie 6 liczba Fibonacciego wynosi 8 = 5 + 3, (z definicji);
W indeksie 7 liczba Fibonacciego wynosi 13 = 8 + 5, (z definicji);
W indeksie 8 liczba Fibonacciego wynosi 21 = 13 + 8, (z definicji);
W indeksie 9 liczba Fibonacciego wynosi 34 = 21 + 13, (z definicji);
i tak dalej.
W programowaniu zmienna n, a nie i jest używana do indeksów opartych na zero dla tych liczb Fibonacciego. I dzięki temu pierwsze dwanaście liczb Fibonacciego to:
| 0 | 1 | 1 | 2 | 3 | 5 | 8 | 13 | 21 | 34 | 55 | 89 |
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
Drugi wiersz w tabeli podaje indeksy oparte na zero, z których każdy miałby zmienną n w programowaniu. Pierwszy rząd podaje odpowiednie liczby Fibonacci. Tak więc liczby Fibonacciego to nie tylko liczby. Definicja podstawowa zaczyna się od 0, dla pierwszej liczby Fibonacciego i 1 dla drugiej liczby Fibonacciego. Stamtąd produkowane są pozostałe liczby.
Liczby fibonacciego można wytwarzać w czasie O (N), a także w czasie O (1). Przez czas O (n), jeśli n wynosi 12 na przykład, wówczas powstanie pierwsze dwanaście liczb Fibonacciego. Przez czas O (1) produkowana jest tylko jedna liczba Fibonacciego. Na przykład, jeśli n wynosi 6, wówczas wytworzony byłby liczba Fibonacciego.
W tym artykule wyjaśniono te dwa sposoby tworzenia liczb Fibonacciego w Javie.
Formuła liczby Fibonacciego
Istnieje wzór matematyczny dla liczby Fibonacciego. Ta formuła można zapisać w trzech liniach lub jednym wierszu. W trzech wierszach jest napisane jako:
gdzie fN jest liczbą Fibonacciego w zerowym nth indeks. W ten sposób definiuje się liczbę Fibonacciego.
Wytwarzanie liczb Fibonacciego w czasie O (n)
Jeżeli liczby fibonacci mają być wytwarzane w O (3) razy, liczby, 0, 1, 1 zostaną wyprodukowane; To są pierwsze trzy liczby Fibonacci. Ostatni zero nth indeks tutaj, to 2. Jeżeli liczby Fibonacci mają być wytwarzane w O (7) razy, liczby, 0, 1, 1, 2, 3, 5, 8; To jest pierwsze siedem liczb Fibonacciego. Ostatni zero nth indeks tutaj, to 6. Jeśli liczby fibonacci mają być wytwarzane w czasach O (n), liczby, 0, 1, 1, 2, 3, 5, 8 - - -, zostaną wyprodukowane; To są pierwsze N Fibonacci. Ostatni zero nth indeks tutaj jest n-1.
Metoda Java w klasie do wytworzenia pierwszych N Fibonacciego jest:
klasa fibonaccivoid fibonacci (int [] p)
int n = p.długość;
if (n> 0)
P [0] = 0;
if (n> 1)
P [1] = 1;
dla (int i = 2; i
P [i] = currno;
Klasa, Fibonacci jest prywatna. fibonacci () Metoda przyjmuje tablicę P i zwraca pustkę. Metoda zaczyna się od określania długości tablicy. Ta długość n jest liczbą wymaganych liczb Fibonacciego. Pierwsza i druga liczba Fibonacciego są określone jawnie i umieszczane w pierwszej i drugiej pozycji w tablicy.
Reszta liczb Fibonacciego zaczyna się od trzecie. Tak więc funkcja musi zwrócić pustkę. Główne stwierdzenie w pętli dodaje dwie poprzednie liczby.
Zmienna indeksu, i, została użyta zamiast N, w celu przejrzystości.
Odpowiednia główna klasa Java (z główną metodą Java) to:
Klasa publiczna Mainpublic static void main (string args [])
int m = 12;
int [] arr = new int [m];
Fibonacci obj = new Fibonacci ();
obj.Fibonacci (ARR);
dla (int i = 0; i
System.na zewnątrz.println ();
Po wytworzeniu liczb metodą fibonacci (), główna metoda Java odczytuje je.
Wytwarzanie jednej liczby Fibonacciego w ciągłym czasie
Istnieje formuła matematyczna, którą można wykorzystać do wytworzenia liczby Fibonaccie. Formuła to:
gdzie n jest indeksem i fib opartym na zerowymN jest odpowiednią liczbą Fibonacciego. Zauważ, że po prawej stronie równania nie jest to pierwiastek kwadratowy 5, który jest podniesiony do mocy N; jest to wyrażenie w nawiasach podniesionych do mocy n. Istnieją dwa takie wyrażenia.
Jeśli n wynosi 0, fibN byłby 0. Jeśli n to 1, fibN byłby 1. Jeśli n wynosi 2, fibN byłby 1. Jeśli n ma 3, fibN byłoby 2. Jeśli n ma 4, fibN byłoby 3 - i tak dalej. Czytelnik może matematycznie zweryfikować tę formułę, zastępując różne wartości N i ocenę.
Po zakodowaniu ta formuła wytworzyłaby tylko jedną liczbę Fibonacciego dla n. Jeśli wymagane są więcej niż jedna liczba Fibonaccie.
W Javie metoda wytworzenia tylko jednej liczby Fibonacciego jest:
Importuj Java.Lang.*;klasa fib
Double Fibno (int n)
Double fibn = (matematyka.pow (1+matematyka.sqrt (5))/2, n) -math.pow (1 matka.sqrt (5)) / 2, n)) / Math.sqrt (5);
powrót fibn;
Java.Lang.* Pakiet musiał zostać zaimportowany na początku programu. Wynika to z faktu, że pakiet ma klasę matematyczną, która ma metody mocy (pow) i root kwadratowych (SQRT). Niestandardowa metoda Java tutaj implementuje formułę matematyki.
Złożoność czasu dla tej funkcji to O (1), stała oswojona jednej głównej operacji. Odpowiednia główna klasa Java z główną metodą Java dla powyższej metody to:
Klasa publiczna Mainpublic static void main (string args [])
int n = 11;
Fib obj = nowy fib ();
Double ret = obj.fibno (n);
System.na zewnątrz.println (ret);
Indeks n = 11 jest wysyłany, a liczba Fibonacciego, 89 jest zwracana. Wyjście to:
89.00000000000003Niepotrzebne cyfry dziesiętne można usunąć, ale jest to dyskusja na jakiś czas.
Wniosek
Liczby fibonacciego są szczególną sekwencją liczb całkowitych. Aby uzyskać bieżącą liczbę, dodaj bezpośrednią poprzednie dwa odpowiednie liczby. Pierwsze dwie liczby Fibonacciego, 0, a następnie 1, są wstępnie zadeklarowane, dla całej sekwencji. Stamtąd produkowane są reszta liczb Fibonacciego.
Aby wyprodukować liczby Fibonacciego z indeksu 2, do tego, co odpowiada indeksowi N-1, użyj podkładki z instrukcją ogólną:
int currno = p [i - 1] + p [i - 2];gdzie Currno jest aktualną liczbą Fibonacciego, a P jest tablicą do przechowywania numerów N.
Aby wyprodukować tylko jedną liczbę Fibonacciego z dowolnego indeksu opartego na zero, użyj wzoru matematycznego: