0

Euclid のアルゴリズムの問​​題で再び問題が発生しています。これを MS Visual Studio でコンソール アプリケーションとして実行しています。実行すると、「プロセスはスタックオーバーフロー例外により終了しました」と表示されます。

私は最近、このアルゴリズムに関する別の質問を投稿しましたが、今この問題を抱えており、初めて見ました。私は初心者プログラマーです。

int algoritmoeuclides(int a,int b)
{
if (a%b==0)
return b;
return algoritmoeuclides(b,a%b);
}

std::pair<int, int>division(int dividendo,int divisor)
{
    int resultado=0;
    int residuo=0;
    residuo=dividendo%divisor;
    resultado=dividendo/divisor;
    return std::pair<int, int>(residuo,resultado);
}

std::pair<int, int>EuclidesExtendido(int a,int b)
{
    int q,r,s,t;
    if (b == 0)
    return std::pair<int, int>(1, 0);
    else
        {
        std::pair<int, int>(q, r) = division(a, b);
        std::pair<int, int>(s, t) = EuclidesExtendido(b, r);
        }
        return std::pair<int, int>(t, s - q * t);
}

int main(array<System::String ^> ^args)
{
int a=525;
int b=231;
int s,t;
std::pair<int, int>(s, t)=EuclidesExtendido(a,b);
printf("%d",algoritmoeuclides(a,b));
printf("s=%d  t=%d",s,t);

getch();
}
4

3 に答える 3

4

関数の戻り値を正しく収集していません。

2 つの値がありますが、ペアは 1 つのオブジェクトです。そう

std::pair<int, int>(q, r) = division(a, b);

次のようになります。

std::pair<int, int> qr = division(a, b);

そして、次の方法qでr個別に取得できます。

int q = qr.first;
int r = qr.second;

同様のエラーが発生しているすべての場所で、この種の変更を行う必要があります。

于 2012-05-20T03:38:18.067 に答える
1

GNU でコードをコンパイルしg++、 をコメントアウトし、getch()の定義をmain()より単純なものに変更しint main()(コードは引数を使用しないため)、<cstdio>および<utility>ヘッダーを追加すると、広範な警告が表示されます。

euc.cpp: In function ‘int main()’:
euc.cpp:43:1: warning: ‘s’ is used uninitialized in this function [-Wuninitialized]
euc.cpp: In function ‘std::pair<int, int> EuclidesExtendido(int, int)’:
euc.cpp:23:5: warning: ‘r’ may be used uninitialized in this function [-Wuninitialized]
euc.cpp:28:60: warning: ‘r’ may be used uninitialized in this function [-Wuninitialized]
euc.cpp:30:44: warning: ‘q’ may be used uninitialized in this function [-Wuninitialized]
euc.cpp:30:44: warning: ‘t’ may be used uninitialized in this function [-Wuninitialized]
euc.cpp:30:44: warning: ‘s’ may be used uninitialized in this function [-Wuninitialized]
euc.cpp: In function ‘int main()’:
euc.cpp:40:29: warning: ‘s’ is used uninitialized in this function [-Wuninitialized]
euc.cpp:40:29: warning: ‘t’ is used uninitialized in this function [-Wuninitialized]

MS Visual Studio で警告レベルを上げて、このような警告が表示され、ここで質問を送信する前に修正できるようにする必要があります。初期化されていない変数を使用していることを考えると、疑似ランダムな値で遊ぶことになります。これにより、システムが予想よりもはるかに深い再帰に追い込まれ、スタック オーバーフローが発生する可能性があります。

このコードは、Mac OS X 上で自明の問題なしにコンパイルおよび実行されます。答えは次のとおりです。

21
s=-1  t=64

それがあなたが期待しているものかどうかはわかりません。21 は、231 (11x7x3) と 525 (7x5x5x3) の最大公約数です。-1 は正しくないと思われます (したがって、64 もおそらく間違っています)。

#include <cstdio>
#include <utility>

int algoritmoeuclides(int a, int b)
{
    if (a % b == 0)
        return b;
    return algoritmoeuclides(b, a % b);
}

std::pair<int, int>division(int dividendo, int divisor)
{
    int residuo = dividendo % divisor;
    int resultado = dividendo / divisor;
    return std::pair<int, int>(residuo, resultado);
}

std::pair<int, int>EuclidesExtendido(int a, int b)
{
    if (b == 0)
        return std::pair<int, int>(1, 0);
    else
    {
        std::pair<int, int>q = division(a, b);
        std::pair<int, int>s = EuclidesExtendido(b, q.second);
        return std::pair<int, int>(s.second, s.first - q.first * s.second);
    }
}

int main()
{
    int a = 525;
    int b = 231;
    std::pair<int, int>p = EuclidesExtendido(a, b);
    printf("%d\n", algoritmoeuclides(a, b));
    printf("s=%d  t=%d\n", p.first, p.second);
}
于 2012-05-20T03:53:24.293 に答える
0

割り当て可能な参照のペアを作成するヘッダーからではなく、いくつstd::pair<int, int>(s, t)かの C++11 ライブラリ機能を使用しても問題ないと仮定します。std::tie(s, t)<tuple>

于 2012-05-20T04:22:52.270 に答える