1

我从 Euclid's extended Algorithm 的 Wikipedia 中找到了这个伪代码，但我不知道如何从函数中返回 2 个值。

function extended_gcd(a, b)
    if b = 0
        return (1, 0)
    else
        (q, r) := divide (a, b)
        (s, t) := extended_gcd(b, r)
        return (t, s - q * t)

资料来源： http ://en.wikipedia.org/wiki/Extended_Euclidean_algorithm

4

3 回答 3

3

您的问题被标记为 C 和 C++。

在 C 中，您实际上不能从一个函数中返回两个值，但是有几种方法可以达到相同的效果。

您可以返回一个struct. 例如，请参见在div中声明的函数，<stdlib.h>它返回类型为的结果div_t，一个包含quot和rem成员的结构。

或者，您可以通过传递指针间接“返回”多个结果：

void func(int *result1, int *result2) {
    *result1 = 10;
    *result2 = 20;
}
...
int r1, r2;
func(&r1, &r2);

C++ 支持这两种方法，以及其他一些方法。例如，C++ 有引用类型；C++ 标准库中还有一些类型，比如std::pair和元组，可以用于这种事情。

但在开始实施之前，您应该决定使用哪种语言。

于 2012-05-20T02:14:10.313 回答
2

模板类std::pair可用于此；IE，

if (b == 0)
    return std::pair<int, int>(1, 0);
于 2012-05-20T02:04:37.550 回答
1 
#include <stdio.h>

typedef struct _tuple {
    int fst;
    int snd;
} Tuple;

Tuple tuple(int a, int b){
    Tuple ret = { a, b };
    return ret;
}

Tuple extended_gcd(Tuple x){
    if(x.snd == 0)
        return tuple(1,0);
    else {
        Tuple qr = tuple(x.fst/x.snd, x.fst%x.snd);
        Tuple st = extended_gcd(tuple(x.snd, qr.snd));
        return tuple(st.snd, st.fst - qr.fst * st.snd);
    }
}

int main() {
    Tuple ans = extended_gcd(tuple(120,23));
    printf("(%d,%d)\n", ans.fst, ans.snd);//(-9,47)
    return 0;
}
于 2012-05-20T13:16:24.617 回答