Eukleidův algoritmus: Porovnání verzí
Smazaný obsah Přidaný obsah
google.com značka: editace z Vizuálního editoru |
m Editace uživatele 188.175.191.210 (diskuse) vráceny do předchozího stavu, jehož autorem je 84.19.71.113 |
||
Řádek 1:
'''Eukleidův algoritmus''' (též '''Euklidův''') je [[algoritmus]], kterým lze určit [[Největší společný dělitel|největšího společného dělitele]] dvou [[Přirozené číslo|přirozených čísel]], tedy největší číslo takové, že beze zbytku dělí obě čísla. Jedná se o jeden z nejstarších známých netriviálních algoritmů a postupně vznikla řada jeho modifikací například pro příbuzné úlohy. Z nich nejdůležitější je [[rozšířený Eukleidův algoritmus]], kterým lze nalézt [[Bézoutova rovnost|Bézoutovu rovnost]], neboli vyjádření největšího společného dělitele dvou čísel jejich lineární kombinací.
m díle [[Eukleidovy Základy|''Základy'']] (cca 300 př.n.l.), přestože tento postup zřejmě sám nevynalezl. Jedná se pravděpodobně o nejstarší lidstvu známý netriviální algoritmus, takže po jistou dobu se slovem algoritmus prakticky rozuměl Eukleidův algoritmus.▼
Algoritmus lze také použít i v jiných [[algebraická struktura|algebraických strukturách]], než jsou přirozená čísla. Takové struktury se nazývají [[Eukleidovský obor|Eukleidovské obory]] a jedná se například o některé [[okruh mnohočlenů|okruhy mnohočlenů]] nebo o [[Eisensteinovo číslo|Eisensteinova čísla]].
== Algoritmus ==
Mějme dána dvě přirozená čísla, uložená v proměnných ''u'' a ''w''.
Dokud ''w'' není nulové, opakuj:
Do ''r'' ulož [[zbytek po dělení]] čísla ''u'' číslem ''w''
Do ''u'' ulož ''w''
Do ''w'' ulož ''r''
Konec algoritmu, v ''u'' je uložen největší společný dělitel původních čísel.
== Popis činnosti ==
Opakovaně prováděné operace nemění hodnotu největšího společného dělitele (neboť NSD(''u'',''v'')=NSD(''v'',''u''-''qv'') pro libovolné celé číslo ''q''), ale v každém kroku se hodnota proměnné ''v'' sníží, takže je zřejmé, že v konečném počtu kroků se algoritmus ukončí s tím, že ''v'' je nulové. Tehdy obsahuje proměnná ''u'' největší společný dělitel, neboť NSD(''u'',0)=''u'', což musí být současně největší společný dělitel původních čísel, neboť, jak už bylo uvedeno, hlavní smyčka programu hodnotu největšího společného dělitele nemění.
== Vlastnosti algoritmu ==
Doba provádění programu je závislá na počtu průchodů hlavní smyčkou. Ten je maximální tehdy, jsou-li počáteční hodnoty ''u'' a ''v'' rovné dvěma po sobě jdoucím členům [[Fibonacciho posloupnost]]i. Maximální počet provedených opakování je tedy <math>\log_\phi (3-\phi)v \approx 4{,}785 \log v + 0{,}6273 = O(\log v)</math>. Průměrný počet kroků pak je o něco nižší, přibližně <math>\frac{12 \ln 2}{\pi^2}\log v \approx 1{,}9405 \log v = O(\log v)</math>.
== Ukázka činnosti algoritmu ==
Mějme čísla ''u''=40902, ''v''=24140. Výpočet probíhá následujícím způsobem:
{| class="wikitable"
! ''u''
! ''v''
! ''u''=''v.q''+''r''
|- align="right"
| 40902
| 24140
| 40902=24140×1+16762
|- align="right"
| 24140
| 16762
| 24140=16762×1+7378
|- align="right"
| 16762
| 7378
| 16762=7378×2+2006
|- align="right"
| 7378
| 2006
| 7378=2006×3+1360
|- align="right"
| 2006
| 1360
| 2006=1360×1+646
|- align="right"
| 1360
| 646
| 1360=646×2+68
|- align="right"
| 646
| 68
| 646=68×9+34
|- align="right"
| 68
| 34
| 68=34×2+0
|- align="right"
| 34
| 0
| ''konec algoritmu''
|}
Největším společným dělitelem čísel 40902 a 24140 je číslo 34.
== Historie ==
▲
== Poznámky ==
| |||