Euklidov algoritmus: Rozdiel medzi revíziami

z Wikipédie, slobodnej encyklopédie
Smazaný obsah Přidaný obsah
Rubinbot (diskusia | príspevky)
d r2.7.3) (robot Pridal: he:מחלק משותף מקסימלי
Addbot (diskusia | príspevky)
d Bot: Odstránenie 39 odkazov interwiki, ktoré sú teraz dostupné na Wikiúdajoch (d:q230848)
Riadok 51: Riadok 51:
{{Link FA|en}}
{{Link FA|en}}


[[ar:خوارزمية أقليدس]]
[[bg:Алгоритъм на Евклид]]
[[bn:ইউক্লিডীয় এলগরিদম]]
[[ca:Algorisme d'Euclides]]
[[cs:Eukleidův algoritmus]]
[[de:Euklidischer Algorithmus]]
[[el:Αλγόριθμος του Ευκλείδη]]
[[en:Euclidean algorithm]]
[[eo:Eŭklida algoritmo]]
[[es:Algoritmo de Euclides]]
[[fa:الگوریتم اقلیدس]]
[[fi:Eukleideen algoritmi]]
[[fr:Algorithme d'Euclide]]
[[he:מחלק משותף מקסימלי]]
[[he:מחלק משותף מקסימלי]]
[[hu:Euklideszi algoritmus]]
[[id:Algoritma Euklidean]]
[[it:Algoritmo di Euclide]]
[[ja:ユークリッドの互除法]]
[[ko:유클리드 호제법]]
[[lt:Euklido algoritmas]]
[[lv:Eiklīda algoritms]]
[[ml:യൂക്ലിഡിന്റെ അൽഗൊരിതം]]
[[mn:Евклидийн алгоритм]]
[[nds:Euklidsch Algorithmus]]
[[nl:Algoritme van Euclides]]
[[nn:Euklidsk algoritme]]
[[no:Euklids algoritme]]
[[pl:Algorytm Euklidesa]]
[[pms:Algoritm d'Euclid]]
[[pt:Algoritmo de Euclides]]
[[ro:Algoritmul lui Euclid]]
[[ru:Алгоритм Евклида]]
[[simple:Euclidean algorithm]]
[[sl:Evklidov algoritem]]
[[sr:Еуклидов алгоритам]]
[[sv:Euklides algoritm]]
[[tr:Öklid algoritması]]
[[uk:Алгоритм Евкліда]]
[[vi:Giải thuật Euclid]]
[[zh:輾轉相除法]]

Verzia z 19:14, 20. marec 2013

Euklidov algoritmus je v teórii čísel algoritmus na určenie najväčšieho spoločného deliteľa dvoch prirodzených čísel. Je pomenovaný podľa starogréckeho matematika Euklida, ktorý ho opísal v siedmej a desiatej knihe svojich Základov.

Algoritmus

Euklidov algoritmus využíva nasledujúcu skutočnosť: ak a je najväčším spoločným deliteľom (označovaný aj NSD(u,v) alebo GCD(u,v)) čísel u,v, potom je aj najväčším spoločným deliteľom čísel v,u-qv pre ľubovoľné q. Tvrdenie možno dokázať nasledujúcim spôsobom. Keďže je a najväčší spoločný deliteľ čísel u,v, musí platiť a , kde a je najväčšie takéto číslo. Potom zrejme

čo znamená, že a je spoločným deliteľom čísel v,u-qv pre ľubovoľné q. Zostáva dokázať, že žiadny väčší spoločný deliteľ neexistuje. Sporom. Nech b > a je spoločný deliteľ v,u-qv. Potom platí v = kb a u-qv = lb. Z toho ale

čo znamená že b je spoločným deliteľom u,v, a keďže b > a, nemôže byť a najväčším spoločným deliteľom u,v, čo je spor s predpokladom.

Špeciálnym prípadom práve dokázaného tvrdenia je tvrdenie: ak a je najväčším spoločným deliteľom u,v, kde , potom je aj najväčším spoločným deliteľom čísel v a .

Euklidov algoritmus možno opísať nasledovne:

Vstup: prirodzené čísla u, v, .

Výstup: Najväčší spoločný deliteľ čísel u,v.

Procedúra:

  1. Ak v = 0, vráť na výstup hodnotu u, inak pokračuj krokom 2.
  2. Zavolaj procedúru Euklidovho algoritmu pre vstup .

Podľa dokázaného tvrdenia nevráti Euklidov algoritmus nikdy zlú hodnotu. Navyše, pri každom rekurzívnom volaní sa zmenší hodnota aspoň jedného vstupu, pričom obe zotrvávajú nezáporné. To znamená, že Euklidov algoritmus sa na každom vstupe zastaví, pričom jeho výstupom je naozaj najväčší spoločný deliteľ čísel u,v.

Pseudokód

Pseudokód pre rekurzívnu implementáciu Euklidovho algoritmu môže byť nasledovný:

function gcd(u, v)
    if v = 0
       return u
    else
       return gcd(v, u mod v).

Pre iteratívnu verziu možno napísať nasledujúci pseudokód

function gcd(u, v)
    while v ≠ 0
       t := v
       v := u mod v
       u := t
    return u.

Externé odkazy

Šablóna:Link FA