Hledáme nové posily do ITnetwork týmu. Podívej se na volné pozice a přidej se do nejagilnější firmy na trhu - Více informací.
Pouze tento týden sleva až 80 % na e-learning týkající se Swiftu. Zároveň využij výhodnou slevovou akci až 30 % zdarma při nákupu e-learningu - více informací.
swift week + discount 30

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.

Tento výukový obsah pomáhají rozvíjet následující firmy, které dost možná hledají právě tebe!

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.


 

Všechny články v sekci
Matematické algoritmy
Přeskočit článek
(nedoporučujeme)
Matice a základní operace s nimi, nejen v kódu
Článek pro vás napsal David Čápka
Avatar
Uživatelské hodnocení:
10 hlasů
David je zakladatelem ITnetwork a programování se profesionálně věnuje 13 let. Má rád Nirvanu, sushi a svobodu podnikání.
Unicorn university David se informační technologie naučil na Unicorn University - prestižní soukromé vysoké škole IT a ekonomie.
Aktivity

 

 

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
Tvůrce
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
21.3.2014 16:18
One of the most common causes of failure is the habit of quitting when one is overtaken by temporary defeat.
Avatar
Silvinios
Tvůrce
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.5.2019 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.5.2019 8:16
Tento výukový obsah pomáhají rozvíjet následující firmy, které dost možná hledají právě tebe!
Avatar
DarkCoder
Člen
Avatar
Odpovídá na Patrik Pastor
DarkCoder:30.5.2019 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.5.2019 10:00
"Chceš-li předávat své znalosti, měj kvalitní podklady."
Avatar
Odpovídá na DarkCoder
Patrik Pastor:30.5.2019 10:02

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

 
Odpovědět
30.5.2019 10:02
Avatar
DarkCoder
Člen
Avatar
Odpovídá na Patrik Pastor
DarkCoder:30.5.2019 10:09

Třeba QuickSort.

Odpovědět
30.5.2019 10:09
"Chceš-li předávat své znalosti, měj kvalitní podklady."
Avatar
Odpovídá na DarkCoder
Patrik Pastor:30.5.2019 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.5.2019 14:22
Avatar
Odpovídá na Patrik Pastor
Ondřej Michálek:1.6.2019 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
1.6.2019 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