Liczby Fibonacciego
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 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: .
Z tych rozważań wynika następująca postać liczb Fibonacciego:
Okazuje się, że istnieje jawna postać liczb Fibonacciego dla dowolnego k i wyraża się wzorem:
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:
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) |
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 |
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!
Filed under: Matematyka,Teoria liczb - @ 13 lutego 2018 13:26
Tagi: ciąg, ciąg fibonacciego, fraktale, przyroda, złota liczba, złoty podział