Obsah
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“.
- Je-li n > m, čísla navzájem prohodíme (tj. zajistíme, že n je menší z čísel).
- 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ů:
- Vypočteme r jako zbytek po celočíselném dělení m / n.
- Číslu m přiřadíme hodnotu n.
- Číslu n přiřadíme hodnotu r a vracíme se do bodu 2.
- 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 = m1 – q.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 | 220 | 7480 = 5.1452 + 220 |
| 2 | 1452 | 220 | 132 | 1452 = 6.220 + 132 |
| 3 | 220 | 132 | 88 | 220 = 1.132 + 88 |
| 4 | 132 | 88 | 44 | 132 = 1.88 + 44 |
| 5 | 88 | 44 | 0 | 88 = 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.
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).