Výpočet faktoriálu aneb u programování se musí myslet

Trocha teorie pro ty, co se s faktoriálem jeste nesetkali:
Faktoriál čísla x získáme tak, že vynásobíme všechna čísla od jedné do čísla x. Počítá se pouze pro celá kladná čísla a značí se vykřičníkem za číslem.

Funkce by mohla vypadat třeba takto:

function faktorial(cislo) { var f = 1; for (var i = 1; i <= cislo; i++) f = f * i; return (f); }

Naplnění pole faktoriály jeho indexů

Máme za úkol vytvořit funkci, která pro zadané pole vloží jako hodnotu prvků faktoriál indexu (tzn. pro prvek 1 vloží hodnotu 1!, pro prvek 2 hodnotu 2!...atd.). S radostí, že už výpočet faktoriálu máme naprogramovaný vytvoříme tuto funkci:


function naplnPoleFaktorialy(pole)

{

  var velikost = pole.length;

  for (var i = 1; i <= velikost; i++)

    pole[i] = faktorial(i);

}

Vše bude fungovat, ale pro větší pole to bude pomalé.

Jde to nějak zlepšit? Jde. Stačí jednoduchá úvaha. Pokud znám faktoriál čísla x, mohu ho nějak využít k výpočtu faktoriálu čísla x+1? Ano, stačí ho vynásobit číslem x+1. V první funkci předchozí výsledek vždy "zahodíme" a počítame znovu od začátku.

Upravená funkce:


function naplnPoleFaktorialy2(pole)

{

  var velikost = pole.length;

  var f = 1;

  for (var i = 1; i <= velikost; i++)

  {

    f = f * i;

    pole[i] = f;

  }

}

Délka výpočtu se po této optimalizaci výrazně zmenší. První funkce pro naplnění pole o 100 prvcích provede 5050x násobení, druhá pouze 100. Pro pole o 1 000 prvcích musí první funkce provést přes půl milionu násobení!

Zde si můžete vyzkoušet rychlost uvedených funkcí

Počet prvků v poli:
Doba zjišťování:	ms
Počet násobení:

Přidávám tabulku časů (v ms) pro vybraná čísla na počítači s procesorem Pentium 4 2,8GHz. Z výsledků je vidět co způsobí programování bez přemýšlení.

Funkce\velikost pole	100	200	500	1 000	5 000
naplnPoleFaktorialy	0	16	110	485	13 600
naplnPoleFaktorialy2	0	0	0	0	8