1

Euclidの拡張アルゴリズムのウィキペディアからこの擬似コードを見つけましたが、関数から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では、関数から実際に2つの値を返すことはできませんが、同じ効果を実現する方法はいくつかあります。

を返すことができますstruct。たとえば、divで宣言された関数を参照してください。この関数は、タイプの結果、およびメンバーを含む構造体を<stdlib.h>返します。div_tquotrem

または、ポインタを渡すことにより、間接的に複数の結果を「返す」ことができます。

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はこれに使用できます。すなわち、

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 に答える