如何使用递归打印最大公约数？

Question

我正在尝试编写一个代码来使用递归计算两个数字的 GCD（Greatest Common Divisor）。

虽然我可以打印数字的公约数，但我很难打印 GCD。

这就是我必须打印的公约数：

#include <stdio.h>

void gcd(int num1, int num2, int i) {
    int x;
    int small = (num1 < num2) ? num1 : num2;
    if (i == small) {
        return;
    } else {
        if (num1 % i == 0 && num2 % i == 0) {
            x = i;
           printf("%d ", x);
        }
        gcd(num1, num2, i + 1);
    }
    
}

int main() {
    int num1, num2, i;
    printf("Enter the 1st number: ");
    scanf("%d", &num1);
    printf("Enter the 2nd number: ");
    scanf("%d", &num2);
    i = 1;
    gcd(num1, num2, i);
    return 0;
}

现在我必须打印 GCD。但是当我运行以下程序时，我得到随机输出（可能是地址）。我该如何解决这个问题？

这是我迄今为止打印的 GCD：

#include <stdio.h>

void gcd(int num1, int num2, int i) {
    int x;
    int small = (num1 < num2) ? num1 : num2;
    if (i == small) {
        return;
    } else {
        if (num1 % i == 0 && num2 % i == 0) {
            x = i;
           
        }
        gcd(num1, num2, i + 1);
    }
   printf("%d ", x);
}

int main() {
    int num1, num2, i;
    printf("Enter the 1st number: ");
    scanf("%d", &num1);
    printf("Enter the 2nd number: ");
    scanf("%d", &num2);
    i = 1;
    gcd(num1, num2, i);
    return 0;
}

Answer 1

来自我的档案。不知道从哪里得到的。

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

Answer 2

问题

我知道在你的第一个代码中，你想要考虑从 1 到更小的数字并找到公约数。但是当您使用

if (i == small)

时，当

gcd

等于较小的数字时，函数

i

将返回。这意味着当一个数字恰好是另一个数字的倍数时，函数 不会 输出 GCD（例如

6

和

12

）。因此您应该使用

if (i > small)

。

代码中的另一个问题是在第二个代码中，正如comment部分所指出的，

x

的值未定义，因此程序可能会输出未定义的值（例如

2097184

），这就是为什么你会得到随机值输出。因此，您可能应该初始化

x

，例如

int x = 0;

。

解决方案

我建议你使用带有返回值的函数，因为返回值可以加入其他计算并创建可移植性。

解决方案之一就是找到公约数，然后找到最大的那个。
你仍然可以使用你的函数

gcd(int num1, int num2, int i)

，但是你可以让它有一个返回值，意思是从

i

到较小的数，即两个数字的公约数，并且返回值

0

意味着没有符合以上条件的号码。
源代码：

#include <stdio.h>

int gcd(int num1, int num2, int i) {
    int x = 0, y;
    int small = (num1 < num2) ? num1 : num2;
    if (i > small) {
        return 0;
    } else {
        if (num1 % i == 0 && num2 % i == 0) {
            x = i;
        }
        y=gcd(num1,num2,i + 1);
        return (x > y) ? x : y;
    }
}

int main() {
    int num1, num2, i;
    printf("Enter the 1st number: ");
    scanf("%d", &num1);
    printf("Enter the 2nd number: ");
    scanf("%d", &num2);
    i = 1;
    printf("%d",gcd(num1, num2, i));
    return 0;
}

解决问题的另一种方法是使用Euclid算法，正如注释部分提到的，可以用以下语句来表达：

gcd(a, b) = gcd(b, a%b) (a >= b)

所以，我们可以使用一个

gcd(int num1, int num2)

函数，让

gcd

函数在

gcd(num2, num1 % num2)

时返回

num1 >= num2

。
但是当其中一个数字是

0

时该怎么办？我们返回另一个号码。
根据上面的内容，我们可以编写如下源码：

#include <stdio.h>

int gcd(int num1, int num2) {
    if (num1 == 0) {
        return num2;
    } else if (num2 == 0) {
        return num1;
    } else {
        return gcd(num2, num1 % num2);
    }
}

int main() {
    int num1, num2;
    printf("Enter the 1st number: ");
    scanf("%d", &num1);
    printf("Enter the 2nd number: ");
    scanf("%d", &num2);
    printf("%d",gcd(num1, num2));
    return 0;
}

结论

上面列出了该问题的一些可能的解决方案。
我觉得如果用

loops

来解决问题的话会更容易写和理解。当然，了解其他方法以及背后的逻辑思想对你来说也是有好处的。

Answer 3

GCD 在 C 中的递归实现是（欧几里得：公元前 300 年左右）：

#include <stdio.h>

int gcd(int a, int b)
{
    int rem = a % b;
    return rem != 0
        ? gcd(b, rem)
        : b;
} /* gcd */

int main()
{
#define P(a, b)                        \
        printf("P(%d, %d) -> %d\n",    \
                   a,  b,    gcd(a, b))
    P(8, 6);
    P(8, 16);
    P(7, 24);
} /* main */

我无法猜测您在问题中所写的内容是从哪里得到的。对此我深表歉意。