GCD 如果为正数和负数-解网

问：

如下所述： .但是，当我使用以下代码时，我得到的输入输出不同（-4，-8）。gcd(a,b) = gcd(-a,b) = gcd(-a,-b)

gcd(x,y)给 -4，给 4。gcd(abs(x),abs(y))

有人能帮我理解我错在哪里吗？

int gcd(int a ,int b)
{
    if(b==0)
        return a;
    return gcd(b,a%b);
}
 int main()
{
    int x,y;
    cin>>x>>y;
    cout<<gcd(x,y)<<endl;   // gives -4
    cout<<gcd(abs(x),abs(y))<<endl;   //gives 4
    return 0;
}

C++ 数学语言不可知的最大公约数

评论

3赞 NathanOliver 9/18/2017

相关/欺骗：stackoverflow.com/questions/7594508/......

1赞 The Javatar 9/19/2017

这不是骗人，但它们肯定是相关的

0赞 John Coleman 9/19/2017

您的基本情况是错误的（在存在负值的情况下）。为什么不回来？abs(a)

答：

1赞 google user 1/19/2021 #1

你没有考虑到输出范围有一个加号或减号，这会破坏你的算法，它断言负数和正数将被视为正整数。离散数学中的形式集合论对与大多数编程语言不兼容的符号有不同的术语集。

使用递归的 C++ 中的最大公分母

int GCD(int A,int B)
{
    if(A==0) return B;
    if(B==0) return A;
    A=abs(A);
    B=abs(B);
    if(A>B) return GCD(B,A);
    return GCD(B%A,A);
}

1赞 Sajjad Ranjbar 11/22/2021 #2

您的算法无法涵盖所有正数和负数。使用下面的代码。

int gcd(int a, int b){
    a = abs(a);b = abs(b);
    if (a == 0)
        return b;
    if (b == 0)
        return a;
    if (a == b)
        return a;
    if (a > b)
        return gcd(a - b, b);
    return gcd(a, b - a);
}

上一个：如何在SQLite中表示一组标志

下一个：For 循环是否总是至少执行一次？