Liczby Fibonacciego w języku Python

Liczby Fibonacciego to szczególna sekwencja, w której pierwsza wartość jest wstępnie zadeklarowana jako 0, a druga wartość jest wstępnie zadeklarowana jako 1. Pozostałe liczby są tworzone z tych dwóch przez dodanie dwóch poprzednich liczb. Wszystkie liczby Fibonacciego są dodatnimi liczbami całkowitymi, zaczynając od 0. Pierwsze dwanaście liczb Fibonacciego i sposób ich uzyskania są następujące:

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

Bez wyrażeń sumy te liczby Fibonacciego można umieścić w tabeli w następujący sposób:

Pierwszy wiersz zawiera liczby Fibonacciego. Drugi wiersz ma indeksy liczone od zera, zakładając, że liczby Fibonacciego znajdują się w tablicy.

Liczby Fibonacciego mogą być tworzone w czasie O(n) iw 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 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 za pomocą Pythona.

Wzór na liczbę Fibonacciego

Formalna definicja liczby Fibonacciego to:

gdzie F _n jest liczbą Fibonacciego przy n

Wytwarzanie liczb Fibonacciego w czasie O(n)

Jeśli n wynosi 1, to tylko 0 zostanie wydrukowane jako liczba Fibonacciego. Jeśli n wynosi 2, to 0 i 1 zostaną wydrukowane jako liczby Fibonacciego w tej kolejności. Jeśli n wynosi 3, to 0, 1 i 1 zostaną wydrukowane jako liczby Fibonacciego w tej kolejności. Jeśli n wynosi 4, to 0, 1, 1 i 2 zostaną wydrukowane jako liczby Fibonacciego w tej kolejności. Jeśli n wynosi 5, to 0, 1, 1, 2 i 3 zostaną wydrukowane jako liczby Fibonacciego w tej kolejności. Jeśli n wynosi 6, to 0, 1, 1, 2, 3 i 5 zostaną wydrukowane jako liczby Fibonacciego, w tej kolejności – i tak dalej.

Funkcja Pythona do utworzenia pierwszych n liczb Fibonacciego to:

Rozpoczyna się od utworzenia tablicy n elementów, wszystkie zainicjowane zerami. Ta tablica będzie przechowywać liczby Fibonacciego. Pierwsza liczba Fibonacciego, 0, już tam jest. Druga liczba Fibonacciego, 1, jest przypisywana przez następną instrukcję (w funkcji). Następnie jest pętla for, która zaczyna się od indeksu 2 do tuż przed n. Ma oświadczenie:

Spowoduje to dodanie bezpośrednio poprzednich dwóch liczb.

Kod do wywołania funkcji i wydrukowania pierwszych dwunastu liczb Fibonacciego może mieć postać:

N = 12
A = Fibonacciego (N)
dla i w zakresie (N):
drukuj (A[i], koniec=’’)
wydrukować()

Dane wyjściowe to:

Wytwarzanie jednej liczby Fibonacciego w stałym czasie

Istnieje wzór matematyczny, który wiąże indeks liczony od zera z odpowiednią liczbą Fibonacciego. Formuła to:

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 równe 0. Jeśli n wynosi 1, Fib _n byłoby 1. Jeśli n wynosi 2, Fib _n byłoby 1. Jeśli n wynosi 3, Fib _n byłoby 2. Jeśli n wynosi 4, Fib _n byłoby 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.

Kod Pythona dla tej formuły to:

importuj matematykę

Moduł matematyczny został zaimportowany. Ma funkcję pierwiastka kwadratowego. Operator ** służy do zasilania. Funkcja fibNo() bezpośrednio implementuje formułę. Odpowiednie wywołanie i wydruk funkcji fibNo() to:

N = 11
prawo = fibNo(N)
drukuj(ret)

Dane wyjściowe to:

Możliwe jest usunięcie z odpowiedzi niepotrzebnych cyfr dziesiętnych. Jest to jednak dyskusja na inny czas.

Jeśli różne liczby Fibonacciego są wymagane dla różnych n indeksów, funkcja fibNo() musi być wywołana raz dla każdego z n indeksów, aby zwrócić różne odpowiadające im liczby Fibonacciego. Poniższy program robi to dla indeksów od zera, od 7 do 9 (włącznie):

importuj matematykę

Dane wyjściowe to:

Zwróć uwagę na sposób, w jaki pętla for została zakodowana w Pythonie. Pierwszy indeks to 7. Następny indeks to 8, a ostatni indeks to 9. 10 w argumencie zakresu to 9 + 1. Wartość na pozycji 10 musi być ostatnim indeksem liczącym od zera plus 1. Pierwszy argument, 7, jest początkowym indeksem liczonym od zera.

Wniosek

Liczby Fibonacciego to szczególny ciąg liczb całkowitych (liczb całkowitych dodatnich). Zaczyna się od 0, po którym następuje bezwarunkowo 1. Pozostałe liczby są rozwijane stamtąd przez dodanie dwóch poprzednich liczb.

Aby uzyskać pierwsze n liczb Fibonacciego, zaakceptuj 0 i 1 jako pierwsze dwa, a dla reszty użyj pętli for z oświadczeniem takim jak:

co dodaje bezpośrednio poprzednie dwie liczby.

Aby uzyskać tylko jedną liczbę Fibonacciego z indeksu n liczonego od zera, użyj wzoru: