Estoy tratando de encontrar el GCD de dos números usando el algoritmo de Euclid en C (recursivamente) y sé que matemáticamente aún no es completamente perfecto ya que descuida las condiciones de números negativos, pero solo quiero que este funcione para números positivos por ahora.

#include <stdio.h>

int gcd(int m, int n);

int main() {
    return gcd(60, 24);
}

int gcd(int m, int n) {
    if (m < n) {
        //swapping both a and b
        m = m + n;
        n = m - n;
        m = m - n;
    }
    if (m == n) {
        return m;
    } else {
        return gcd(n, m % n);   
    }
}
1
ThisSiteSucks 30 ene. 2016 a las 02:30

1 respuesta

La mejor respuesta

gcd(60, 24) - & gt; gcd(24, 12) - & gt; gcd(12, 0).

Eso significa que debe agregar un cheque.

if ( n == 0 )
{
   return m;
}

O

if ( m%n == 0 )
{
   return n;
}

También puede eliminar el código de intercambio de variables con otra llamada a la función con los valores intercambiados en la llamada.

int gcd(int m, int n) {

   if (m < n) {
      return gcd(n, m);
   }

   if (m%n == 0) {
      return n;
   } else {
      return gcd(n, m % n);   
   }
}
4
R Sahu 29 ene. 2016 a las 23:46