0

以下程序出现分段错误。我正在尝试使用递归函数找出 GCD。代码是：

#include<stdio.h>

int gcd(int a, int b)
{
    int temp, g, c;
    if(a>b)
    {
        c=a;
        a=b;
        b=c;
    }

    //printf("The values of a and b are: %d %d",a,b);
    temp = a % b;

    if(temp != 0)
    {
        g = gcd(b, temp);
        return(g);
    }

    if(temp == 0)
        g= b;

    return g;
}

int main()
{
    int a,b;
    printf("Enter two numbers: \n");
    scanf("%d %d", &a, &b);
    printf("The GCD of two numbers you entered are: %d\n", gcd(a,b));
}

我发现的问题在于交换变量。如果我要删除它，那么代码工作正常。谁能告诉我哪里出错了？我正在尝试使用Euclidean algorithm. 所以没有其他方法可以实现。

4

6 回答 6

2

与其在 GCD 函数中交换变量，不如在主函数本身中找到最大数并将其作为a和最小数作为b发送。

    int GCD(int a, int b)
    {
        if (b == 0)
            return a;
        else
            return GCD(b, a % b);
    }
于 2013-09-04T16:11:56.217 回答
2 
if(a>b)
{
    c=a;
    a=b;
    b=c;
}

temp = a % b;

问题就在这里。首先，您要确保b > a. 现在，如果 b 大于 a，不难证明a % b == a。例如，2% 5 = 2。

只需将最后一行替换为

temp = b % a;

或者，更好的是，反转交换条件：

if(a < b)
于 2013-09-04T15:20:09.930 回答
0

条件应该是

if (a < b)

因为做

// Pre-condition: a >= b
temp = a % b;
// Post-condition: temp < b or temp == 0.

然后打电话gcd(b, temp)

有：temp < b, b <= min(original a, original b)

所以 gcd 终止（a + b每次调用变体变小）。

于 2013-09-04T15:25:34.103 回答
0

我认为不需要 if (a > b) 测试，只需将其删除即可。如果 a >= b，则代码按您的意愿工作；如果没有，第一个递归调用只是进行交换。

于 2013-09-04T15:41:10.390 回答
0

您真的不需要检查每个更大的步骤（a 或 b）。

使用以下函数计算两个数字的 gcd。

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

而已。

于 2016-06-15T08:45:42.693 回答
-1

为什么要把事情复杂化这么多？用这个：

int findgcd(int x,int y){
     while(x!=y){
          if(x>y)
              return findgcd(x-y,y);
          else
             return findgcd(x,y-x);
     }
     return x;
}
于 2013-09-04T16:05:59.887 回答