Algoritmul Lui Euclid (cmmdc) 102m1w

Algoritmi: Algoritmul lui Euclid (CMMDC)

@

In

fos

ho w-

D

esi gn

Algoritmul lui Euclid reprezintă o metodă eficientă de calculare a celui mai mare divizor comun (CMMDC) a două numere întregi. Algoritmul bazat pe împărţire (implementat în C++): int cmmdc(int a, int b) { int t; while (b != 0) { t = b; b = a % b; a = t; } return a; } Funcţia de mai sus returnează CMMDC al numerelor a şi b. Există şi versiunea bazată pe scăderi repetate: int cmmdc(int a, int b) { if(a == 0) return b; while(b != 0) { if(a > b) a -= b; else b -= a; } return a; } Bineînţeles că poate fi implementat şi recursiv: int cmmdc(int a, int b)

if(b == 0) return a; else return cmmdc(b, a % b);

esi gn

{

} Pentru a calcula cel mai mic multiplu comun, înmulţiţi numerele a şi b, şi împărţiţi prin cmmdc. Exemplu: 12 * 6 / cmmdc(12, 6);

D

Algoritmul lui Euclid extins

ho w-

Algoritmul lui Euclid extins găseşte, pe lângă cmmmd al numerelor a şi b, întregii x şi y care satisfac identitatea lui Bézout:

@

In

fos

Implementarea algoritmului în C++: int euclidExtins(int a, int b, int& lastX, int& lastY) { int x = 0, y = 1, q; lastX = 1; lastY = 0; // variabile temporare int tA, tX, tY; while(b != 0) { q = a / b; // aveti grija ca a > b tA = b; b = a % b; a = tA; tX = x; x = lastX - q * x; lastX = tX; tY = y; y = lastY - q * y; lastY = tY; }

return a;

esi gn

} Algoritmul returnează cmmdc(a, b), iar prin referinţele lastX şi lastY returnează cei doi întregi x şi y. Exemplu: int main() { int x, y;

@

In

fos

}

ho w-

system("PAUSE"); return 0;

D

cout << euclidExtins(27, 6, x, y) << '\n'; // 3 cout << x << ' ' << y; // 1 -4