Faktoriál

Algoritmy Matematické 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.

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

 

  Aktivity (1)

Článek pro vás napsal David Čápka
Avatar
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 se informační technologie naučil na Unicorn College - prestižní soukromé vysoké škole IT a ekonomie.

Jak se ti líbí článek?
Celkem (6 hlasů) :
3.833333.833333.833333.83333 3.83333


 


Miniatura
Všechny články v sekci
Matematické algoritmy

 

 

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

Avatar
jan.vencl
Redaktor
Avatar
jan.vencl:

Hele dělám to jen co se týče zábavy, zatím testuju u sebe nikde na netu to neni, já nemám moc velké zkušenosti a uvědomuju si že tam je spoustu chyb,ted se chystám to udělat nějak lepší ale nevím jestli v C nebo zvolit Javu ale Javu skoro vůbec neumim spíš se jí chci naučit tak na tom bych to zkusil, s programování dělám asi 9 měsíců :D ale ty matematické úlohy mě baví.
Chci tam ještě přidat možnost definovat vlastní proměné a řešení rovnic

 
Odpovědět 25.9.2012 8:59
Avatar
David Čápka
Tým ITnetwork
Avatar
Odpovídá na jan.vencl
David Čápka:

Ono to nebude těžké opravit, stačí si stáhnout nové PHP a zapnout warningy. Hlavně tam bylo používání funkcí eregi, ty už se nepoužívají, nahradily je preg, měly by se ale volat stejně, jen jiný název :)

Odpovědět 25.9.2012 9:35
Miluji svou práci a zdejší komunitu, baví mě se rozvíjet, děkuji každému členovi za to, že zde působí.
Avatar
jan.vencl
Redaktor
Avatar
Odpovídá na David Čápka
jan.vencl:

Děkuji moc za rady, warningy zapnu v PHP.ini? a tvůj názor sdraco je to lepší dělat v C a volat tu aplikaci pak pomocí exec() aby to slo na webu nebo to mit komplet v PHP ?

 
Odpovědět 25.9.2012 9:56
Avatar
Kit
Redaktor
Avatar
Odpovídá na jan.vencl
Kit:

Dynamicky to nastavíš
http://php.net/…eporting.php

Jinak se to dá napevno nastavit v php.ini direktivou error_reporting. Při spouštění přes CLI tam mám hlášení všech chyb (dobré na ladění a testy), přes Apache to mám nastaveno na standard. Na produkčním serveru se to redukuje, aby to neobtěžovalo klienty.

Odpovědět 25.9.2012 14:05
Vlastnosti objektů by neměly být veřejné. A to ani prostřednictvím getterů/setterů.
Avatar
David Čápka
Tým ITnetwork
Avatar
Odpovídá na Kit
David Čápka:

Hlavně se to redukuje z důvodu bezpečnosti, nikdo nemusí znát strukturu naší aplikace :)

Odpovědět 25.9.2012 14:07
Miluji svou práci a zdejší komunitu, baví mě se rozvíjet, děkuji každému členovi za to, že zde působí.
Avatar
Kit
Redaktor
Avatar
Odpovídá na David Čápka
Kit:

Je fakt, že vhodnou modifikací HTTP požadavku se dá o aplikaci zjistit dost údajů, pokud si to admin neošetří. Nejlepší je všechny warningy, errory i fatal errory zachytit a zalogovat tak, aby se klientovi nic takového nevypisovalo.

Odpovědět 25.9.2012 14:11
Vlastnosti objektů by neměly být veřejné. A to ani prostřednictvím getterů/setterů.
Avatar
Hynek
Člen
Avatar
Hynek:

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:

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:

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
Miluji svou práci a zdejší komunitu, baví mě se rozvíjet, děkuji každému členovi za to, že zde působí.
Avatar
Silvinios
Redaktor
Avatar
Odpovídá na David Čápka
Silvinios:

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
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 15. Zobrazit vše