Fibonacciho posloupnost je nekonečnou posloupností přirozených čísel, kde každý následující člen, kromě prvních dvou, je vyjádřen výsledkem součtu dvou předcházejících čísel. Tato posloupnost byla popsána matematikem Leonardo Pisano, který je také znám právě jako Fibonacci. Čísla, která se nacházejí v této posloupnosti jsou často nazývána Fibonacciho čísly.
Prvních 20 členů Fibonacciho posloupnosti - 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181
První dva členy jsou dány pevně, jako 0 a 1.
F(n) můžeme vyjádřit jako:
F(n) = F(n - 2) + F(n - 1) -> To samozřejmě neplatí pro první dva členy.
Ještě si dovolím odkázat na obrázek z wikipedie.
Po prvním pohledu na definici této posloupnosti je jasné, že by se tento úkon velice snadno řešil pomocí rekurze, což si také ukážeme. Tento algoritmus ale není opravdu moc efektivní, a je časově poměrně náročný - jeho asymptotická složitost se pohybuje v exponenciálním čase. Mnohem kvalitenějšího a efektivnějšího zápisu bychom dosáhli pomocí dynamického programování, ale o tom možná až jindy.
Implementace do Javy:
public static int fibonacci(int n) {
if(n < 2)
return n;
else
return fibonacci(n - 1) + fibonacci(n - 2);
}
Vytvořili jsme si jednoduchou statickou rekurzivní metodu, která nám vrací celé číslo datového typu int. Pomocí této metody si můžeme ku příkladu vypisovat řadu čísel, které se řídí Fibonacciho posloupností. Kdybychom tedy chtěli vypsat prvních 30 členů Fibonacciho posloupnosti, můžeme to provédst třeba takto.
public static void main(String[] args) {
for(int i = 0;i<30;i++) {
System.out.print(fibonacci(i) + " ");
}
}
Výpis by v tomto případě vypadal takto - 0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946 17711 28657 46368 75025 121393 196418 317811 514229
Další informace ohledně Fibonacciho posloupnosti najdete třeba na české wikipedii.
2009-11-28 14:29:23
nevi nekdo jak by se daly tyto cisla ulozit do pole?? ja kdyz se pokousim to tam nejak nacpat a pak ho vypisu tak me to pokazde vypisuje nesmyslne cisla... delam co v C++ ale to je podobne...:-)