Fibonacciho posloupnost

V tomto článku si přiblížíme, co je to Fibonacciho posloupnost a s ní související další pojmy, které se často používají v matematice a dalších disciplínách.

Fibonacciho posloupnost

Jedná se o matematickou posloupnost, která začíná čísly 0 a 1. Každé další číslo je poté součet dvou předchozích čísel. Číslům v této posloupnosti se říká Fibonacciho čísla.

Začátek posloupnosti tedy vypadá takto:

0

1

1

2

3

5

8

13

21

34

55

89

144

...

Z vývojářského pohledu si s touto definicí vystačíme. Oblíbené programátorské úlohy jsou např. jak Fibonnaciho čísla dostat např. do pole a následně z pole vypsat x-té číslo. Nebo jak tuto posloupnost vypsat pozpátku a podobně.

Matematicky se dá Fibonacciho posloupnost vyjádřit také rekurzivně, explicitně nebo maticí. Maticemi se nebudeme zabývat, další vyjádření si v článku ukážeme.

Fibonacciho králíci

Fibonacci popsal svou posloupnost na množení populace králíků. S tímto příkladem jste se s největší pravděpodobností již někdy setkali. Jedná se o na první pohled jednoduchý matematický příklad, kdy na začátku máme:

• jeden pár králíků (samce a samici)
• pár je produktivní od druhého měsíce života
• každý měsíc zplodí každý produktivní pár jeden další pár
• platí ideální podmínky, králíci nikdy neumírají, nejsou nemocní apod.

Pro výpis této posloupnosti se často používá jen jednoduchý průchod cyklem a pomocné proměnné, kde máme uložené předchozí dva prvky, abychom dokázali vypočítat prvek následující.

Algoritmus

Teď si můžeme zkusit naprogramovat jednoduchý příklad, kdy pomocí vnořených cyklu necháme do řádků pod sebe vypisovat jednotlivé počty králíků podle Fibonnaciho poslounopsti. Por názornost použijeme obrázek králíka níže :

Jelikož by bylo trochu náročnější vypsat zdrojový kód pro všechny možné programovací jazyky, vezmu to obecněji (za příklad poslouží kód v JavaScriptu). Bude nutné si vytvořit 2 proměnné, např. predminula a minula pro počet v předchozích dvou generacích králíků. Uložíme do nich hodnoty 0 a 1. Dále pak budeme potřebovat proměnnou soucasna, do které se bude ukládat mezivýsledek, počet králíků současné generace. Prvnímu cyklu nastavíme, kolikrát se má zopakovat (počet generací k výpisu). Samotná Fibonacciho posloupnost samozřejmě nemá konečné číslo. Druhý cyklus nám bude vypisovat obrázky králíků:

let predminula = 0;
let minula = 1;

for(let i = 3; i<10; i++) {
    let soucasna = predminula + minula;
    predminula = minula;
    minula = soucasna;

    for(let j = 0; j < soucasna; j++) {
        document.write('<img src="rabbit.png" width="32" height="32">');
    }
    document.write("<br />");
}

V každém průběhu cyklu vypočítáme počet králíků v současné generaci jako součet králíků v předchozích dvou generacích. Současná generace se poté pro další běh cyklu stává minulou a minulá předminulou.

Výsledek:

Rekurzivní algoritmus

Určitě vás napadlo, že by se n-tý prvek v řadě dal zjistit i rekurzí. Daná funkce by vypadala takto:

function fibonacci(n) {
  if (n < 2)
    return n;
  else
    return fibonacci(n - 1) + fibonacci(n - 2)
}

Pokud chceme nultý nebo první prvek, je výsledkem 0, resp. 1. Tím se splní podmínka ukončení rekurze. Pokud chceme prvek pro n od 2 a více, vrátíme součet prvků pro n - 1 a n - 2, tedy 2 předchozí prvky posloupnosti. Rekurze takto postupně postoupí od vysokých n až ke známým hodnotám pro 0 a 1 a pomocí těchto výsledků se zpětně sestaví n-tý prvek.

Rekurzivní řešení je méně efektivní než řešení cyklem, jelikož vyžaduje dodatečnou paměť zásobníku k udržení všech vnořených volání funkce.

Zlatý řez a explicitní vyjádření

N-tý prvek Fibonacciho posloupnosti můžeme i vypočítat pomocí vzorečku, bez nutnosti použití členů předchozích. Jak asi tušíte, řešení bude mnohem složitější a také méně přesné, proto tato metoda není v programování preferována.

Se Zlatým řezem, tzv. "ideální proporcí", se můžeme setkat například v umění nebo v přírodě (šnečí ulity, schránky dalších měkkýšů, zobáky, rohy...), ale také v umění (proporce obrazů, fotografií, rozvržení hudby, knih, scénářů,...).

Hodnota Zlatého řezu se velice blíží hodnotě Fí (φ), což je iracionální číslo. Dá se vypočítat jako: φ = (1+√5) / 2 ≈ 1,618.

Této hodnotě se blíží rychlost růstu Fibonacciho posloupnosti. Fibonacciho spirála je tudíž často vnímána jako synonymum pro Zlatý řez.

Díky Zlatému řezu, technice generujících funkcí, nebo za pomoci řešení rekurentních rovnic, lze dospět k explicitnímu (nerekurzivnímu) vztahu pro n-tý člen Fibonacciho posloupnosti, který vypadá takto:

Kde:

• φ ≈ 1,618
• n - n-tý člen posloupnosti
• F - podle Fibonacciho, označuje výsledek

Druhý člen této rovnice se s rostoucím n blíží nule. Asymptotické chování Fibonacciho posloupnosti je tudíž dáno prvním členem.

Ve skutečnosti je druhý člen malý i pro malá n, takže jej lze zcela zanedbat a získávat Fibonacciho čísla prostým zaokrouhlováním prvního členu na nejbližší celé číslo.

To je k základní problematice Fibonacciho posloupnosti asi vše. Děkuji za pozornost a doufám, že jste se dozvěděli něco nového!