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);
}
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);
Algoritmul lui Euclid extins
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:
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;
}
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;
cout << euclidExtins(27, 6, x, y) << '\n'; // 3
cout << x << ' ' << y; // 1 -4
system("PAUSE");
return 0;
}
Explicaţia o găsiţi aici:
http://en.wikipedia.org/wiki/Extended_Euclidean_algorithm sau luaţi pixul şi hârtia şi executaţi algoritmul pas cu pas (recomand să faceţi asta, veţi înţelege mai bine).
Niciun comentariu:
Trimiteți un comentariu
Rețineți: Numai membrii acestui blog pot posta comentarii.