在 C 语言中计算 GCD

介绍

在 C 语言编程中，GCD（最大公约数，Greatest Common Divisor）的计算非常常见。通常有两种不同的方法来计算 GCD。我们可以使用欧几里得算法（Euclidean algorithm），或者通过重复减法来计算 GCD。在这个逐步的实验中，我们将演示这两种方法。

使用欧几里得算法

欧几里得算法（Euclidean algorithm）通过用除法的余数替换分子来计算 GCD。当余数为零时，GCD 就是分子。

1.1 首先声明两个整数变量 a 和 b 来开始解决方案。

    int a, b;

1.2 接下来，要求用户输入 a 和 b 的值。

    printf("Enter two numbers: \n");
    scanf("%d %d", &a, &b);

1.3 然后，创建一个 while 循环，直到 a 除以 b 的余数为零时停止。

    while(a!=b)
    {
        if(a>b)
            a=a-b;
        else
            b=b-a;
    }

1.4 最后，显示这两个数的 GCD。

    printf("The GCD of two numbers is %d", a);

使用重复减法方法

在这种方法中，GCD 是通过从较大的值中重复减去较小的值，直到两者相等来计算的。如果两者相等，则该数就是 GCD。

2.1 首先声明一个名为 num 的整数变量，并初始化为 0。

    int num = 0;

2.2 声明一个名为 x 的整数变量，并初始化为 2。

    int x = 2;

2.3 要求用户输入要计算 GCD 的整数数量。

    printf("Enter the number of integers you want to find the GCD of: ");
    scanf("%d", &num);

2.4 然后，要求用户输入这些数字。

    printf("Enter %d numbers:\n", num);
    int arr[num];
    for(int i = 0; i < num; i++)
    {
        scanf("%d", &arr[i]);
    }

2.5 现在，我们可以通过输入值并使用重复减法方法来计算 GCD。我们将调用 gcd() 函数来计算输入值的 GCD。

    int result = arr[0];
    for(int i = 1; i < num; i++)
    {
        result = gcd(result, arr[i]);
    }

结合两种方法

在这一步中，我们将结合两种方法来完成实现。

3.1 声明一个 gcd() 函数，用于通过重复减法方法计算 GCD。

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

3.2 声明一个名为 gcd_result 的新变量，并将其初始化为 0。

    int gcd_result = 0;

3.3 我们将创建一个新的循环，提示用户输入数字，直到检测到输入值为 0。

    printf("Enter numbers. To exit enter 0\n");
    while(1)    // 无限循环以接收输入
    {
        int num;
        scanf("%d", &num);
        if(num < 1)
            break;
        else if(gcd_result == 0)
            gcd_result = num;
        else if(num < gcd_result)
            gcd_result = gcd(num, gcd_result);
        else
            gcd_result = gcd(gcd_result, num);
    }

3.4 最后，使用 printf 函数显示最终结果。

    printf("The GCD of all the entered numbers is: %d\n", gcd_result);

总结

在本实验中，我们学习了在 C 语言编程中计算一组整数的 GCD 的两种方法：欧几里得算法（Euclidean algorithm）和重复减法方法。我们通过详细的解释和示例代码块演示了如何使用这些方法。为了进一步理解，建议修改并执行 main.c 文件中的代码。