Найти НОД в программировании на C

Введение

В программировании на C наибольший общий делитель (GCD) часто вычисляется. Обычно используются два различных способа для нахождения GCD. Мы можем использовать алгоритм Евклида и вычислять GCD путём повторяющихся вычитаний. В этом пошаговом практическом занятии мы покажем оба метода.

Skills Graph

Использование алгоритма Евклида

Алгоритм Евклида, при котором числитель заменяется на остаток от деления, используется для вычисления НОД. Когда остаток становится равным нулю, НОД равен числителю.

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 Наконец, выведите НОД двух чисел.

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

Использование метода повторяющихся вычитаний

В этом методе НОД вычисляется путём повторяющегося вычитания меньшего значения из большего, пока они не станут равными. Если оба значения станут равными, то это число является НОД.

2.1 Начните с целочисленной переменной под именем num, инициализированной значением 0.

    int num = 0;

2.2 Объявите целочисленную переменную под именем x и инициализируйте значением 2.

    int x = 2;

2.3 попросите пользователя ввести количество целых чисел, для которых нужно найти НОД.

    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() для вычисления НОД введённых значений.

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

Объединение методов

В этом шаге мы объединим методы для завершения реализации.

3.1 Объявите функцию 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)    // infinite loop to take input
    {
        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: алгоритм Евклида и метод повторяющихся вычитаний. Мы показали, как использовать эти методы с детальным объяснением и примерами кодовых блоков. Для дальнейшего понимания рекомендуется изменить и выполнить код в файле main.c.