Написать вариант алгоритма Евклида, использующий соотношения НОД - C (СИ)

Узнай цену своей работы

Формулировка задачи:

Здравствуйте! Задача состоит в том, чтобы "Написать вариант алгоритма Евклида, использующий соотношения НОД(2a, 2b) = 2•НОД(a,b), НОД(2a,b) = НОД(a,b) при нечётном b, не включающий деления с остатком, а использующий лишь деление на 2 и проверку чётности. (Число действий должно быть порядка log k для исходных данных, не превосходящих k.)" И я, извините за глупость, не понимаю чего же от меня хотят, особенно часть "НОД(2a, 2b) = 2*НОД(a,b), НОД(2a,b) = НОД(a,b)". Т.е вместо обычного алгоритма нахождения нода делением меня просят написать код, основывающийся на этих равенствах? Если кто сталкивался с подобной задачей, прошу помочь.

Решение задачи: «Написать вариант алгоритма Евклида, использующий соотношения НОД»

textual
Листинг программы
#include <stdio.h>
 
/* обычная версия */
int gcd(int a, int b)
{
    if (b == 0)
        return a;
    return gcd(b, a % b);
}
 
/* через деление на 2 */
int gcd2(int a, int b)
{
    if (a == 0)
        return b;
 
    if ((b & 1) == 0)
    {
        if ((a & 1) == 0)
            return 2 * gcd2(a / 2, b / 2);
        return gcd2(b / 2, a);
    }
 
    if ((a & 1) == 0)
        return gcd2(a / 2, b);
 
    if (b > a)
        return gcd2(b - a, a);
 
    return gcd2(a - b, b);
}
 
int main(void)
{
    int a, b;
    printf("Input a, b: ");
    scanf("%d%d", &a, &b);
    printf("\ngcd(%d, %d) = %d\n", a, b, gcd(a, b));
    printf("gcd2(%d, %d) = %d\n", a, b, gcd2(a, b));
    return 0;
}

Объяснение кода листинга программы

  1. Обычная версия, представленная функцией gcd, реализует алгоритм Евклида с использованием операции модуля. Если делитель равен 0, то возвращается делимое. В противном случае, функция рекурсивно вызывается для оставшегося делителя и делимого, уменьшенного на остаток от деления на этот делитель.
  2. Версия через деление на 2, представленная функцией gcd2, использует деление на 2 и логику обработки остатков от деления. Если делимое равно 0, то возвращается делитель. Если делитель делится на 2 без остатка, то функция рекурсивно вызывается для половины делителя и половины делимого. Если делитель не делится на 2 без остатка и делимое не равно 0, то функция рекурсивно вызывается для половины делимого и половины делителя. Если делитель больше делимого, то функция рекурсивно вызывается для разности делимого и делителя и делимого. Если делимое больше делителя, то функция рекурсивно вызывается для разности делителя и делимого и делимого. В обоих случаях возвращается результат рекурсивного вызова.
  3. В функции main считываются два целых числа, затем вызывается функция gcd и gcd2 для этих чисел, и выводятся результаты на экран.

Оцени полезность:

9   голосов , оценка 4.222 из 5
Похожие ответы