Page 41 - MATINF Nr. 11-12

Algoritmul extins al lui Euclid 41

(m − m 1 )a + (n − n 1 )b = a − b.

Dac˘a a s , i b sunt numere naturale strict pozitive, putem ˆıntrerupe procesul de reducere prin
sc˘adere aplicat ˆıntre relat , iile (5) s , i (6) ˆın momentul atingerii egalit˘at , ii ˆıntre a si b.
Metoda prezentat˘ mai sus, de obt , inere a coeficient , ilor m s , i n, reprezint˘ s , i o demonstrat , ie
a
a
(constructiv˘a) a urm˘atoarei teoreme:
a
a
a
Teorema 1. Fie a s , i b dou˘ numere ˆıntregi s , i d c.m.m.d.c. al lor. Atunci exist˘ dou˘ numere
ˆıntregi, m s , i n, astfel ˆıncˆat d = ma + nb.
Funct , ia C++ ce implementeaz˘ acest algoritm este:
a
int _cmmdcExtins(int a,int b,int &m, int &n) ///a>0,b>0
{ int m1=0,n1=1;
m=1,n=0;
while(a!=b)
{ if(a>b) { m-=m1; n-=n1; a-=b; }
else { m1 -=m; n1 -=n; b-=a; }
}
return a;
}

a
Putem optimiza algoritmul astfel: dac˘ a = bq + r, 0 ≤ r < b sc˘adem din relat , ia (5) relat , ia (6)
a
multiplicat˘ cu q. Obt , inem urm˘atoarea implementare:
int _cmmdcExtins(int a,int b,int &m, int &n) /// a>0, b>=0
{ m=1; n=0;
int m1=0,n1=1,u,v,q,r;
while(b!=0)
{ q=a/b, r=a%b;
u=m-q*m1; v=n-q*n1;
m=m1; n=n1; a=b;
m1=u; n1=v; b=r;
}
return a;
}

Pentru a obt , ine coeficient , ii m si n pentru numere a, b ˆıntregi oarecare, apel˘am adecvat funct , ia
cmmdcExtins fiec˘arei situat , ii:
int cmmdcExtins(int a,int b, int &m, int &n)
{
int d;
if(b==0) { m=1; n=0; return a;}
if(a==0){m=0,n=1; return b;}
if(a>0 && b>0) return _cmmdcExtins (a,b,m,n);
if(a<0 && b <0){d= _cmmdcExtins(-a,-b,m,n); m=-m;n=-n; return d;}
if(a <0){d=_cmmdcExtins(-a,b,m,n); m=-m; return d;}
if(b <0){d=_cmmdcExtins(a,-b,m,n); n=-n; return d;}
}

Varianta recursiv˘ a algoritmului extins al lui Euclid este urm˘atoarea:
a