Algoritmul lui Euclid este o metodă de a găsi cel mai mare divizor comun (CMMDC) a două numere întregi pozitive.
Algoritmul lui Euclid formula de calcul:
Pentru două numere întregi pozitive a și b, cu a ≥ b, algoritmul lui Euclid este următorul:
Impărțim a la b și notăm restul cu r.
Dacă r = 0, atunci b este cel mai mare divizor comun al numerelor a și b și algoritmul se încheie.
Dacă r ≠ 0, atunci setăm a = b și b = r și revenim la pasul 1.
Acest proces este repetat până când restul devine 0, caz în care b devine cel mai mare divizor comun al numerelor a și b.
Algoritmul lui Euclid Exemplul 1
Să luăm numerele a = 24 și b = 18.
Împărțim 24 la 18 și obținem restul 6. Deci r = 6.
Deoarece r ≠ 0, setăm a = 18 și b = 6 și revenim la pasul 1.
Împărțim 18 la 6 și obținem restul 0.
Deci, b = 6 este cel mai mare divizor comun al numerelor 24 și 18.
Așadar, CMMDC al numerelor 24 și 18 este 6.
Algoritmul lui Euclid Exemplul 2
Să presupunem că dorim să găsim cel mai mare divizor comun între 24 și 16 folosind algoritmul lui Euclid. Prima dată, calculăm restul r prin impartirea lui 24 la 16, rezultand restul 8.
Aplicăm acum algoritmul lui Euclid pentru 16 și 8.
Din nou, calculăm r = 16 impartit la 8 si rezulta r = 0.
Deoarece restul este 0, algoritmul se oprește, iar cel mai mare divizor comun este ultimul număr diferit de 0, adică 8.
Astfel, CMMDC(24,16) = 8.
Niciun comentariu:
Trimiteți un comentariu