Vydělávej až 160.000 Kč měsíčně! Akreditované rekvalifikační kurzy s garancí práce od 0 Kč. Více informací.
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í.

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.


 

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 Hartinger
Avatar
Uživatelské hodnocení:
32 hlasů
David je zakladatelem ITnetwork a programování se profesionálně věnuje 15 let. Má rád Nirvanu, nemovitosti 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