0

这是我们应该用 C++ 解决的问题：

GCD ( 2m , 2n )         =  2 * GCD( m , n )
GCD ( 2m , 2n+1 )       = GCD ( m , 2n+1 )
GCD ( 2m+1,  2n+1 ) = GCD ( n-m , 2m+1 )  (m<n)
GCD ( m , m )       = m

这是我写的函数：

int GCD(int n1, int n2)
{
    bool n1Zoj, n2Zoj;
    n1Zoj = (n1%2 == 0);
    n2Zoj = (n2%2 == 0);

    if(n1Zoj && n2Zoj)
        return 2 * GCD(n1/2, n2/2);

    if(n1Zoj && !n2Zoj)
        return GCD(n1/2, n2);

    if(!n1Zoj && !n2Zoj)
        return GCD((n2-n1)/2, n1);

    if(n1 == n2)
        return n1;
}

（*“Zoj”在我的语言（波斯语）中的意思是“偶数”）

当我将 5 作为第二个参数传递时，程序崩溃并打印此消息：

Segmentation fault (core dumped)

退出代码是139。我在使用 g++ 作为编译器的 ubuntu 12.04 上使用 Code::Blocks。

更新：程序崩溃 5,10,15,20,25,...

更新：我认为正确的函数形式是：

int GCD(int n1, int n2)
{
    if (n1 > n2)
        std::swap(n1, n2);

    //std::cout<<"GCD is called with params: "<<n1<<" & "<<n2<<std::endl;
    bool n1Zoj, n2Zoj;

    n1Zoj = (n1%2 == 0);
    n2Zoj = (n2%2 == 0);

    if(n1 == n2)
        return n1;

    if(n1Zoj && n2Zoj)
        return 2 * GCD(n1/2, n2/2);

    if(n1Zoj && !n2Zoj)
        return GCD(n1/2, n2);

    if(!n1Zoj && n2Zoj)
        return GCD(n2/2, n1);

    if(!n1Zoj && !n2Zoj)
        return GCD((n2-n1)/2, n1);
}
4

1 回答 1

9

当(n1Zoj && n2Zoj)评估为真时，你会做什么？你打电话

return 2 * GCD(n1, n2);

它使用完全相同的参数调用函数，导致无限递归、堆栈溢出和堆栈溢出（分段错误）。

Protip - 学习调试 - 我无法强调这是多么重要。

于 2012-12-20T12:14:28.357 回答