Fibonacciho postupnosť a včelí rodokmeň

V spoločenstvách včiel medonosných, môžeme osadenstvo rozdeliť na tri skupiny:

Jedna kráľovná kralovna
Robotnice robotnica
Trúdy trud

Rozmnožovanie prebieha tak, že kráľovná je oplodnená trúdom a kladie oplodnené vajíčka, z ktorých sa neskôr vyliahnu robotnice alebo nová kráľovná. Zároveň kladie neoplodnené vajíčka, z ktorých sa vyliahnu trúdy. Schematicky:

kralovna trud kralovna
kráľovná + trúd → robotnica alebo nová kráľovná
robotnica
/
kralovna
kráľovná → trúd
trud

Teda trúd má jedného rodiča a robotnica a kráľovná dvoch rodičov. Kráľovná poväčšinu svojho života rodí robotnice a šíri okolo seba feromóny, ktoré zabraňujú vývoju novej kráľovnej. Tieto vyprchajú, keď nadíde čas na novú kráľovnú, napríklad vo vyššom veku pôvodnej.

Poďme sa zamerať na trúdov rodokmeň. Máme


kralovna

trud

kralovna

kralovna

trud

kralovna

trud

trud
8

kralovna

trud

kralovna

kralovna

trud
5

kralovna

trud

kralovna
3

kralovna

trud
2

kralovna
1

trud
1

a keby sme pokračovali, dostali by sme postupnosť

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

Otázka, ktorú si položíme znie: Za predpokladu, že sa kráľovná nepári s vlastnými potomkami, koľko predkov má trúd v rodokmeni v n-tej generácií dozadu?

Fibonacciho postupnosť

Ukážka z Liber Abbaci. Prvých 13 Fibonacciho čísel je vyísaných v červenom rámiku vpravo v indicko-arabskom systéme. (Zdroj: Wikipedia)

Označme počet predkov v generácií n, F_n. Písmeno F ako Fibonacci, alebo pre niekoho možno fčela… Všimneme si, že pre počet predkov v n-tej generácií dozadu platí

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

s tým, že v generácií nula je iba trúd samotný F_0 = 1 a generácií jedna je iba kráľovná F_1 = 1. Túto postupnosť nazývame Fibonacciho postupnosťou.

Leonardo Bonacci, prezývaný Fibonacci, bol taliansky matematik pôsobiaci v Pise na prelome dvanásteho a trinásteho storočia. V publikácií Liber Abbaci (1209) sa zaoberal sa podobnou úlohou ako my, ale na králikoch.

Vzťah (1) môžeme odvodiť aj rigorózne. Nech K_n je počet kráľovien a T_n je počet trúdov v n-tej generácií dozadu. Označme teda celkový počet predkov

    \[F_n=T_n + K_n.\]

Počet trúdov zrátame ako počet otcov kráľovných v generácií n-1, to jest T_n = K_{n-1} a na úvod T_0 = 1. Kráľovné zrátame ako počet mám všetkých trúdov a kráľovien z generá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 počiatočý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*}

Vzťah (1) nazývame rekurentný z francúzskeho recourir – znovu bežať. Ak nás zaujíma počet predkov v generácií 10 tak pomocou vzťahu vyrátame F_2 = F_1 + F_0 a znovu pomocou toho istého vzťahu F_3 = F_2 + F_1 a takto ho necháme zopárkrát bežat, až kým sa nedostaneme k číslu F_{10}.

Teraz je vhodná doba zavolať na výpomoc Pytóna, programovací jazyk, ktorý nám pomôže toto všetko urobiť za nás:

# kód sa dá spustiť naprí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

Cvičenie: fib(n) ukladá n prvkov do pamäti v zozname fib_cisla. Skúste ho prepísať tak, aby používal iba trojprvkový zoznam. Riešenie na konci článku.

Uzavretý tvar

Pokiaľ sa čitateľ neuspokojil s algoritmickým riešením, pravdepodobne mu vŕta v hlave, čí by sa dala Fibonacciho postupnosť vyjadrít v uzavretom tvare. To jest pomocou nejakého vzorca, ktorý je nezávislý od predchádzajúcich hodnôt F_{n-1}, F_{n-2}, ... ale iba od n samotného

    \[F_n = f(n)\]

pre nejakú funkciu f. Takýto prepis by bol veľmi pohodlný z výpočtového hľadiska, lebo pre lubovoľné n by funkcia vykonala iba konštantný počet operácií. V informatike označujeme ako O(1). Algoritmus, ktorý sme uviedli v predchádzajúcej sekcií, na druhej strane, potrebuje vykonať n razy konštantný počet operácií, čo zodpovedá zložitosti O(n).

Poďme sa na to pozrieť. Jeden z účinných nástrojov na riešenie vzťahov podobných typu (1) je skúsiť riešenie uhádnuť. Vyskúšajme teda predpokladať, že F_n má tvar

    \[F_n = r^n\]

pre nejakú konštantu r. Dosadíme do rekurentného prepisu Fibonacciho postupnosti \label{eq:1} a dostávame r^n = r^{n-1} + r^{n-2}. Vydelíme r^{n-2} a zostane nám

    \[r^2 = r + 1\]

Toto je dobre známa kvadratická rovnica r^2 - r - 1 = 0 s diskriminantom D = (-1)^2 - (4.1.(-1)) = 5, čo zodpovedá dvom riešeniam

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

Už sme skoro tam! Všimnime si, že ak by sme položili F_n = r_1^n tak v rekurentnom prepise (1) sa ľavá strana sa rovná pravej, dokonca F_0 = 1 ale bohužial F_1 = r_1 \neq 1. To isté platí pre r_2. Ako sa vysporiadať s F_1 \neq 1?

Všimnime si jednu dôležitú vlastnosť Fibonacciho prepisu, ktorou je lineárnosť. Ak je riešením G_n = r_1^n aj H_n = r_2^n, tak ľává strana sa bude rovnať pravej aj pre

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

s ľubovoľnými konš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 týmto všeobecným riešením F_n sme ale vo veľkej výhode, lebo si môžeme vybrať konštanty k,l tak aby platilo F_0 = 1 a F_1 = 1. Dostávame sa k sústave

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

ktorej riešením je

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

Dosadíme k,l,G_n,H_n do (2) a po upravení dostá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 veľmi zaujímavý fakt a to, že hoc to tak nevyzerá, keď sa to všetko zráta, dostaneme celé číslo 😯 .

Preveríme v Pytóne

# kód sa dá spustiť naprí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

Pripomeňme si, že \sqrt{5} = 5^{1/2}.

Teraz môže pozorný čitateľ protestovať: „Ha! Veď 89.00000000000003 nie je celé číslo!“. Zhruba ide o to, že vo vnútri počítača sú desatinné čísla pre numerické výpočty zapísané v dvojkovej sústave s konečným rozvojom. Takže pri výpočte dochádza k chybám na vyšších desatinných miestach, pokiaľ má medzivýpočet nekonečný dvojkový rozvoj.

Riešenie cvičenia

# kód sa dá spustiť naprí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.
Obrázky včiel prevzaté z: http://vcelamedonosnagc.blogspot.co.uk.

Pridaj komentár

Vaša e-mailová adresa nebude zverejnená. Vyžadované polia sú označené *