Zpět na seznam článků     Číst komentáře (8)     Verze pro tisk

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

Autor: sukovanej   
27.1.2013

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.

  1. long n = 0;
  2. string result = null;
  3.  
  4. Console.Write("Zadejte číslo : ");
  5. n = Convert.ToInt64(Console.ReadLine());
  6.  
  7. while (n != 1)
  8.     {
  9.        int x = 0;
  10.        for (int i = 2; i <= n; i++)
  11.        {
  12.            if ((n % i) == 0)
  13.            {
  14.               x = i;
  15.               break;
  16.            }
  17.        }
  18.  
  19.        result += x.ToString() + " * ";
  20.  
  21.        n = n / x;
  22. }
  23.  
  24. Console.Write("Rozklad na součin : " + result + " 1");
  25. 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.

  1. double n = 0;
  2. double result = 1;
  3.  
  4. Console.Write("Zadejte číslo : ");
  5. n = Convert.ToDouble(Console.ReadLine());
  6.  
  7. for (ulong i = 1; i <= n; i++)
  8. {
  9.     result *= i;
  10. }
  11.  
  12. Console.Write(result.ToString());
  13. 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.


Líbil se Vám článek?
Budeme potěšeni, pokud vás zaujme také reklamní nabídka

Social Bookmarking

     





Hodnocení/Hlasovalo: 2.71/14

1  2  3  4  5    
(známkování jako ve škole)