Lekce 1 - Faktoriál
V tomto kurzu si ukážeme matematické algoritmy se zdrojovými kódy. Ukážeme si například Euklidův algoritmus, Eratosthenovo síto či Algoritmus pro numerické integrování. Nyní se podíváme ale na faktoriál.
Faktoriál je funkce, která přiřadí každému kladnému celému číslu
x
takové číslo, které se rovná součinu všech čísel
menších nebo rovných x
.
Například tedy:
5! = 5 * 4 * 3 * 2 * 1 = 120
Faktoriál má jeden speciální případ, se kterým musíme počítat, a to: 0! = 1
Samotný algoritmus je velmi jednoduchý a lze ho napsat s rekurzí či bez rekurze. Jako první si uvedeme verzi bez rekurze.
Do proměnné s výsledkem si dosadíme číslo 1
. Výpočet
provedeme jednoduše cyklem od 2
do x
, přičemž v
každém kroku výsledek pronásobíme hodnotou proměnné cyklu. Cyklus by mohl
běžet i od 1
do x
, ale násobit něco jedničkou
nedává úplně smysl Také
by mohl běžet pozpátku, jako je faktoriál definován výše, ale popředu je
to přirozenější a při násobení nezáleží na pořadí čísel. Když se
zamyslíte, snadno uhodnete, že tento postup bude fungovat i pro
x=0
, protože na začátku se do výsledku dosadí jednička a
cyklus se pak už neprovede.
Jedná se o velmi rychle rostoucí funkci, tudíž si
dávejte pozor na výpočet faktoriálů vysokých čísel.
5! = 120
, ale 10!
je již v řádu milionů. Je tedy
třeba rozmyslet si výběr datového typu podle hodnot, které bude funkce
zpracovávat.
Funkce také musí být omezena jen pro kladná čísla včetně
nuly, protože se záporným argumentem nemá smysl. Je velmi vhodné
funkci faktoriál omezit na nějakou maximální hodnotu (zde 10
),
aby výpočet nezasekl program nebo nezavinil výjimku přetečení paměti.
Pokud budete chtít počítat vyšší faktoriály, je to s tímto algoritmem
samozřejmě možné, jen budete potřebovat nějakou knihovnu, která umožní
práci s velkými čísly.
Zdrojový kód - bez rekurze
-
public static int factorial(int x) { if (x < 0) throw new IllegalArgumentException("Argument je zaporny"); if (x > 10) throw new IllegalArgumentException("Prilis vysoka hodnota"); int result = 1; for (int i = 2; i <= x; i++) { result *= i; } return result; }
-
public static int factorial(int x) { if (x < 0) throw new System.ArgumentException("Argument je zaporny", "x"); if (x > 10) throw new System.ArgumentException("Prilis vysoka hodnota", "x"); int result = 1; for (int i = 2; i <= x; i++) { result *= i; } return result; }
-
function factorial(x: integer): longint; var vysledek, i: integer; begin if (x < 0) then Raise Exception.Create('Argument je zaporny'); if (x > 10) then Raise Exception.Create('Prilis vysoka hodnota'); vysledek:=1; for i:=2 to x do begin vysledek:=vysledek * i; end; result:=vysledek end;
-
def factorial(x) raise "Argument je zaporny" if (x < 0) raise "Prilis vysoka hodnota" if (x > 10) result = 1 2.upto(x) do |i| result *= i end return result end
Rekurzivně faktoriál naprogramujeme tak, že budeme vždy vracet parametr x a tím vynásobený výsledek funkce s parametrem o jednu menší. Když si rozmyslíme, kdy by se měla rekurze zastavit, dospějeme k podmínce x = 1. Pokud budeme chtít, aby nám funkce správě počítala i 0!, bude podmínka (x < 2).
Zdrojový kód - s rekurzí
-
public static int factorial(int x) { if (x < 0) throw new IllegalArgumentException("Argument je zaporny"); if (x > 10) throw new IllegalArgumentException("Prilis vysoka hodnota"); if (x < 2) return 1; return x * factorial(x - 1); }
-
public static int factorial(int x) { if (x < 0) throw new System.ArgumentException("Argument je zaporny", "x"); if (x > 10) throw new System.ArgumentException("Prilis vysoka hodnota", "x"); if (x < 2) return 1; return x * factorial(x - 1); }
-
function factorial(x: integer): longint; var i: integer; begin if (x < 0) then Raise Exception.Create('Argument je zaporny'); if (x > 10) then Raise Exception.Create('Prilis vysoka hodnota'); if (x < 2) then result:=1 else result:=x * factorial(x - 1); end;
-
def factorial(x) raise "Argument je zaporny" if (x < 0) raise "Prilis vysoka hodnota" if (x > 10) return 1 if (x < 2) return x * factorial(x - 1) end
V další lekci, Matice a základní operace s nimi, nejen v kódu, se seznámíme s pojmem matice a naučíme se základní matematické operace, které na ně lze aplikovat.