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
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.
}