Faktoriál se často v programování řadí mezi začátečnické úlohy. Na mnoha školách, kde se vyučují alespoň nějaké základy programování se studenti s faktoriálem setkávají poměrně často. Nějakou dobu jsem se zamýšlel, jestli má vůbec smysl o něčem, jako je faktoriál vůbec psát, ale nakonec jsem se rozhodl, že napíšu takový malý přehled, jak lze faktoriál zapsat.
Co to vlastně faktoriál je? Faktoriál je jednoduše řečeno číslo, které je rovné součinu všech celých čísel menších a rovných našemu "vstupnímu" číslu. V matematice se faktoriál označuje pomocí znaku ! - takže jako n!, kde n bude nějaké celé kladné číslo (případně 0).
Dovolím si vypůjčit obrázek obecného vzorce faktoriálu z wikipedie.
Aby jsme si také ukázali alespoň jeden příklad, tak vypočítáme 4!. Výsledek bude 24. Jak jsme k němu tedy došli?
4! = 4 * 3 * 2 * 1 = 24
Počítání faktoriálu je tedy velice snadné. Ukážeme si, jak počítat v Javě faktoriál třemi způsoby. První metoda bude provádět výpočet pomocí cyklu. Další dvě metody budou demonstrovat výpočet faktoriálu pomocí rekurze. První příklad s použitím rekurze bude využívat takzvanou "přirozenou" rekurzi, kdežto druhý bude demonstrovat rekurzi s pomocným parametrem. Všechny příklady jsou psané jako statické metody datového typu long. Na konci článku také uvedu časové srovnání všech metod.
Implementace faktoriálu do Javy za prvé:
public static long faktorial1(int cislo) {
int vysledek = 1;
for(int i = cislo;i > 0;i--) {
vysledek *= i;
}
return vysledek;
}
Opravdu snadná metoda. Používá cyklus for, ve kterém násobí výsledné číslo všemi n většími než nula. Cyklus for můžeme samozřejmě nahradit řádně upraveným cyklem while.
Implementace faktoriálu do Javy po druhé:
public static long faktorial2(long cislo) {
if(cislo == 1 || cislo == 0)
return 1;
else
return cislo*faktorial2(cislo - 1);
}
Zde již používáme přirozenou rekurzi. Myslím, že zde není třeba nic vysvětlovat - stačí, aby každý chápal, jak rekurze funguje. Dobré informace o rekurzi jsou například na wikipedii.
Implementace faktoriálu do Javy po třetí:
public static long faktorial3(int cislo, long vysledek) {
if(cislo == 1 || cislo == 0)
return vysledek;
else
return faktorial3(cislo-1,cislo*vysledek);
}
Na tomto příkladě jsme použili rekurzi s pomocným parametrem. Metoda si stále předává, jaké je zrovna n a jaký je aktuální výsledek. Nevýhodou zřejmě bude to, že když tuto metodu voláme, musíme zadávat dva parametry, z toho druhý musí být vždy 1.
Časová obtížnost:
Priklad 1 - faktorial cisla 7 je 5040. Vypocitano za 4792.0 ns.
Priklad 2 - faktorial cisla 7 je 5040. Vypocitano za 15584.0 ns.
Priklad 3 - faktorial cisla 7 je 5040. Vypocitano za 18931.0 ns.
Jak vidíme, tak je výpočet faktoriálu čísla 7 přibližně 3x až 4x rychlejší pomocí počítání cyklem, než rekurzí. Tyto časy se samozřejmě budou každým spuštěním trochu lišit, ale průměrně budou vypadat pořád stejně.
