Dziś zajmiemy się liczbami Fibonacciego.
Czym są owe liczby?

Są to jeden z najpopularniejszych liczb występujących w informatyce.
Fibonacci w swojej książce Liber abaci zawarł pytanie dotyczące rozmnażania się królików.
Chodzi o to, że mamy parę nowo narodzonych królików i o każdej parze zakładamy, że:

-nowa para staje się płodna po miesiącu życia
-każda para rodzi jedną parę nowych królików w miesiącu
-króliki nigdy nie umierają.

Pytanie brzmiało: ile par królików będzie po upływie roku?

Pytanie najczęściej zadajemy w następujący sposób:
Ile będzie par królików po upływie k miesięcy?

tę liczbę oznaczamy przez F_k i nazywamy liczbą Fibonacciego.

Okazuje się, że w pierwszym miesiącu i drugim mamy tylko jedna parę, ale w drugim miesiącu może ona dać już parę młodych.
W trzecim miesiącu są już dwie pary, przy czym tylko ta starsza może dalej rodzić młode. Stąd w czwartym miesiącu są już trzy pary, z których dwie, a więc tyle ile było już w poprzednim miesiącu, mogą rodzić młode.
W następnym miesiącu mamy te trzy pary i dwie pary młodych, a więc razem 5 par.
Otrzymujemy więc ciąg: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55 itd.

Wynika z tego, że w kolejnym miesiącu liczba par królików będzie równa liczbie par z poprzedniego miesiącam plus liczba par nowo narodzonych królików, a tych jest tyle, ile było par dwa miesiące wcześniej..
Zatem kolejna liczba Fibonacciego jest sumą dwóch poprzednich.

Możemy zastosować wzór: F_k=F_{k-1}+F_{k-2}.
Z tych rozważań wynika następująca postać liczb Fibonacciego:
\begin{cases} 1, &\text{dla } x =1,2 \\F_{k-1}+F_{k-2} &\text{dla } k \ge 3\end{cases}

Okazuje się, że istnieje jawna postać liczb Fibonacciego dla dowolnego k i wyraża się wzorem:

\displaystyle{F_k=\frac{1}{\sqrt{5}}[(\frac{1+\sqrt{5}}{2})^k - (\frac{1-\sqrt{5}}{2})^k]}

Liczby fibonacciego mają wiele ciekawych właściwości, jedną z nich jest powiązanie ze złota liczbą.
Jeżeli podzielimy przez siebie dowolne, kolejne dwa wyrazy ciągu Fibonacciego, np. 987 : 610; 89 : 55 to stosunek tych liczb będzie równy zawsze tej samej liczbie, równej w przybliżeniu 1.618. Im większe liczby przez siebie podzielimy, tym większe będzie przybliżenie złotej liczby.

Ciąg fibonacciego pojawia się w naturze i sztuce. Poniżej kilka ilustracji przedstawiający ukazywanie się liczb fibonacciego:

Niesamowite jest to, że ciąg fibonacciego ukazuje się, także w muzyce czy obiektach zwanych fraktalami.

Wracając do złotej liczby okazuje się, że jest ona równa:
\displaystyle{\phi= \frac{1+\sqrt{5}}{2}=1,6180330887}

Na koniec dwa krótkie kody źródłowe w Pythonie dotyczące rekurencyjnego podejścia do ciągu fibonacciego a także podejścia iteracyjnego.

Sposób rekurencyjny:

def FibRek(k):
    if k <= 2:
       return 1
    else:
        return FibRek(k-1) + FibRek(k-2)

A poniżej sposób iteracyjny:

def FibIter(k):
    Fk=1
    Fk1=1
    for i in range(k-2):
        Fk, Fk1 = Fk+Fk1,Fk
 
    return Fk

W kolejnym artykule zapoznamy się z fraktalami, jak się okaże, ciąg fibonacciego występuje także, w tych obiektach.

Na dziś koniec!

ZOSTAW ODPOWIEDŹ

Please enter your comment!
Please enter your name here