Algoritmul lui EUCLID

WEBER KINGA

INFORMATICA ANUL I. - GRUPA II. SUBGRUPA III. - 2015-16

LABORATOR ALGORITMI SI STRUCTURI DE DATE

Prima descriere rămasă a algoritmului lui Euclid este lucrarea lui Euclid intitulată Elementele (c. 300 î.e.n.), fiind unul dintre cei mai vechi algoritmi numerici încă utilizați. Algoritmul original a fost descris doar pentru numere naturale și lungimi geometrice (numere reale), dar algoritmul a fost generalizat în secolul al XIX-lea și la alte tipuri de numere

În matematică, algoritmul lui Euclid este o metodă eficientă de calcul al

celui mai mare divizor comun. Algoritmul lui Euclid calculează cel

mai mare divizor comun (CMMDC) al două numere naturale m și n.

Cel mai mare divizor comun este cel mai mare număr natural

care îi divide pe m și pe n. Cel mai mare divizor comune este adesea se

noteaza ca CMMDC

Metoda de calcul

Algoritmul lui Euclid• pentru două numere m şi n

atribuie lui n restul împărţirii lui m la n, iar lui m vechea valoare a lui n.

• Rezolvarea problemei se bazează pe condiţia n≠0. Se repetă procesul de împărţire  până când  r=0.

Pasii algoritmului

• Animaţia prezintă algoritmul lui Euclid pentru numerele 252 şi 105.

• Barele reprezintă unităţile de 21, cel mai mare divizor comun (CMMDC).

• La fiecare pas, numărul mai mic este scăzut din cel mai mare, până când unul dintre numere ajunge să fie zero. Celălalt este CMMDC.

ALGORITMUL IN PHP public function getEuclid($n, $m) { if ($this->isNLessThanM($n, $m)) { echo "n trebuie sa fie mai mic decat m"; die(); } $d = $n; $i = $m; do { $r = $d - $d % $i * $i; $d = $i; $i = $r; } while ($r = 0); echo "d este: " . $d; }