c++ - 实现欧几里德除法，根据这些整数的线性组合写出两个正整数的最大公约数

Question

我正在尝试编写一个程序，可以根据这些整数写出两个正整数的最大公约数。例如，假设我有数字 353 和 15，我将使用以下步骤找到 gcd:

353 = 23*15 + 8

15 = 1*8 + 7

8 = 1*7 + 1

7 = 7*1

所以 gcd 是 1。我将其实现为:

//div_algo always takes int1 >= int2
int div_algo(int int1, int int2)
{   
    if (int2 == 0) //we are done
        return int1;
    int factor = 0;
    int remainder = 0;
    factor = int1/int2; //this is useful for linear combination
    remainder = int1 % int2;
    return div_algo(int2, remainder);
}

问题是，如果我想找到线性组合，我基本上是向后工作。所以，继续我的例子:

1 = 1*8 - 1*7(代入 7 = 15 - 1*8)

1 = 1*8 - 1*15 + 1*8 = 2*8 - 1*15(代入 8 = 353 - 23*15)

1 = 2*353 - 46*15 - 1*15 = 2*353 - 47*15

我们开始吧。我遇到的问题是我不知道如何“存储”以前的方程式以便我可以替代。

Answer 1

添加另一个参数来存储您正在寻找的因素。你可以这样实现它:

int div_algo(int int1, int int2, vector<int>& factors)
{   
    if (int2 == 0) //we are done
        return int1;
    int factor = 0;
    int remainder = 0;
    factors.push_back(int1/int2); //this is useful for linear combination
    remainder = int1 % int2;
    return div_algo(int2, remainder, factors);
}

请注意使用 & 作为因子。您不想复制数组，而只是发送对同一原始数组的引用。您可以将 vector 中的 int 替换为可以保留您认为必要的任何数据的结构。

要调用它你可以这样做:

vector<int> factors;
div_algo(353, 15, factors);
for (int x : factors) cout << x << " ";