Page 42 - MATINF Nr. 11-12

42 V. P˘aun

int _cmmdcExtinsR(int a, int b,int &m, int &n) ///a>0,b>=0
{
if(b==0){m=1; n=0; return a;}
int d=_cmmdcExtinsR(b,a % b, n, m);
n=n-(a/b)*m;
return d;
}

Pentru a ˆınt , elege modul de lucru al acestui cod, ne uit˘am mai ˆıntˆai la modul recursiv de obt , inere
al cmmdc(a, b), algoritm inclus s , i ˆın cmmdcExtinsR:
int cmmdc(int a,int b)
{
if(b==0) return a;
return cmmdc(b,a%b);
}

a
Acest algoritm calculeaz˘ continuu restul a%b ˆınlocuind valorile lui a s , i b cu b s , i a%b pˆan˘ cˆand
a
restul devine 0, restul final diferit de 0 fiind cel mai mare divizor comun.
ˆ
In algoritmul extins al lui Euclid, odat˘a g˘asit cel mai mare divizor comun d, trebuie s˘a
determin˘am valorile m s , i n care s˘a respecte relat , ia ma + nb = d.

Observ˘am c˘a aici condit , ia de terminare a algoritmului, este b = 0 s , i a = d (cel mai mare
divizor comun).
a
Construim astfel relat , ia 1 · d + 0 · r = d adic˘ m = 1 s , i n = 0 pentru valorile finale ale lui a
s , i b.

a
Apoi revenim la starea anterioar˘ a algoritmului, s , tiind c˘ cmmdc(a, b) = d este determinat.
a
Acum dup˘a apelul d = cmmdcExtinsR(b,a % b, n, m), avem o solut , ie de forma n 1 b +
m 1 (a%b) = d.
Pentru ment , inerea relat , iei m · a + n · b = d, unde a s , i b sunt valori intermediare s , i d este
valoare final˘a, vom actualiza variabilele m s , i n cu valorile care rezult˘a din urm˘atoarele relat , ii:

a%b = a − [a/b] · b

⇒ n 1 · b + m 1 · (a − [a/b] · b) = d
⇒ m 1 · a + (n 1 − [a/b] · m 1 ) · b = d,

a
de unde rezult˘ valorile actualizate: m = m 1 , n = n 1 − [a/b] · m 1 ).
a
Ne ˆıntoarcem continuu la starea anterioar˘ prin recursivitate, pˆan˘ cˆand ajungem ˆın starea
a
a
init , ial˘ s , i astfel obt , inem solut , ia ma + nb = d.
Funct , ia C++ ce implementeaz˘ acest algoritm este:
a
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;}