Fibonacciho postupnosA? a vA?elA� rodokmeA?

V spoloA?enstvA?ch vA?iel medonosnA?ch, mA?A?eme osadenstvo rozdeliA? na tri skupiny:

Jedna krA?A?ovnA? a�� kralovna
Robotnice a�� robotnica
TrA?dy a�� trud

RozmnoA?ovanie prebieha tak, A?e krA?A?ovnA? je oplodnenA? trA?dom a kladie oplodnenA� vajA�A?ka, z ktorA?ch sa neskA?r vyliahnu robotnice alebo novA? krA?A?ovnA?. ZA?roveA? kladie neoplodnenA� vajA�A?ka, z ktorA?ch sa vyliahnu trA?dy. Schematicky:

kralovna trud kralovna
krA?A?ovnA? + trA?d a�� robotnica alebo novA? krA?A?ovnA?
robotnica
/
kralovna
krA?A?ovnA? a�� trA?d
trud

Teda trA?d mA? jednA�ho rodiA?a a robotnica a krA?A?ovnA? dvoch rodiA?ov. KrA?A?ovnA? povA�A?A?inu svojho A?ivota rodA� robotnice a A?A�ri okolo seba feromA?ny, ktorA� zabraA?ujA? vA?voju novej krA?A?ovnej. Tieto vyprchajA?, keA? nadA�de A?as na novA? krA?A?ovnA?, naprA�klad vo vyA?A?om veku pA?vodnej.

PoA?me sa zameraA? na trA?dov rodokmeA?. MA?me

a��
kralovna
a��
trud
a��
kralovna
a��
kralovna
a��
trud
a��
kralovna
a��
trud
a��
trud
8
a��
kralovna
a��
trud
a��
kralovna
a��
kralovna
a��
trud
5
a��
kralovna
a��
trud
a��
kralovna
3
a��
kralovna
a��
trud
2
a��
kralovna
1
a��
trud
1

a keby sme pokraA?ovali, dostali by sme postupnosA?

    \[1,1,2,3,5,8,13,21,34,55,89...\]

OtA?zka, ktorA? si poloA?A�me znie: Za predpokladu, A?e sa krA?A?ovnA? nepA?ri s vlastnA?mi potomkami, koA?ko predkov mA? trA?d v rodokmeni v n-tej generA?ciA� dozadu?

Fibonacciho postupnosA?

UkA?A?ka z Liber Abbaci. PrvA?ch 13 Fibonacciho A?A�sel je vyA�sanA?ch v A?ervenom rA?miku vpravo v indicko-arabskom systA�me. (Zdroj: Wikipedia)

OznaA?me poA?et predkov v generA?ciA� n, F_n. PA�smeno F ako Fibonacci, alebo pre niekoho moA?no fA?ela… VA?imneme si, A?e pre poA?et predkov v n-tej generA?ciA� dozadu platA�

(1)   \begin{equation*} F_n = F_{n-1} + F_{n-2} \end{equation*}

s tA?m, A?e v generA?ciA� nula je iba trA?d samotnA? F_0 = 1 a generA?ciA� jedna je iba krA?A?ovnA? F_1 = 1. TA?to postupnosA? nazA?vame Fibonacciho postupnosA?ou.

Leonardo Bonacci, prezA?vanA? Fibonacci, bol taliansky matematik pA?sobiaci v Pise na prelome dvanA?steho a trinA?steho storoA?ia. V publikA?ciA� Liber Abbaci (1209) sa zaoberal sa podobnou A?lohou ako my, ale na krA?likoch.

VzA?ah (1) mA?A?eme odvodiA? aj rigorA?zne. Nech K_n je poA?et krA?A?ovien a T_n je poA?et trA?dov v n-tej generA?ciA� dozadu. OznaA?me teda celkovA? poA?et predkov

    \[F_n=T_n + K_n.\]

PoA?et trA?dov zrA?tame ako poA?et otcov krA?A?ovnA?ch v generA?ciA� n-1, to jest T_n = K_{n-1} a na A?vod T_0 = 1. KrA?A?ovnA� zrA?tame ako poA?et mA?m vA?etkA?ch trA?dov a krA?A?ovien z generA?cie n-1, teda K_n = T_{n-1} + K_{n-1} s K_0 = 0.

