0

我的欧几里得算法问题再次出现问题。我在 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

您错误地收集了函数的返回值。

尽管有两个值，但一对是单个对象。所以

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>and<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

假设您可以使用某些 C++11 库功能，而不是std::pair<int, int>(s, t)希望std::tie(s, t)从<tuple>创建一对可以分配的引用的标头中获得。

于 2012-05-20T04:22:52.270 回答