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.
/**
* Fibonacciho posloupnost rekurzivne
* @param index poradi cisla (pocitano od 0)
* @return Fibonacciho cislo na danem poradi
*/
public static int fibonacciRek(int index){
if(index == 0) return 0;
else if(index == 1) return 1;
else return fibonacciRek(index - 1) + fibonacciRek(index - 2);
}
/**
* Fibonacci sequence
* @param to order of a number (counting from 0)
* @return Fibonacci number at the given position
* @autor Thomas (www.adamjak.net)
*/
int fiborek(int to)
{
if (to == 0)
{
return 0;
}
else if (to == 1)
{
return 1;
}
else
{
return fiborek(to - 2) + fiborek(to - 1);
}
}
/**
* Fibonacci sequence
* @param to order of a number (counting from 0)
* @return Fibonacci number at the given position
* @autor Thomas (www.adamjak.net)
*/
public static int FibonacciRek(int to)
{
if (to == 0)
{
return 0;
}
else if (to == 1)
{
return 1;
}
else
{
return FibonacciRek(to - 1) + FibonacciRek(to - 2);
}
}
/**
* Fibonacci sequence
* @param $to order of a number (counting from 0)
* @return Fibonacci number at the given position
* @autor Thomas (www.adamjak.net)
*/
function fibonacci_rek($to) {
if ($to == 0) {
return 0;
}
else if ($to == 1){
return 1;
}
else{
return fibonacci_rek($to - 1) + fibonacci_rek($to - 2);
}
}
Co je špatně na rekurzivní implementaci
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:
/**
* Fibonacciho posloupnost dynamicky
* @param index poradi cisla (pocitano od 0)
* @return Fibonacciho cislo na danem poradi
*/
public static int fibonacci(int index){
if(index == 0) return 0;
if(index == 1) return 1;
int prePre = 0; //predminule cislo
int pre = 1; //minule cislo
int result = 0; //vysledek
for(int i = 1; i < index; i++){ //pocitame od druheho indexu
result = prePre + pre; //vysledek je soucet dvou minulych cisel
prePre = pre; //v dalsim kroku je minule predminulym
pre = result; //a vysledek je minulym cislem
}
return result;
}
/**
* Fibonacci sequence
* @param to order of a number (counting from 0)
* @return Fibonacci number at the given position
* @autor Thomas (www.adamjak.net)
*/
static int Fib(int to)
{
if (to == 0)
{
return 0;
}
if (to == 1)
{
return 1;
}
int last_last = 0, last = 1, result = 0, i;
for (i = 1; i < to; i++)
{
result = last_last + last;
last_last = last;
last = result;
}
return result;
}
/**
* Fibonacci sequence
* @param to order of a number (counting from 0)
* @return Fibonacci number at the given position
* @autor Thomas (www.adamjak.net)
*/
static int Fibonacci(int to)
{
if (to == 0)
{
return 0;
}
if (to == 1)
{
return 1;
}
int last_last = 0;
int last = 1;
int result = 0;
for (int i = 1; i < to; i++)
{
result = last_last + last;
last_last = last;
last = result;
}
return result;
}
/**
* Fibonacci sequence
* @param $to order of a number (counting from 0)
* @return Fibonacci number at the given position
* @autor Thomas (www.adamjak.net)
*/
function fibonacciho_postupnost($to) {
if ($to == 0) {
return 0;
}
if ($to == 1) {
return 1;
}
$last_last = 0;
$last = 1;
$result = 0;
for($i = 1; $i < $to; $i++){
$result = $last_last + $last;
$last_last = $last;
$last = $result;
}
return $result;
}