Dostaneme

    \begin{align*} F_n &= T_n + K_n \\    &= K_{n-1} + T_{n-1} + K_{n-1}\\    &= F_{n-1} + K_{n-1}\\    &= F_{n-1} + T_{n-2} + K_{n-2}\\    &= F_{n-1} + F_{n-2}. \end{align*}

s poA?iatoA?A?mi podmienkami

    \begin{align*} F_0 &= T_0 + K_0 \\     &= 1 \end{align*}

a

    \begin{align*} F_1 &= T_1 + K_1 \\     &= T_1 + T_0 + K_0\\     &= 1. \end{align*}

VzA?ah (1) nazA?vame rekurentnA? z francA?zskeho recourir – znovu beA?aA?. Ak nA?s zaujA�ma poA?et predkov v generA?ciA� 10 tak pomocou vzA?ahu vyrA?tame F_2 = F_1 + F_0 a znovu pomocou toho istA�ho vzA?ahu F_3 = F_2 + F_1 a takto ho nechA?me zopA?rkrA?t beA?at, aA? kA?m sa nedostaneme k A?A�slu F_{10}.

Teraz je vhodnA? doba zavolaA? na vA?pomoc PytA?na, programovacA� jazyk, ktorA? nA?m pomA?A?e toto vA?etko urobiA? za nA?s:

# kA?d sa dA? spustiA? naprA�klad cez https://try.jupyter.org, New -> Python 3
def fib(n):
    fib_cisla = [1, 1]
   
    for i in range(2, n + 1):
      fib_cisla += [fib_cisla[i - 1] + fib_cisla[i - 2]]
  
    return fib_cisla[n]

print(fib(10))
>>> 89

CviA?enie: fib(n) ukladA? n prvkov do pamA�ti v zozname fib_cisla. SkA?ste ho prepA�saA? tak, aby pouA?A�val iba trojprvkovA? zoznam. RieA?enie na konci A?lA?nku.

UzavretA? tvar

PokiaA? sa A?itateA? neuspokojil s algoritmickA?m rieA?enA�m, pravdepodobne mu vA�ta v hlave, A?A� by sa dala Fibonacciho postupnosA? vyjadrA�t v uzavretom tvare. To jest pomocou nejakA�ho vzorca, ktorA? je nezA?vislA? od predchA?dzajA?cich hodnA?t F_{n-1}, F_{n-2}, ... ale iba od n samotnA�ho

    \[F_n = f(n)\]

pre nejakA? funkciu f. TakA?to prepis by bol veA?mi pohodlnA? z vA?poA?tovA�ho hA?adiska, lebo pre lubovoA?nA� n by funkcia vykonala iba konA?tantnA? poA?et operA?ciA�. V informatike oznaA?ujeme ako O(1). Algoritmus, ktorA? sme uviedli v predchA?dzajA?cej sekciA�, na druhej strane, potrebuje vykonaA? n razy konA?tantnA? poA?et operA?ciA�, A?o zodpovedA? zloA?itosti O(n).

PoA?me sa na to pozrieA?. Jeden z A?A?innA?ch nA?strojov na rieA?enie vzA?ahov podobnA?ch typu (1) je skA?siA? rieA?enie uhA?dnuA?. VyskA?A?ajme teda predpokladaA?, A?e F_n mA? tvar

    \[F_n = r^n\]

pre nejakA? konA?tantu r. DosadA�me do rekurentnA�ho prepisu Fibonacciho postupnosti \label{eq:1} a dostA?vame r^n = r^{n-1} + r^{n-2}. VydelA�me r^{n-2} a zostane nA?m

    \[r^2 = r + 1\]

Toto je dobre znA?ma kvadratickA? rovnica r^2 - r - 1 = 0 s diskriminantom D = (-1)^2 - (4.1.(-1)) = 5, A?o zodpovedA? dvom rieA?eniam

    \begin{align*} r_1 = \frac{1 + \sqrt{5}}{2} \\ r_2 = \frac{1 - \sqrt{5}}{2}. \end{align*}

UA? sme skoro tam! VA?imnime si, A?e ak by sme poloA?ili F_n = r_1^n tak v rekurentnom prepise (1) sa A?avA? strana sa rovnA? pravej, dokonca F_0 = 1 ale bohuA?ial F_1 = r_1 \neq 1. To istA� platA� pre r_2. Ako sa vysporiadaA? s F_1 \neq 1?

