Fibonacciho postupnosť

V tomto článku si priblížime, čo je to Fibonacciho postupnosť as ňou súvisiace ďalšie pojmy, ktoré sa často používajú v matematike a ďalších disciplínach.

Fibonacciho postupnosť

Jedná sa o matematickú postupnosť, ktorá začína číslami 0 a 1. Každé ďalšie číslo je potom súčet dvoch predchádzajúcich čísel. Číslam v tejto postupnosti sa hovorí Fibonacciho čísla.

Začiatok postupnosti teda vyzerá takto:

0

1

1

2

3

5

8

13

21

34

55

89

144

...

Z vývojárskeho pohľadu si s touto definíciou vystačíme. Obľúbené programátorské úlohy sú napr. Ako Fibonnaciho čísla dostať napr. Do pole a následne z poľa vypísať x-tej číslo. Alebo ako túto postupnosť vypísať pospiatky a podobne.

Matematicky sa dá Fibonacciho postupnosť vyjadriť tiež rekurzívne, explicitne alebo maticou. Maticami sa nebudeme zaoberať, ďalšie vyjadrenia si v článku ukážeme.

Fibonacciho králiky

Fibonacci popísal svoju postupnosť na množenie populácie králikov. S týmto príkladom ste sa s najväčšou pravdepodobnosťou už niekedy stretli. Jedná sa o na prvý pohľad jednoduchý matematický príklad, kedy na začiatku máme:

• jeden pár králikov (samca a samicu)
• pár je produktívny od druhého mesiaca života
• každý mesiac splodí každý produktívny pár jeden ďalší pár
• platia ideálne podmienky, králiky nikdy neumierajú, nie sú chorí a pod.

Pre výpis tejto postupnosti sa často používa len jednoduchý priechod cyklom a pomocné premenné, kde máme uložené predchádzajúce dva prvky, aby sme dokázali vypočítať prvok nasledujúce.

Algoritmus

Teraz si môžeme skúsiť naprogramovať jednoduchý príklad, kedy pomocou vnorených cyklu necháme do riadkov pod seba vypisovať jednotlivé počty králikov podľa Fibonnaciho poslounopsti. Por názornosť použijeme obrázok králika nižšie :

Keďže by bolo trochu náročnejšie vypísať zdrojový kód pre všetky možné programovacie jazyky, vezmem to všeobecnejšie (za príklad poslúži kód v JavaScriptu). Bude nutné si vytvoriť 2 premenné, napr. predminula a minula pre počet v predchádzajúcich dvoch generáciách králikov. Uložíme do nich hodnoty 0 a 1. Ďalej potom budeme potrebovať premennú soucasna, do ktorej sa bude ukladať medzivýsledok, počet králikov súčasnej generácie. Prvému cyklu nastavíme, koľkokrát sa má zopakovať (počet generácií k výpisu). Samotná Fibonacciho postupnosť samozrejme nemá konečné číslo. Druhý cyklus nám bude vypisovať obrázky králikov:

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ždom priebehu cyklu vypočítame počet králikov v súčasnej generácii ako súčet králikov v predchádzajúcich dvoch generáciách. Súčasná generácia sa potom pre ďalší beh cyklu stáva minulú a minulá predminulú.

výsledok:

Rekurzívny algoritmus

Určite vás napadlo, že by sa n-tý prvok v rade dal zistiť aj rekurziu. Daná funkcia by vyzerala takto:

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

Ak chceme nultý alebo prvý prvok, je výsledkom 0, resp. 1. Tým sa splní podmienka ukončenia rekurzia. Ak chceme prvok pre n od 2 a viac, vrátime súčet prvkov pre n - 1 a n - 2, teda 2 predchádzajúce prvky postupnosti. Rekurzia takto postupne postúpi od vysokých n až k známym hodnotám pre 0 a 1 a pomocou týchto výsledkov sa spätne zostaví n-tý prvok.

Rekurzívne riešenie je menej efektívne než riešenie cyklom, pretože si vyžaduje dodatočnú pamäť zásobníka na udržanie všetkých vnorených volanie funkcie.

Zlatý rez a explicitné vyjadrenie

N-tý prvok Fibonacciho postupnosti môžeme aj vypočítať pomocou vzorca, bez nutnosti použitia členov predchádzajúcich. Ako asi tušíte, riešenie bude oveľa zložitejšie a tiež menej presné, preto táto metóda nie je v programovaní preferovaná.

So Zlatým rezom, tzv. "Ideálne proporcií", sa môžeme stretnúť napríklad v umení alebo v prírode (slimačie ulity, schránky iných mäkkýšov, zobáky, rohy ...), ale aj v umení (proporcie obrazov, fotografií, rozvrhnutie hudby, kníh , scenárov, ...).

Hodnota Zlatého rezu sa veľmi blíži hodnote PHI (φ), čo je iracionálne číslo. Dá sa vypočítať ako: φ = (1+√5) / 2 ≈ 1,618.

Tejto hodnote sa blíži rýchlosť rastu Fibonacciho postupnosti. Fibonacciho špirála je teda často vnímaná ako synonymum pre Zlatý rez.

Vďaka Zlatému rezu, technike generujúcich funkcií, alebo za pomoci riešenie rekurentných rovníc, možno dospieť k výslovnému (nerekurzivnímu) vzťahu pre n -Ty člen Fibonacciho postupnosti, ktorý vyzerá takto:

kde:

• φ ≈ 1,618
• n - n-tý člen postupnosti
• F - podľa Fibonacciho, označuje výsledok

Druhý člen tejto rovnice sa s rastúcim n blíži nule. Asymptotickej správanie Fibonacciho postupnosti je teda dané prvým členom.

V skutočnosti je druhý člen malý aj pre malé n, takže ho možno úplne zanedbať a získavať Fibonacciho čísla prostým zaokrúhľovaním prvého člena na najbližšie celé číslo.

To je k základnej problematike Fibonacciho postupnosti asi všetko. Ďakujem za pozornosť a dúfam, že ste sa dozvedeli niečo nové!