Algoritmi: Algoritmul lui Euclid (CMMDC)

Algoritmul lui Euclid reprezint o metod eficient de calculare a celui mai mare divizor comun (CMMDC) adou numere ntregi. Algoritmul bazat pe mprire (implementat n C++):int cmmdc(int a, int b){ int t; while (b != 0) { t = b; b = a % b; a = t; } return a;}Funcia de mai sus returneaz CMMDC al numerelor a i b. Exist i versiunea bazat pe scderi 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;}Bineneles c poate fi implementat i recursiv:int cmmdc(int a, int b)

@In

foshow

-Desi

gn

{ if(b == 0) return a; else return cmmdc(b, a % b);}Pentru a calcula cel mai mic multiplu comun, nmulii numerele a i b, i mprii prin cmmdc. Exemplu:12 * 6 / cmmdc(12, 6);Algoritmul lui Euclid extins

Algoritmul lui Euclid extins gsete, pe lng cmmmd al numerelor a i b, ntregii x i y care satisfacidentitatea lui Bzout:

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; }

@In

foshow

-Desi

gn

return a;}Algoritmul returneaz cmmdc(a, b), iar prin referinele lastX i lastY returneaz cei doi ntregi x i y.Exemplu:int main(){ int x, y;

cout