Fibonacciho posloupnost je nekonečná řada čísel, ve které je prvním číslem 0, druhým 1 a každé následující číslo je definováno jako součet dvou předchozích čísel. Řada proto začíná čísly 0, 1, 1, 2, 3, 5, 8, 13, 21, 34...

Řada byla vymyšlena italským matematikem Leonardem Pisanem (Fibonacci) ve dvanáctém století jako popis pro růst počtu králíků.

  • Na začátku se narodí 1 pár králíků.
  • Králící se mohou množit od druhého měsíce života.
  • Každý produktivní pár zplodí měsíčně jeden pár králíků.
  • Králíci neumírají, pokud jednou začnou plodit, tak plodí pořád.

Posloupnost v algoritmice

Z algoritmického hlediska je Fibonacciho posloupnost zajímavé téma – slouží jako odstrašující příklad toho, když se algoritmus vytváří přímým přepisem definice. V tomto případě se jedná o jednoduchou rekurzivní implementaci.

01./**
02. * Fibonacciho posloupnost rekurzivne
03. * @param index poradi cisla (pocitano od 0)
04. * @return Fibonacciho cislo na danem poradi
05. */
06.public static int fibonacciRek(int index){
07.    if(index == 0) return 0;
08.    else if(index == 1) return 1;
09.    else return fibonacciRek(index - 1) + fibonacciRek(index - 2);
10.}
01./**
02. * Fibonacci sequence
03. * @param to order of a number (counting from 0)
04. * @return Fibonacci number at the given position
05. * @autor Thomas (www.adamjak.net)
06. */
07.int fiborek(int to)
08.{
09.    if (to == 0)
10.    {
11.        return 0;
12.    }
13.    else if (to == 1)
14.    {
15.        return 1;
16.    }
17.    else
18.    {
19.        return fiborek(to - 2) + fiborek(to - 1);
20.    }
21.}
01./**
02. * Fibonacci sequence
03. * @param to order of a number (counting from 0)
04. * @return Fibonacci number at the given position
05. * @autor Thomas (www.adamjak.net)
06. */
07.public static int FibonacciRek(int to)
08.{
09.    if (to == 0)
10.    {
11.        return 0;
12.    }
13.    else if (to == 1)
14.    {
15.        return 1;
16.    }
17.    else
18.    {
19.        return FibonacciRek(to - 1) + FibonacciRek(to - 2);
20.    }
21.}
01./**
02. * Fibonacci sequence
03. * @param $to order of a number (counting from 0)
04. * @return Fibonacci number at the given position
05. * @autor Thomas (www.adamjak.net)
06. */
07.function fibonacci_rek($to) {
08.    if ($to == 0) {
09.        return 0;
10.    }
11.    else if ($to == 1){
12.        return 1;
13.    }
14.    else{
15.        return fibonacci_rek($to - 1) + fibonacci_rek($to - 2);
16.    }
17.}

Co je špatně na rekurzivní implementaci

Fibonacciho posloupnost
Fibonacciho posloupnost - větvení volání

Na rekurzivní implementaci je špatně nic a zároveň všechno. Algoritmus samozřejmě funguje, dává vždy dobrý výsledek. Jeho zásadní problém je ovšem v samotné rekurzi. Pokud počítáme rekurzivně posloupnost pro číslo 5, tak vidíme, že hodnotu 3 spočítáme 2x, 2 spočítáme 3x a na triviální hodnoty se podíváme dokonce 8x. Už nyní je vidět obrovská nehospodárnost, která se s vyšší hodnotou parametru funkce bude dále jen zhoršovat.

Jak na to lépe

Řešením je odstranění rekurze - převedení algoritmu do iterativní podoby. Toho lze v tomto případě dosáhnout prostřednictvím velmi jednoduchého dynamického programováním (je založeno na ukládání již vypočítaných hodnot, které jsou nutné pro další výpočet). V tomto případě zřídíme dvě pomocné proměnné, do kterých budeme ukládat předminulé a minulé vypočítané číslo. Výsledný algoritmus bude vypadat takto:

01./**
02. * Fibonacciho posloupnost dynamicky
03. * @param index poradi cisla (pocitano od 0)
04. * @return Fibonacciho cislo na danem poradi
05. */
06.public static int fibonacci(int index){
07.    if(index == 0) return 0;
08.    if(index == 1) return 1;
09.    int prePre = 0; //predminule cislo
10.    int pre = 1; //minule cislo
11.    int result = 0; //vysledek
12.    for(int i = 1; i < index; i++){ //pocitame od druheho indexu
13.        result = prePre + pre; //vysledek je soucet dvou minulych cisel
14.        prePre = pre; //v dalsim kroku je minule predminulym
15.        pre = result; //a vysledek je minulym cislem
16.    }
17.    return result;
18.}
01./**
02. * Fibonacci sequence
03. * @param to order of a number (counting from 0)
04. * @return Fibonacci number at the given position
05. * @autor Thomas (www.adamjak.net)
06. */
07.static int Fib(int to)
08.{
09.    if (to == 0)
10.    {
11.        return 0;
12.    }
13.    if (to == 1)
14.    {
15.        return 1;
16.    }
17. 
18.    int last_last = 0, last = 1, result = 0, i;
19. 
20.    for (i = 1; i < to; i++)
21.    {
22.        result = last_last + last;
23.        last_last = last;
24.        last = result;
25.    }
26. 
27.    return result;
28.}
01./**
02. * Fibonacci sequence
03. * @param to order of a number (counting from 0)
04. * @return Fibonacci number at the given position
05. * @autor Thomas (www.adamjak.net)
06. */
07.static int Fibonacci(int to)
08.{
09.    if (to == 0)
10.    {
11.        return 0;
12.    }
13.    if (to == 1)
14.    {
15.        return 1;
16.    }
17.    int last_last = 0;
18.    int last = 1;
19.    int result = 0;
20.    for (int i = 1; i < to; i++)
21.    {
22.        result = last_last + last;
23.        last_last = last;
24.        last = result;
25.    }
26.    return result;
27.}
01./**
02. * Fibonacci sequence
03. * @param $to order of a number (counting from 0)
04. * @return Fibonacci number at the given position
05. * @autor Thomas (www.adamjak.net)
06. */
07.function fibonacciho_postupnost($to) {
08.    if ($to == 0) {
09.        return 0;
10.    }
11.    if ($to == 1) {
12.        return 1;
13.    }
14.     
15.    $last_last = 0;
16.    $last = 1;
17.    $result = 0;
18.    for($i = 1; $i < $to; $i++){
19.        $result = $last_last + $last;
20.        $last_last = $last;
21.        $last = $result;
22.    }
23.    return $result;
24.     
25.}







       
 

Place for your banner

Here is the position ready for our customer's banners.