欧几里得算法函数参数

Question

我已经为类编写了一个程序，我需要递归地计算a和b的扩展欧几里得算法，返回最大公约数G，以及as+bt=gcd（a，b）的s和t。 我相当确定我正确编写了函数，但是我在函数之间传递值时遇到了问题。 我有一段时间没有编码了，最近才写伪代码，所以我有点生疏。

例如，我写了当 b=0，返回 （a， 1， 0） 时，但是当我输入 b 作为 0 时，我得到返回 （0， 0， 0） 并且无法弄清楚为什么会发生这种情况。 任何帮助或指导将不胜感激。

#include <iostream>
using namespace std;
int ExtGCD (int a, int b)
{
    int g, s, t, g1, s1, t1;
    if (b == 0) {
        return (a, 1, 0);
    }
    (g1, s1, t1) = ExtGCD(b, a%b);
    g = g1;
    s = s1;
    t = s1 - ((a/b)*t1);
    return (g, s, t);
}
int main(int argc, char* argv[])
{
    int a,b, g2, s2, t2, temp;
    cout << "Please input a: ";
    cin >> a;
    cout << "Please input b: ";
    cin >> b;
    if (b > a) {
        temp = a; a = b; b = temp;
    }
    (g2, s2, t2) = ExtGCD (a, b);
    cout << "G = "<< g2 << ", S = " << s2 << ", T = " << t2;
    return 0;
}

Answer 1

C++11引入了元组，它允许你像这样编写代码，只需最少的修改：

#include <iostream>
#include <tuple>
using namespace std;
std::tuple<int, int, int> ExtGCD (int a, int b)
{
    int g, s, t, g1, s1, t1;
    if (b == 0) {
        return std::make_tuple(a, 1, 0);
    }
    std::tie(g1, s1, t1) = ExtGCD(b, a%b);
    g = g1;
    s = s1;
    t = s1 - ((a/b)*t1);
    return std::make_tuple(g, s, t);
}
int main(int argc, char* argv[])
{
    int a,b, g2, s2, t2, temp;
    cout << "Please input a: ";
    cin >> a;
    cout << "Please input b: ";
    cin >> b;
    if (b > a) {
        temp = a; a = b; b = temp;
    }
    std::tie(g2, s2, t2) = ExtGCD (a, b);
    cout << "G = "<< g2 << ", S = " << s2 << ", T = " << t2;
    return 0;
}

请参阅 http://en.cppreference.com/w/cpp/utility/tuple/tie 和 http://en.cppreference.com/w/cpp/utility/tuple。

在相关说明中，您还可以替换

if (b > a) {
    temp = a; a = b; b = temp;
}

由

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

甚至通过

std::tie(b, a) = std::minmax({a, b});

C++标准库提供了许多算法工具，应该学习这些工具以充分发挥其潜力C++。

Answer 2

return (g, s, t);

不做你想的那样。不可能从这样的函数返回多个值。如果要解释该代码的作用，请查找逗号运算符。

有几种不同的方法可以解决这个问题。也许最简单的方法是通过传递给函数的引用返回您的值。喜欢这个

#include <iostream>
using namespace std;
void ExtGCD (int a, int b, int& g, int& s, int& t)
{
    int g1, s1, t1;
    if (b == 0) {
        g = a;
        s = 1;
        t = 0;
        return;
    }
    ExtGCD(b, a%b, g1, s1, t1);
    g = g1;
    s = s1;
    t = s1 - ((a/b)*t1);
}
int main(int argc, char* argv[])
{
    int a,b, g2, s2, t2, temp;
    cout << "Please input a: ";
    cin >> a;
    cout << "Please input b: ";
    cin >> b;
    if (b > a) {
        temp = a; a = b; b = temp;
    }
    ExtGCD (a, b, g2, s2, t2);
    cout << "G = "<< g2 << ", S = " << s2 << ", T = " << t2;
    return 0;
}

在此代码g中，s 和 t 是引用，这意味着对它们的赋值会在调用函数时更改绑定到引用的变量的值。

Answer 3

你不能像这样返回元组。

在C++中，逗号运算符将扔掉左侧的内容。在您的特定情况下，"元组"(a,b,c)实际上等于 c 。一个更具体的例子：

if (b == 0) {
    return (a, 1, 0);
}

其实和

if (b == 0) {
    return 0;
}

要一次返回多个内容，您必须使用结构或类。