VA?imnime si jednu dA?leA?itA? vlastnosA? Fibonacciho prepisu, ktorou je lineA?rnosA?. Ak je rieA?enA�m G_n = r_1^n aj H_n = r_2^n, tak A?A?vA? strana sa bude rovnaA? pravej aj pre

(2)   \begin{equation*} F_n = k . G_n + l . H_n \end{equation*}

s A?ubovoA?nA?mi konA?tantami k, l:

    \begin{align*} F_n &= k . G_n + l . H_n \\ &= k . (G_{n-1} + G_{n-2}) + l . (H_{n-1} + H_{n-2}) \\ &= k . G_{n-1} + l H_{n-1} + k . G_{n-2} + l H_{n-2} \\ &= F_{n-1} + F_{n-2}. \end{align*}

S tA?mto vA?eobecnA?m rieA?enA�m F_n sme ale vo veA?kej vA?hode, lebo si mA?A?eme vybraA? konA?tanty k,l tak aby platilo F_0 = 1 a F_1 = 1. DostA?vame sa k sA?stave

    \begin{align*} k + l &= 1 \\ k . r_1 + l . r_2 &= 1 \end{align*}

ktorej rieA?enA�m je

    \begin{align*} k &= \frac{1 + \sqrt{5}}{2\sqrt{5}} \\ l &= \frac{1 - \sqrt{5}}{2\sqrt{5}}. \end{align*}

DosadA�me k,l,G_n,H_n do (2) a po upravenA� dostA?vame

    \[\label{eq:3} F_{n}=\frac{1}{\sqrt{5}}\bigg[\bigg(\frac{1+\sqrt{5}}{2}\bigg)^{n+1}-\bigg(\frac{1-\sqrt{5}}{2}\bigg)^{n+1}\bigg].\]

Na tejto formule je jeden veA?mi zaujA�mavA? fakt a to, A?e hoc to tak nevyzerA?, keA? sa to vA?etko zrA?ta, dostaneme celA� A?A�slo 😯 .

PreverA�me v PytA?ne

# kA?d sa dA? spustiA? naprA�klad cez https://try.jupyter.org, New -> Python 3
def fib(n):
    od5 = 5 ** 0.5
    return (((1 + od5) / 2) ** (n + 1) - ((1 - od5) / 2) ** (n + 1)) / od5

print(fib(10))
>>> 89.00000000000003

PripomeA?me si, A?e \sqrt{5} = 5^{1/2}.

Teraz mA?A?e pozornA? A?itateA? protestovaA?: „Ha! VeA? 89.00000000000003 nie je celA� A?A�slo!“. Zhruba ide o to, A?e vo vnA?tri poA?A�taA?a sA? desatinnA� A?A�sla pre numerickA� vA?poA?ty zapA�sanA� v dvojkovej sA?stave s koneA?nA?m rozvojom. TakA?e pri vA?poA?te dochA?dza k chybA?m na vyA?A?A�ch desatinnA?ch miestach, pokiaA? mA? medzivA?poA?et nekoneA?nA? dvojkovA? rozvoj.

RieA?enie cviA?enia

# kA?d sa dA? spustiA? naprA�klad cez https://try.jupyter.org, New -> Python 3
def fib(n):
    fib_cisla = [1, 1, 0]
    for i in range(2, n + 1):
        fib_cisla[i % 3] = fib_cisla[(i + 1) % 3] + fib_cisla[(i + 2) % 3]
    
    return fib_cisla[n % 3]

print(fib(10))
>>> 89

Zdroje

Basin SL. The Fibonacci sequence as it appears in nature. Fibonacci Quarterly. 1963 Feb;1(1):53-6.
King, F. Probability, Part IA Lecture Notes. 1st ed. Cambridge University, 2003. Web. 7 Feb. 2016.
Knott, R. „Who was Fibonacci?“. Maths.surrey.ac.uk. Retrieved 2010-08-02.
Knott, R. „Fibonacci Numbers and Nature“. Maths.surrey.ac.uk. Retrieved 2016-02-07.
ObrA?zky vA?iel prevzatA� z: http://vcelamedonosnagc.blogspot.co.uk.