967 afișări Omer Genan (genan) 26.10.2022
www.pbinfo.ro
Etichete: nicio etichetă

În timp ce algoritmul euclidian calculează doar cel mai mare divizor comun (GCD) a două numere întregi și , versiunea extinsă găsește, de asemenea, o modalitate de a reprezenta GCD în termeni de a și b, adică coeficienții x și y pentru care:

ax+by=gcd(a,b)

Este important de reținut că putem găsi întotdeauna o astfel de reprezentare, de exemplu gcd(55,80)=5 prin urmare, putem reprezenta 5 ca o combinație liniară cu termenii 55 și 80: 553+80(2)=5

Algoritmul

În această secțiune vom nota GCD-ul lui a și b cu g.

Modificările aduse algoritmului original sunt foarte simple. Dacă ne amintim algoritmul, putem vedea că acesta se termină cu b=0 și a=g. Pentru acești parametri putem găsi cu ușurință coeficienți, și anume g1+00=g.

Pornind de la acești coeficienți (x,y)=(1,0), putem merge înapoi în sus în apelurile recursive. Tot ce trebuie să facem este să ne dăm seama cum se schimbă coeficienții și în timpul tranziției de la (a,b)), la (b,amodb) .

Să presupunem că am găsit coeficienții (x1,y1) pentru (b,amodb):

bx1+(amodb)y1=g

și dorim să găsim perechea (x,y) pentru (a,b) :

ax+by=g

Putem reprezenta amodb sub forma:

amodb=aabb

Înlocuind această expresie în ecuația coeficientului din (x1,y1) se obține:

g=bx1+(amodb)y1=bx1+(aabb)y1)

și după rearanjarea termenilor:

g=ay1+b(x1y1ab)

Am găsit valorile lui x și y:

{x=y1y=x1y1ab

Implementare

int gcd(int a, int b, int& x, int& y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    int x1, y1;
    int d = gcd(b, a % b, x1, y1);
    x = y1;
    y = x1 - y1 * (a / b);
    return d;
}

Funcția recursivă de mai sus returnează GCD și valorile coeficienților pentru x și y (care sunt transmise prin referință la funcție).

Această implementare a algoritmului euclidian extins produce rezultate corecte și pentru numere întregi negative.


967 afișări Omer Genan (genan) 26.10.2022
www.pbinfo.ro
Du-te sus!