欧几里德的算法函数参数

Question

我已经为类编写了一个程序,我需要递归地计算a和b的扩展euclid算法,返回G,最大公约数,以及s和t,as + bt = gcd(a,b).我相当确定我正确编写了函数,但是我遇到了传递给函数和从函数传递的值的问题.我有一段时间没有编码,最近只写了伪代码,所以我有点生疏了.

例如,我写了当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是引用，这意味着对它们的赋值会在调用函数时更改绑定到引用的变量的值。