12

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

2 に答える 2

13

質問はずっと前に尋ねられましたが、答えは拡張ユークリッドアルゴリズムの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

于 2015-08-27T05:01:06.547 に答える
9

あなたの割り当てのうちの2つは間違っているはずです：

    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
于 2012-10-10T18:47:58.343 に答える