Question

Care este algoritmul lui Euclid?Am nevoie de datele de intrare,cele de iesire si pasii de rezolvare ale acestuia.

Answer 1

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 $r_{k-1}$ și [tex] r_{k-2} [/tex] . Cu pasul k afli catul($q_{k}$) si restul([tex]r_{q} [/tex]) a.i :
$r _{k-2}$ = $q_{k}xr_{k-1}+r_{q}$

Answer 2

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.