A | B | C | D | E | F | G | H | CH | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
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:
- Ak v = 0, vráť na výstup hodnotu u, inak pokračuj krokom 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
- Euklidov algoritmus - Wolfram MathWorld (po anglicky).
- Euklidov algoritmus - cut-the-knot (po anglicky).
- Euklidov algoritmus
Pozri aj
Text je dostupný za podmienok Creative Commons Attribution/Share-Alike License 3.0 Unported; prípadne za ďalších podmienok. Podrobnejšie informácie nájdete na stránke Podmienky použitia.
Antropológia
Aplikované vedy
Bibliometria
Dejiny vedy
Encyklopédie
Filozofia vedy
Forenzné vedy
Humanitné vedy
Knižničná veda
Kryogenika
Kryptológia
Kulturológia
Literárna veda
Medzidisciplinárne oblasti
Metódy kvantitatívnej analýzy
Metavedy
Metodika
Text je dostupný za podmienok Creative
Commons Attribution/Share-Alike License 3.0 Unported; prípadne za ďalších
podmienok.
Podrobnejšie informácie nájdete na stránke Podmienky
použitia.
www.astronomia.sk | www.biologia.sk | www.botanika.sk | www.dejiny.sk | www.economy.sk | www.elektrotechnika.sk | www.estetika.sk | www.farmakologia.sk | www.filozofia.sk | Fyzika | www.futurologia.sk | www.genetika.sk | www.chemia.sk | www.lingvistika.sk | www.politologia.sk | www.psychologia.sk | www.sexuologia.sk | www.sociologia.sk | www.veda.sk I www.zoologia.sk