Функция GCD в С++ sans cmath library

Ответ 1

У меня возникает соблазн проголосовать за закрытие - кажется, трудно поверить, что реализация будет трудно найти, но кто знает наверняка.

unsigned GCD(unsigned u, unsigned v) {
    while ( v != 0) {
        unsigned r = u % v;
        u = v;
        v = r;
    }
    return u;
}

Ответ 2

Библиотека алгоритмов libstdС++ имеет скрытую функцию gcd (я использую g++ 4.6.3).

#include <iostream>
#include <algorithm>

int main()
{
  cout << std::__gcd(100,24);
  return 0;
}

Добро пожаловать:)

ОБНОВЛЕНИЕ: Как отметил @chema989, в С++ 17 есть функция std::gcd(), доступная с заголовком <numeric>.

Ответ 3

Быстрая рекурсивная версия:

unsigned int gcd (unsigned int n1, unsigned int n2) {
    return (n2 == 0) ? n1 : gcd (n2, n1 % n2);
}

или эквивалентную итеративную версию, если вы решительно против рекурсии ^(a):

unsigned int gcd (unsigned int n1, unsigned int n2) {
    unsigned int tmp;
    while (n2 != 0) {
        tmp = n1;
        n1 = n2;
        n2 = tmp % n2;
    }
    return n1;
}

Просто замените в своем собственном типе данных, методе нулевого сравнения, присваивании и модуле (например, если вы используете неклассический тип, например класс bignum).

Эта функция действительно появилась из более раннего моего ответа для разработки интегральных соотношений сторон для размеров экрана, но исходным источником был алгоритм Евклида, который я давно изучил, подробно здесь, в Википедии, если вы хотите узнать математику за ней.

^(a) Проблема с некоторыми рекурсивными решениями заключается в том, что они подходят к ответу так медленно, что вы, как правило, выбегаете из пространства стека, прежде чем доберетесь туда, например, с очень плохо продуманным (псевдо -код):

def sum (a:unsigned, b:unsigned):
    if b == 0: return a
    return sum (a + 1, b - 1)

Вы найдете это очень дорогим на чем-то вроде sum (1, 1000000000), поскольку вы (пытаетесь) использовать миллиард кадров стека. Идеальный вариант использования для рекурсии - это что-то вроде бинарного поиска, где вы уменьшаете пространство решения на половину для каждой итерации. Наибольший общий делитель также является тем, где пространство решений быстро сокращается, поэтому опасения по поводу массового использования стека необоснованны.

Ответ 4

Алгоритм Euclidean довольно легко записать в C.

int gcd(int a, int b) {
  while (b != 0)  {
    int t = b;
    b = a % b;
    a = t;
  }
  return a;
}

Ответ 5

Для С++ 17 вы можете использовать std::gcd, определенный в заголовке <numeric>:

auto res = std::gcd(10, 20);

Ответ 6

Мои два цента; шаблонный алгоритм Евклида с использованием XOR swap для целых типов без знака:

template <class Unsigned>
Unsigned gcd( Unsigned a, Unsigned b )
{

    static_assert(
        std::numeric_limits<Unsigned>::is_integer &&
        !std::numeric_limits<Unsigned>::is_signed, "Unsigned required." );

    while ( b )
    {
        b ^= a;
        a ^= b;
        b  = (b^a) % a;
    }
    return a;
}