欧几里得算法函数参数

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

- Fluke

---

我几乎可以确定它与逗号运算符有关，但我还不知道足够的信息来给出完整的答案。 - Dennis Meng

这行代码是一个函数返回语句，包含三个变量 g、s 和 t。这段代码不是 Python 语言。 - librik

打印出你的 a 和 b。如果你输入 "0"，那实际上是 ASCII 码 48。找出当你输入它们时 a 和 b 是什么。 - Mike 'Pomax' Kamermans

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++的潜力。

- SirDarius

---

谢谢你的建议。现在我只需要理解这个问题到底是怎么回事。其中关于“tie”的部分让我感到困惑。 - Fluke

std::tie(b, a) = std::minmax(a, b); 这段代码做的事情与你想象的截然不同。你需要的是一个 initializer_list 的重载版本 std::minmax。 - robson3.14

@user2797124，std::tie创建了一个左值引用类型的元组，这意味着从一个元组到这个元组的赋值操作实际上修改了作为参数传递的变量。 - SirDarius

@SirDarius 我知道，这也是我在评论中写的。 - Christian Rau

请参见https://dev59.com/vmMk5IYBdhLWcg3w2RaT，其中包含有关std :: minmax和std :: tie的重载的信息。 - SirDarius

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都是引用，这意味着对它们的赋值会在函数被调用时改变与引用绑定的变量的值。

- john

---

太棒了，谢谢！我完全忘记了引用和从函数内部更改变量。 - Fluke

Answer 3

你不能像那样返回元组。

在C++中，逗号运算符会抛弃左边的内容。在你的情况下，“元组” (a,b,c) 实际上等于只有c。以下是一个更具体的例子：

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

实际上等同于

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

为了一次性返回多个东西，你需要使用结构体或类。

- Dennis Meng