funciones - Función GCD en c++ sans cmath library

math.h c++ ejemplos

Question

Estoy escribiendo una clase de numeración mixta y necesito una función rápida y fácil de "máximo divisor común". ¿Alguien me puede dar el código o un enlace al código?

Answer 1

El algoritmo Euclidean es bastante fácil de escribir en C.

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

Answer 2

Estoy tentado a votar para cerrar: parece difícil creer que una implementación sería difícil de encontrar, pero quién sabe a ciencia cierta.

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

En C ++ 17 o más reciente, simplemente puede #include <numeric> , y usar std::gcd (y si le importa el gcd, probablemente esté interesado en el std::lcm que se agregó) también).

Answer 3

La biblioteca de algoritmos libstdc ++ tiene una función gcd oculta (estoy usando g ++ 4.6.3).

#include <iostream>
#include <algorithm>

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

De nada :)

ACTUALIZACIÓN: Como @ chema989 lo señaló, en C ++ 17 hay una función std::gcd() disponible con el encabezado <numeric> .

Answer 4

Para C ++ 17 puede usar std::gcd definido en el encabezado <numeric> :

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

Answer 5

Una versión rápida recursiva:

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

o la versión iterativa equivalente si se opone violentamente a la recursión ^(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;
}

Simplemente sustituya en su propio tipo de datos, comparación de cero, método de asignación y módulo (por ejemplo, si está utilizando algún tipo no básico como una clase bignum ).

Esta función realmente proviene de una de mis respuestas anteriores para elaborar relaciones de aspecto integrales para tamaños de pantalla, pero la fuente original fue el algoritmo euclidiano que aprendí hace mucho tiempo, detallado aquí en Wikipedia si desea conocer las matemáticas detrás de él.

^(a) El problema con algunas soluciones recursivas es que se aproximan a la respuesta tan lentamente que tiende a quedarse sin espacio en la pila antes de llegar allí, como con el pseudo-código muy mal pensado:

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

Lo encontrará muy costoso en algo así como la sum (1, 1000000000) ya que (intenta) usar un billón o más de marcos de pila. El caso de uso ideal para la recursión es algo así como una búsqueda binaria en la que reduce el espacio de la solución a la mitad para cada iteración. El mayor divisor común es también uno en el que el espacio de la solución se reduce rápidamente, por lo que los temores sobre el uso masivo de pila son infundados allí.