Algoritmul lui Euclid e o metoda prin care se afla cel mai mic multiplu comun . Pasii
se noteaza cu k (Primul pas e k=0 , al doilea e k=1 etc.).Fiecare pas
începe cu două resturi nenegative [tex] r_{k-1} [/tex] și [tex] r_{k-2}
[/tex] . Cu pasul k afli catul([tex] q_{k} [/tex]) si restul([tex]r_{q}
[/tex]) a.i : [tex]r _{k-2} [/tex] = [tex] q_{k}xr_{k-1}+r_{q}[/tex]
Algoritmul lui Euclid reprezintă o metodă eficientă de calculare a celui mai mare divizor comun De exemplu, 21 este CMMDC al numerelor 252 și 105 (252 = 21 × 12;
105 = 21 × 5); întrucât 252 − 105 = 147, CMMDC al lui 147 și 105 este
tot 21.
Vă mulțumim pentru vizita pe platforma noastră dedicată Informatică. Sperăm că informațiile prezentate v-au fost utile. Dacă aveți întrebări sau aveți nevoie de suport suplimentar, nu ezitați să ne contactați. Așteptăm cu entuziasm să reveniți și vă invităm să ne adăugați la lista de favorite!
