C# tipy #5 - Algoritmizace (faktoriál, rozklad na prvočísla)

Zdroj: SOOM.cz [ISSN 1804-7270]
Autor: sukovanej
Datum: 27.1.2013
Hodnocení/Hlasovalo: 2.89/18

V tomto článku si ukážeme, jak lze programově zpracovat výpočet faktoriálu a rozkladu na součin.

Rozklad na prvočísla

Rozklad prvočísel je velice časově náročný proces. Jeho algoritmus bude vypadat následujícím způsobem.

Od uživatele získáme číslo (celé číslo samozřejmě). Budeme procházet cyklem, v němž vyzkoušíme dělitelnost všech celých čísel v rozmezí 2 až n. Pokaždé, když nějaké číslo, které beze zbytku naše n dělí, nalezneme, vyskočíme z cyklu a získaného dělitele si uchováme. Proměnná n bude nejdříve rovna hodnotě čísla získaného od uživatele, ale v dalších iteracích ji budeme zmenšovat takovým způsobem, že ji pokaždé vydělíme číslem získaným v cyklu. A tento proces budeme opakovat, dokud se n nebude rovnat jedničce.

long n = 0;
string result = null;

Console.Write("Zadejte číslo : ");
n = Convert.ToInt64(Console.ReadLine());

while (n != 1)
    {
       int x = 0;
       for (int i = 2; i <= n; i++)
       {
           if ((n % i) == 0)
           {
              x = i;
              break;
           }
       }

       result += x.ToString() + " * ";

       n = n / x;
}

Console.Write("Rozklad na součin : " + result + " 1");
Console.ReadKey();

Rozklad prvočísel (jak určitě zjistíte) je pro komplikovanější čísla (ve smyslu, že mají velmi velké prvočíselné rozklady) časově hodně náročný. Toho se využívá např. při šifrování. V budoucnu, pokud se podaří vývoj tzv. kvantových počítačů, by se tento proces mohl velmi zrychlit. Bohužel, byla by to zároveň zbraň na kreditní karty, které této vlastnosti prvočísel využívají. Útočník by s kvantovým počítačem získal heslo mnohem snadněji.

Faktoriál

Faktoriál se nejčastěji objevuje v kombinatorice. Je definovaný pouze pro celá čísla a je to jedna z nejrychleji rostoucích funkcí. Kalkulačky ho obvykle dokážou spočítat pro hodnoty kolem čísla 70. Na mém počítači jsem ho spočítal pro hodnotu 250 a výše mi vypisovat „nekonečno“.

Algoritmus nebude příliš složitý. Nejdříve získáme číslo od uživatele. Potom budeme procházet cyklem od hodnoty 1 do hodnoty n (to je naše hodnota od uživatele) a při každém průchodu cyklem vynásobíme nějakou proměnnou, kterou si předem definujeme a určíme jí hodnotu 1, samo sebou a aktuálním číslem v cyklu.

double n = 0;
double result = 1;

Console.Write("Zadejte číslo : ");
n = Convert.ToDouble(Console.ReadLine());

for (ulong i = 1; i <= n; i++)
{
    result *= i;
}

Console.Write(result.ToString());
Console.ReadKey();

Může se zdát divné, že proměnnou s počáteční hodnotou máme definovanou jako double. Tento typ má totiž obrovský rozsah (asi 300 řádů) a proto je pro faktoriál ideální.

Závěr

Předpokládám, že tento díl nenajde zalíbení u všech. U algoritmizace doporučuji vše vypsat do vývojových diagramů a potom postupně sepsat jako kód. Příklady jsou pravda velice primitivní, ale není ke škodě ji je vyzkoušet.