7

我已经为类编写了一个程序，我需要递归地评估 a 和 b 的扩展 euclid 算法，返回最大公约数 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;
}
4

3 回答 3

9

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

于 2013-09-19T22:09:35.117 回答
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是引用，这意味着对它们的赋值会在调用函数时更改绑定到引用的变量的值。

于 2013-09-19T21:43:38.807 回答
1

你不能像那样返回元组。

在 C++ 中，逗号运算符会丢弃左边的东西。在您的特定情况下，“元组”(a,b,c)实际上等于 just c。一个更具体的例子：

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

实际上是一样的

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

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

于 2013-09-19T21:41:09.953 回答