erweiterter euklid-Algorithmus C++

Question

Ich habe ein Problem mit dem erweiterten Algorithmus von Euclid. (ax + by = gcd (a, b)) Ich versuche sowohl die GCD als auch x und y zu bestimmen. Die GCD ist kein Problem, aber mit der Loop-Methode läuft etwas falsch mit x und y. Normalerweise erscheint eine Zahl als 0 und die andere als ungewöhnlich große negative Zahl. Code folgt:

#include <iostream> 

using namespace std; 

main() 
{ 
    int a,b,q,x,lastx,y,lasty,temp,temp1,temp2,temp3; 
    cout << "Please input a" << endl; 
    cin >> a; 
    cout << "Please input b" << endl; 
    cin >> b; 
    if (b>a) {//we switch them 
     temp=a; a=b; b=temp; 
    } 
    //begin function 
    x=0; 
    y=1; 
    lastx=1; 
    lasty=0; 
    while (b!=0) { 
     q= a/b; 
     temp1= a%b; 
     a=b; 
     b=temp1; 

     temp2=x-q*x; 
     x=lastx-q*x; 
     lastx=temp2; 

     temp3=y-q*y; 
     y=lasty-q*y; 
     lasty=temp3; 
    } 

    cout << "gcd" << a << endl; 
    cout << "x=" << lastx << endl; 
    cout << "y=" << lasty << endl; 
    return 0; 
} 

Answer 1

Zwei Ihrer Zuweisungen falsch sind, sollten sie auch sein:

temp2 = x; 
    x=lastx-q*x; 
    lastx = temp2; 

    temp3 = y; 
    y = lasty-q*y; 
    lasty=temp3; 

Beispielausgabe mit den oben genannten Korrekturen:

Please input a 
54 
Please input b 
24 
gcd6 
x=1 
y=-2 

Answer 2

Obwohl die Frage eine lange Zeit gefragt wurde vor, aber die Antwort wird jemandem helfen, der C++ Implementierung des erweiterten euklidischen Algorithmus fand.

Dies ist eine rekursive C++ Implementierung:

int xGCD(int a, int b, int &x, int &y) { 
    if(b == 0) { 
     x = 1; 
     y = 0; 
     return a; 
    } 

    int x1, y1, gcd = xGCD(b, a % b, x1, y1); 
    x = y1; 
    y = x1 - (a/b) * y1; 
    return gcd; 
} 

Beispiel mit Code:

#include <iostream> 

int main() 
{ 
    int a = 99, b = 78, x, y, gcd; 

    if(a < b) std::swap(a, b); 

    gcd = xGCD(a, b, x, y); 
    std::cout << "GCD: " << gcd << ", x = " << x << ", y = " << y << std::endl; 

    return 0; 
} 

Input:

a = 99, b = 78

Ausgang:

GCD: 3, x = -11, y = 14