Znaczenie liczb Fibonacciego
Liczby Fibonacciego to szczególny ciąg dodatnich liczb całkowitych, zaczynając od 0. Liczby całkowite są dodatnimi liczbami całkowitymi. Tak więc liczba Fibonacciego to określony ciąg liczb całkowitych lub liczb naturalnych, zaczynając od 0. W tym ciągu pierwsze dwie liczby to 0 i 1, w tej kolejności. Pozostałe liczby są rozwijane stamtąd przez dodanie dwóch poprzednich liczb. Pierwsze dwanaście liczb Fibonacciego otrzymujemy w następujący sposób:
0
1
1 + 0 = 1
1 + 1 = 2
2 + 1 = 3
3 + 2 = 5
5 + 3 = 8
8 + 5 = 13
13 + 8 = 21
21 + 13 = 34
34 + 21 = 55
55 + 34 = 89
Innymi słowy, pierwsze dwanaście liczb Fibonacciego to:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89
Oczywiście trzynasta liczba to: 144 = 55 + 89. Liczby Fibonacciego można sobie wyobrazić jako tablicę, tak:
| 0 | 1 | 1 | dwa | 3 | 5 | 8 | 13 | dwadzieścia jeden | 3. 4 | 55 | 89 |
Tablica ma indeksy. W poniższej tabeli drugi wiersz pokazuje odpowiadające indeksy liczone od zera dla liczb Fibonacciego w tablicy:
| 0 | 1 | 1 | dwa | 3 | 5 | 8 | 13 | dwadzieścia jeden | 3. 4 | 55 | 89 |
| 0 | 1 | dwa | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | jedenaście |
W przypadku indeksów liczonych od zera, jeśli jest dwanaście elementów, ostatni indeks to 11.
Liczby Fibonacciego mogą być tworzone w czasie O(n) lub w czasie O(1). W tych wyrażeniach złożoności czasowej n oznacza n operacji głównych, a 1 oznacza 1 operację główną. Z O(n), n liczb Fibonacciego jest tworzonych, zaczynając od 0. Z O(1), jedna liczba Fibonacciego jest tworzona z odpowiedniego indeksu. Dlatego O(1) zajmuje tylko jedną główną operację zamiast n głównych operacji.
Celem tego artykułu jest wyjaśnienie, w jaki sposób tworzyć liczby Fibonacciego, tak czy inaczej, przy użyciu JavaScript, który obecnie jest ECMAScript.
Środowisko kodowania
Środowisko node.js nie będzie używane, jak mógł się spodziewać czytelnik. Zamiast tego do interpretacji kodu i wyświetlenia wyników zostanie wykorzystana przeglądarka. Skrypt (kod) należy zapisać w pliku edytora tekstu, który należy zapisać z rozszerzeniem „.html”. Skrypt powinien mieć minimalny kod:
DOCTYPE HTML >< html >
< głowa >
< tytuł > Liczby Fibonacciego z JavaScript tytuł >
głowa >
< ciało >
< typ skryptu = „tekst/ekmaskrypt” >
scenariusz >
ciało >
html >
To jest przybliżony minimalny kod, którego potrzebuje strona internetowa. Całe kodowanie tego artykułu znajduje się pomiędzy tagami .
Aby uruchomić napisany (dodany) kod, wystarczy dwukrotnie kliknąć ikonę nazwy pliku, a przeglądarka na komputerze go otworzy.
Definicja liczby Fibonacciego
Istnieje matematyczna definicja liczby Fibonacciego. Definiuje się go następująco:
Gdzie Fn jest liczbą Fibonacciego odpowiadającą indeksowi liczonemu od zera, n.
Pierwsze dwie liczby: 0 i 1, są wstępnie zadeklarowane w tej kolejności. Ostatni wiersz tej funkcji pokazuje, w jaki sposób pozostałe liczby pochodzą od pierwszych dwóch liczb w ich kolejności.
Ta definicja jest również jedną z formuł na liczbę Fibonacciego.
Wytwarzanie liczb Fibonacciego w czasie O(n)
Jeśli n wynosi 1, to tylko 0 będzie wyświetlane jako liczba Fibonacciego. Jeśli n wynosi 2, to 0 i 1 będą wyświetlane jako liczby Fibonacciego w tej kolejności. Jeśli n wynosi 3, to 0, 1 i 1 będą wyświetlane jako liczby Fibonacciego w tej kolejności. Jeśli n wynosi 4, to 0, 1, 1 i 2 będą wyświetlane jako liczby Fibonacciego w tej kolejności. Jeśli n wynosi 5, to 0, 1, 1, 2 i 3 będą wyświetlane jako liczby Fibonacciego w tej kolejności. Jeśli n wynosi 6, to 0, 1, 1, 2, 3 i 5 będą wyświetlane jako liczby Fibonacciego w tej kolejności – i tak dalej.
Funkcja ECMAscript do wygenerowania pierwszych n liczb całkowitych Fibonacciego (liczby) to:
< typ skryptu = „tekst/ekmaskrypt” >funkcjonować Fibonacciego ( A ) {
n = A. długość ;
jeśli ( n > 0 )
A [ 0 ] = 0 ;
jeśli ( n > 1 )
A [ 1 ] = 1 ;
dla ( i = dwa ; i < n ; i ++ ) { //n=0 i n=2 zostały wzięte pod uwagę
aktualnyNie = A [ i - 1 ] + A [ i - dwa ] ;
A [ i ] = aktualnyNie ;
}
}
Zamykający tag skryptu nie został wyświetlony. Funkcja otrzymuje tablicę. Pierwsze dwie liczby Fibonacciego są przypisane na ich pozycji. Pętla for iteruje od indeksu liczonego od zera, od 2 do tuż poniżej n. Najważniejszym stwierdzeniem w pętli for jest:
bieżNo = A[i – 1] + A[i – 2];
Spowoduje to dodanie dwóch bezpośrednich poprzednich liczb w tablicy, aby mieć bieżącą liczbę. Zanim funkcja fibonacci() zakończy wykonywanie, wszystkie elementy tablicy są pierwszymi n liczbami Fibonacciego. Odpowiedni kod do wywołania funkcji fibonacci() i wyświetlenia liczb Fibonacciego to:
N = 12 ;Arr = Nowy Szyk ( N ) ;
Fibonacciego ( Arr ) ;
dla ( i = 0 ; i < N ; i ++ )
dokument. pisać ( Arr [ i ] + ' ' ) ;
dokument. pisać ( „
” ) ;
scenariusz >
Ten kod pokazuje zamykający tag skryptu. Kod jest wpisywany poniżej powyższego kodu. Dane wyjściowe wyświetlane na stronie internetowej to:
0 1 1 2 3 5 8 13 21 34 55 89
zgodnie z oczekiwaniami.
Wytwarzanie jednej liczby Fibonacciego w czasie O (1)
O(1) to czas stały. Odnosi się do jednej głównej operacji. Innym wzorem matematycznym do wytworzenia liczby Fibonacciego jest:
Zauważ, że po prawej stronie równania to nie pierwiastek kwadratowy z 5 jest podnoszony do potęgi n; jest to wyrażenie w nawiasach podniesione do potęgi n. Są dwa takie wyrażenia.
Jeśli n wynosi 0, Fibn będzie wynosił 0. Jeśli n wynosi 1, Fibn będzie wynosił 1. Jeśli n wynosi 2, Fibn będzie wynosił 1. Jeśli n wynosi 3, Fibn będzie wynosił 2. Jeśli n wynosi 4, Fibn będzie wynosił 3 – i tak dalej. Czytelnik może zweryfikować ten wzór matematycznie, zastępując n różnymi wartościami i oceniając. n jest indeksem liczonym od zera w tej formule. Wynikiem jest odpowiednia liczba Fibonacciego.
Kod ECMAScript (JavaScript) dla tej formuły to:
< typ skryptu = „tekst/ekmaskrypt” >funkcjonować fibNo ( n ) {
FibN = ( Matematyka . pow ( ( 1 + Matematyka . sqrt ( 5 ) ) / dwa , n ) - Matematyka . pow ( ( 1 - Matematyka . sqrt ( 5 ) ) / dwa , n ) ) / Matematyka . sqrt ( 5 ) ;
zwrócić FibN ;
}
Zamykający tag skryptu nie został wyświetlony. Zwróć uwagę, jak zostały użyte predefiniowane funkcje potęgi (pow) i pierwiastka kwadratowego (sqrt). W ECMAScript (JavaScript) moduł Math nie musi być importowany. Funkcja fibNo() bezpośrednio implementuje formułę. Odpowiednie wywołanie i wyświetlenie funkcji fibNo() na stronie internetowej to:
N = jedenaście ;prawo = fibNo ( N ) ;
dokument. pisać ( prawo ) ;
scenariusz >
Kod pokazuje zamykający tag skryptu. Dane wyjściowe to:
89.00000000000003
Możliwe jest usunięcie z odpowiedzi niepotrzebnych cyfr dziesiętnych. Jest to jednak dyskusja na inny czas.
Jeśli wymagana jest więcej niż jedna liczba Fibonacciego, kod musi wywołać formułę raz dla każdego odpowiadającego mu indeksu n opartego na zera.
Wniosek
Liczby Fibonacciego to szczególny ciąg dodatnich liczb całkowitych, zaczynając od 0. Liczby całkowite są dodatnimi liczbami całkowitymi. Tak więc liczba Fibonacciego to określony ciąg liczb całkowitych lub liczb naturalnych, zaczynając od 0. W tym ciągu pierwsze dwie liczby to 0 i 1, w tej kolejności. Te dwie pierwsze liczby są po prostu zdefiniowane jako takie. Pozostałe liczby są rozwijane stamtąd przez dodanie dwóch poprzednich liczb.
Po wytworzeniu pierwszych dwóch liczb Fibonacciego, aby wytworzyć resztę liczb Fibonacciego, aby otrzymać w sumie n liczb, należy użyć pętli for ze stwierdzeniem:
bieżNo = A[i – 1] + A[i – 2];
Spowoduje to dodanie dwóch ostatnich liczb Fibonacciego bezpośrednio do aktualnej liczby Fibonacciego.
Mając indeks liczony od zera, aby uzyskać odpowiednią liczbę Fibonacciego, użyj wzoru:
