ITnetwork Flashka zdarma C# týden
Akce! Pouze tento týden sleva až 80 % na kurzy C# .NET. Lze kombinovat s akcí 50 % bodů navíc na prémiový obsah!
Brno? Vypsali jsme pro vás nové termíny školení Základů programování a OOP v Brně!

Faktoriál

Unicorn College Tento obsah je dostupný zdarma v rámci projektu IT lidem.
Vydávání, hosting a aktualizace umožňují jeho sponzoři.

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.

Poznámka: 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

 

 

Článek pro vás napsal David Čápka
Avatar
Jak se ti líbí článek?
6 hlasů
Autor pracuje jako softwarový architekt a pedagog na projektu ITnetwork.cz (a jeho zahraničních verzích). Velmi si váží svobody podnikání v naší zemi a věří, že když se člověk neštítí práce, tak dokáže úplně cokoli.
Unicorn College Autor sítě se informační technologie naučil na Unicorn College - prestižní soukromé vysoké škole IT a ekonomie.
Všechny články v sekci
Matematické algoritmy
Miniatura
Následující článek
Generování (pseudo)náhodných čísel
Aktivity (1)

 

 

Komentáře
Zobrazit starší komentáře (11)

Avatar
Hynek
Člen
Avatar
Hynek:26.2.2013 17:29

Ahoj chci se zeptat jaké existují datové typy větší než long, aby se tenhle algoritmus dal použít i pro větší čísla.

 
Odpovědět 26.2.2013 17:29
Avatar
Silvinios
Redaktor
Avatar
Silvinios:4.12.2013 17:55

Existuje nějaký důvod proč k výpočtu faktoriálu použít rekurzi? Jediný důvod, který mě napadá, je procvičení rekurze.

 
Odpovědět 4.12.2013 17:55
Avatar
David Čápka
Tým ITnetwork
Avatar
Odpovídá na Silvinios
David Čápka:21.3.2014 16:18

Kód s rekurzí je IMHO většinou kratší, protože se ušetří cyklus. Naopak je méně na první pohled vidět co že to vlastně dělá.

Odpovědět  +1 21.3.2014 16:18
Jsem moc rád, že jsi na síti, a přeji ti top IT kariéru, ať jako zaměstnanec nebo podnikatel. Máš na to! :)
Avatar
Silvinios
Redaktor
Avatar
Odpovídá na David Čápka
Silvinios:22.3.2014 20:05

Kratší sice je, ale také je pomalejší. U rekurze navíc může dojít k přetečení zásobníku. Pokud si článek přečte začátečník, může mít dojem, že řešení s rekurzí je správné. Podle mě ale není. Rekurze by se měla používat jen tam, kde to má smysl. Navrhuji doplnit do článku něco v smyslu: "takto lze naprogramovat faktoriál rekurzivně, ale takové řešení má následující nevýhody...".

 
Odpovědět 22.3.2014 20:05
Avatar
Odpovídá na Silvinios
Patrik Pastor:30. května 8:16

a kdy ma rekurze vubec smysl? pokud mi zere vice pamrti, proc bych mel motivaci ji vubec implementovat? Jenom abych usetril par radku psani?

 
Odpovědět 30. května 8:16
Avatar
DarkCoder
Člen
Avatar
Odpovídá na Patrik Pastor
DarkCoder:30. května 10:00

Některé algoritmy bývá obtížné napsat jiným způsobem nežli za použití rekurze. Použití rekurzivních funkcí může výrazně zjednodušit řešení úlohy. Výpočet faktoriálu je natolik jednoduchá aplikace, že ji lze snadno přepsat za pomoci iterace.

Odpovědět 30. května 10:00
"„Učíš-li se proto, aby sis zapamatoval, zapomeneš. Učíš-li se proto, abys porozuměl, zapamatuješ si."
Avatar
Odpovídá na DarkCoder
Patrik Pastor:30. května 10:02

nejaky priklad? kdy by rekurze mela vylozene lepsi implementaci reseni ulohy, nezli klasicky cyklus?

 
Odpovědět 30. května 10:02
Avatar
DarkCoder
Člen
Avatar
Odpovídá na Patrik Pastor
DarkCoder:30. května 10:09

Třeba QuickSort.

Odpovědět 30. května 10:09
"„Učíš-li se proto, aby sis zapamatoval, zapomeneš. Učíš-li se proto, abys porozuměl, zapamatuješ si."
Avatar
Odpovídá na DarkCoder
Patrik Pastor:30. května 14:22

a proc je u quicksortu rekurze lepsi? tridici algoritmy jsem se dival a je tam i bez rekurze, proc by mela byt rekurze lepsi??

 
Odpovědět 30. května 14:22
Avatar
Tricerator
Redaktor
Avatar
Odpovídá na Patrik Pastor
Tricerator:1. června 17:15

Podle me je dulezite si uvedomit, co presne rekurze dela. Neni rekurze jako rekurze. Pokud mas algoritmus, ktery provadi Divide et impera - rozdel a panuj, neboli kde si problem rozdelis na dva mensi celky (idealne polovicni) a ty muzes samostatne resit, je rekurze docela dobrou metodou. Proto to u faktorialu nema smysl, zde se problem zmensi pouze o 1. Rekurze ti totiz pomaha dostat se do nejakeho stavu. Samozrejme cokoliv muzes napsat bez rekurze a nekdy to bude lepsi bez ni.

Problem u rekurze je v tom, ze se uklada na zasobnik volani fce atd... Pokud vsak chces rekurzi nahradit iteraci, je mozne, ze ve vysledku ti kvuli praci s jinymi datovymi typy vyjde lepe rekurzivni algoritmus. Rekurze je pomala. A iterace neni o moc rychlejsi :D Pokud ti jde opravdu o optimalizaci kodu, rozhodne bych nejdrive optimalizoval O(). Navic, existuje jeste tzv. tail rekurze, ktera optimalizuje i samotnou rekurzi. Neboli kdyz potrebujes najit nejaky stav, nemusis si pamatovat ty predchozi. No a tam uz se neni o cem bavit, pres iteraci bych to rozhodne nedelal.

V neposledni rade si vezmeme, o jake casove uspore se bavime. Pokud mi neiterativni reseni bude trvat v O notaci stejne dlouho, sahnu po tom, co rychleji a snadneji naprogramuji. A pokud jde o pamet, muzes si u rekurze rict - tahle vetev nikam nevede, odriznu ji - a usetrena pamet se hezky leze na povrch...

Odpovědět  +3 1. června 17:15
Raduj se z bugu. Tedy z toho, ktery jsi uz nasel...
Děláme co je v našich silách, aby byly zdejší diskuze co nejkvalitnější. Proto do nich také mohou přispívat pouze registrovaní členové. Pro zapojení do diskuze se přihlas. Pokud ještě nemáš účet, zaregistruj se, je to zdarma.

Zobrazeno 10 zpráv z 21. Zobrazit vše