Uživatelské nástroje

Nástroje pro tento web


eukl_algo

Eukleidův algoritmus

Největší společný dělitel dvou přirozených čísel se ve středoškolských učebnicích obvykle počítá pomocí rozkladu obou čísel na prvočíselné činitele. Výsledek je pak součinem všech stejných činitelů (případně i vícenásobných) v rozkladech.

Algoritmus

Takový způsob je přímočarý a snadno pochopitelný, ale v praxi použitelný pouze pro malá čísla. Jinak je totiž faktorizace (nalezení prvočíselného rozkladu) poměrně obtížná úloha1). Naštěstí máme efektivní postup, jak největšího společného dělitele nalézt i v takových případech—Eukleidův algoritmus.

Popis

Mějme dvě různá přirozená čísla m a n. Dále budeme postupovat dle následujícího „předpisu“.

  1. Je-li n > m, čísla navzájem prohodíme (tj. zajistíme, že n je menší z čísel).
  2. Pokud je n rovno nule, přecházíme do bodu 3. V opačném případě provádíme následující sadu kroků:
    1. Vypočteme r jako zbytek po celočíselném dělení m / n.
    2. Číslu m přiřadíme hodnotu n.
    3. Číslu n přiřadíme hodnotu r a vracíme se do bodu 2.
  3. Výpočet je dokončen, největší společný dělitel je hodnota v proměnné m.

Proč to funguje

Podstatná činnost se provádí v bodech 2a až 2c popisu. Při vstupu máme dvojici hodnot m1 a n1, po provedení bloku pak dvojici m2 a n2, přičemž platí

m2 = n1
n2 = m1q.n1

pro nějaké přirozené q2). Společný dělitel m1 a n1 musí být i dělitelem n23). Díky tomu mají dvojice {m1, n1} a {m2, n2} stejného největšího společného dělitele. Důležité je, že se čísla zmenšila. Po konečném počtu opakování tedy musí dojít k situaci, kdy n bude nulové a smyčka v bodu 2 se ukončí. V proměnné m je potom hledaný největší společný dělitel.

Příklad

Nejnázornější bude představit algoritmus v činnosti. Mějme kupříkladu čísla m = 7480 a n = 1452. Prohození proměnných v bodu 1 provádět nemusíme a činnost ve smyčce (bod 2) je zachycena v tabulce.

Krok m n r
1 7480 1452 2207480 = 5.1452 + 220
2 1452 220 1321452 = 6.220 + 132
3 220 132 88220 = 1.132 + 88
4 132 88 44132 = 1.88 + 44
5 88 44 088 = 2.44 + 0
6 44 0 smyčka končí

Výsledek ověříme rozložením vstupních hodnot na prvočinitele

7480 = 23.5.11.17 a
1452 = 22.3.112.

Největší společný dělitel je tedy 22.11 = 44. Vidíme, že popsaný algoritmus nalezl správné řešení a i při takto malých číslech je zřejmá jeho efektivita.

Historická poznámka

Algoritmus se obvykle uvádí s přívlastkem Eukleidův, neboť první zmínka o něm pochází z jeho díla Základy (kolem 300 př.n.l.), pravděpodobně však tento řecký filozof a matematik jeho autorem není. Později jej nezávisle objevili i čínští a indičtí učenci.

Jedná se o nejstarší dochovaný algoritmus, tedy logicky uspořádaný sled kroků vedoucí k řešení matematicky formulované úlohy. A jsou to právě algoritmy tohoto typu, kterými krmíme dnešní počítače a očekáváme od nich odpovědi na naše otázky.

Vyzkoušejte si sami

Zadejte do editačních polí dvě čísla. Po potvrzení tlačítkem bude níže uveden postup nalezení největšího společného dělitele pomocí Eukleidova algoritmu.
 
Průběh Eukleidova algoritmu
Dosud nebyla zadána dvě čísla pro výpočet.

Geometrická interpretace

Úloha nalezení největšího společného dělitele dvou čísel a její řešení pomocí Eukleidova algoritmu má i přímočaré geometrické znázornění. Odpovídá úkolu vydláždit obdélníkovou místnost beze zbytku co největšími čtvercovými dlaždicemi. Rozměry místnosti jsou přitom právě zadaná čísla, hledáme délku hrany dlaždice.

Uvažujme místnost o rozměrech 186 a 84 délkových jednotek. Jednotlivé kroky algoritmu zachycuje animace4).

(viz výše) s výsledkem animace. Hledané dlaždice budou mít hranu 6 délkových jednotek.

Literatura

  • Umění programování, díl 2. Seminumerické algoritmy, D. E. Knuth, Computer press (2010)
1)
Pro velká čísla je to i pro současné superpočítače úloha prakticky neřešitelná, což je základem jedné z velmi rozšířeným šifrovacích metod RSA.
2)
q je výsledkem celočíselného dělení m1/n1, tudíž n2 je zbytkem po tomto dělení.
3)
Dělitel nějakých čísel je také dělitelem jejich součtu, rozdílu i celočíselného násobku.
4)
Z obdélníka můžeme odebírat čtverce o straně menšího rozměru výchozího obrazce. Pokud totiž hledané dlaždice dokáží pokrýt zbylý obdélník, pokryjí úplně i odebrané čtverce. Jejich strany jsou totiž shodné s delší stranou zůstatku. Takové kroky opakujeme do úplného vyčerpání (tedy nikoliv fyzického či duševního, ale místa).
eukl_algo.txt · Poslední úprava: 25.07.2017 07:10 autor: Ivana Stefanová

Donate Powered by PHP Valid HTML5 Valid CSS Driven by DokuWiki