Liczby fibonacciego w języku Python

„Jeśli 0 zostanie dodane do 1, odpowiedź wynosi 1. Jeśli odpowiedź 1 i dodatek (nie augend) zostaną dodane, nowa odpowiedź wynosiłaby 2. Jeśli ta nowa odpowiedź i jej dodatek zostaną dodane, odpowiedź wynosi 3. Jeśli ta nowa odpowiedź i jej dodatek zostaną dodane, odpowiedź wynosi 5."

Liczby fibonacciego są szczególną sekwencją, w której pierwsza wartość jest wstępnie uznana za 0, a druga wartość jest wstępnie uznana za 1. Reszta liczb jest wytwarzana z tych dwóch poprzez dodanie dwóch poprzednich liczb. Wszystkie liczby Fibonacci są dodatnimi liczbami całkowitych, zaczynając od 0. Pierwsze dwanaście liczb Fibonacciego i ich uzyskanie 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:

0	1	1	2	3	5	8	13	21	34	55	89
0	1	2	3	4	5	6	7	8	9	10	11

Pierwszy rząd ma liczby Fibonacci. Drugi rząd ma indeksy oparte na zero, zakładając, że liczby Fibonacci są w tablicy.

Liczby fibonacciego można wytwarzać w czasie O (N) i w O (1). W tych wyrażeniach złożoności czasowej n oznacza n główne operacje, a 1 oznacza 1 główny operacja. Z O (n), n wytwarzane są liczby fibonacciego, poczynając od 0. Z O (1) jedna liczba Fibonacciego jest wytwarzana z odpowiedniego wskaźnika. Dlatego wymaga tylko jednej głównej operacji zamiast N głównych operacji.

Celem tego artykułu jest wyjaśnienie, jak wytwarzać liczby Fibonacciego, tak czy inaczej, za pomocą Pythona.

Formuła liczby Fibonacciego

Formalna definicja liczby Fibonacciego to:

gdzie f_N jest liczbą Fibonacciego w zerowym n

Wytwarzanie liczb Fibonacciego w czasie O (n)

Jeśli n wynosi 1, wówczas tylko 0 zostanie wydrukowany jako numer Fibonacciego. Jeśli n wynosi 2, wówczas 0 i 1 zostaną wydrukowane jako liczby Fibonacci, w tej kolejności. Jeśli n wynosi 3, to 0, 1 i 1 zostaną wydrukowane jako liczby Fibonacci w tej kolejności. Jeśli n wynosi 4, to 0, 1, 1 i 2 zostaną wydrukowane jako liczby Fibonacci w tej kolejności. Jeśli n wynosi 5, to 0, 1, 1, 2 i 3 zostaną wydrukowane jako liczby Fibonacci, w tej kolejności. Jeśli n wynosi 6, to 0, 1, 1, 2, 3 i 5 zostaną wydrukowane jako liczby fibonacci, w tej kolejności - i tak dalej.

Funkcja Pythona do wytworzenia pierwszych N Fibonacciego jest:

def fibonacci (n):
arr = [0] * (n)
ARR [1] = 1
Dla i w zakresie (2, n):
arr [i] = arr [i - 1] + arr [i - 2]
return ARR

Zaczyna się od utworzenia szeregu N elementów, wszystkie zainicjowane do zera. Ta tablica pomieści liczby Fibonacciego. Pierwszy numer Fibonacciego, 0, już tam jest. Drugi numer Fibonacciego, 1, jest przypisany przez następną instrukcję (w funkcji). Następnie jest pętla, która zaczyna się od indeksu 2 do tuż przed n. Ma stwierdzenie:

arr [i] = arr [i - 1] + arr [i - 2]

To dodaje natychmiastowe dwa poprzednie liczby.

Kod wywołania funkcji i wydrukowania pierwszych dwunastu numerów Fibonacciego może być:

N = 12
A = fibonacci (n)
bo w zakresie (n):
print ([i], end = ")
wydrukować()

Wyjście to:

0 1 1 2 3 5 8 13 21 34 55 89

Wytwarzanie jednej liczby Fibonacciego w ciągłym czasie

Istnieje formuła matematyczna, która wiąże wskaźnik oparty na zero z odpowiednią liczbą Fibonacciego. Formuła to:

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 miałby 0. Jeśli n to 1, fib_N byłby 1. Jeśli n wynosi 2, fib_N byłby 1. Jeśli n ma 3, fib_N byłoby 2. Jeśli n ma 4, fib_N byłoby 3 - i tak dalej. Czytelnik może matematycznie zweryfikować tę formułę, zastępując różne wartości N i ocenę. n jest indeksem opartym na zerowym w tej formule.

Kod Python dla tej formuły to:

Importuj matematyka

def Fibno (n):
Fibn = ((1+matematyka.sqrt (5))/2) ** n - (1 -mat.sqrt (5)) / 2) ** n) / matematyka.SQRT (5)
powrót fibn

Moduł matematyki został zaimportowany. Ma funkcję pierwiastka kwadratowego. Operator ** jest używany do zasilania. Funkcja fibno () bezpośrednio implementuje wzór. Odpowiednie połączenie i drukowanie funkcji fibno () to:

N = 11
ret = fibno (n)
Drukuj (ret)

Wyjście to:

89.00000000000003

Możliwe jest usunięcie niepotrzebnych cyfr dziesiętnych z odpowiedzi. Jest to jednak dyskusja od jakiegoś czasu.

Jeśli dla różnych indeksów N indeksów N jest wymagane różne liczby Fibonaccie. Poniższy program robi to dla indeksów opartych na zero, od 7 do 9 (włącznie):

Importuj matematyka

def Fibno (n):
Fibn = ((1+matematyka.sqrt (5))/2) ** n - (1 -mat.sqrt (5)) / 2) ** n) / matematyka.SQRT (5)
powrót fibn
bo w zakresie (7, 10):
print (fibno (i), end = ")
wydrukować()

Wyjście to:

13.000000000000002 21.000000000000004 34.00000000000001

Zwróć uwagę na sposób, w jaki w pętli została zakodowana w Pythonie. Pierwszy indeks to 7. Następny indeks to 8, a ostatni indeks to 9. 10 w argumencie zakresu wynosi 9 + 1. Wartością w pozycji 10 musi być ostatnim indeksem opartym na zerowym plus 1. Pierwszy argument, 7, to indeks oparty na zero.

Wniosek

Liczby fibonacciego są szczególną sekwencją liczb całkowitych (liczby całkowite dodatnie). Zaczyna się od 0, a następnie 1 bezwarunkowo. Reszta liczb powstaje stamtąd, dodając natychmiastowe dwa poprzednie liczby.

Aby uzyskać pierwsze N ​​liczby Fibonacciego, zaakceptuj 0 i 1 jako pierwsze dwa, a następnie przez resztę, użyj zaczepu z oświadczeniem takim:

arr [i] = arr [i - 1] + arr [i - 2]

co dodaje natychmiastowe dwa poprzednie liczby.

Aby uzyskać tylko jedną liczbę Fibonacciego z indeksu opartego na zero, użyj wzoru: