euclid的擴展算法C++

Question

我遇到了Euclid的擴展算法問題。 （ax + by = gcd（a，b））我試圖確定GCD和x和y。 GCD不是問題，但使用循環方法x和y有問題。通常一個數字爲0，另一個數字爲一個異常大的負數。代碼如下：

#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

你的作業中有兩個是錯的，他們應該是：

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

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

輸出上述修正例子：

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

Answer 2

雖然問題已經被問了很久以前，但答案將有助於找到擴展歐幾里得算法的C++實現的人。

這裏是一個遞歸C++實現：

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; 
} 

實施例的代碼：

#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; 
} 

輸入：

A = 99，B = 78

輸出：

GCD：3，X = -11，Y = 14