Ejemplo de una función recursiva: M.C.D.

Carlos Ibáñez Freire

/* Este programa calcula el MÁXIMO común divisor y el MÍNIMO común
múltiplo, de dos números. RESOLUCIÓN MEDIANTE FUNCIÓN RECURSIVA.

El m.c.d. de a y b es igual a la multiplicación, de los factores
comunes de a y b. El m.c.m es la multiplicación de los factores comunes
y no comunes con su mayor exponente.

Aunque para implementarlo, usaremos el algoritmo de Euclides para
hallar el m.c.d. y la formula: a*b = m.c.m(a,b) * m.c.d(a,b) para
obtener su m.c.m.

Resumen del algoritmo de Euclides:  D>=d  ; m.c.d.(a,b) = m.c.d(b,a);
D=d*c+r, m.c.d.(D,d)= m.c.d(d,r)= m.c.d.(r,...)...;   m.c.d.(a,0)=a
Es decir, el m.c.d. de D y d es igual al de d y el resto de su
división, y cuando el resto sea igual a 0 entonces tenemos el m.c.d.
*/

#include<stdio.h>
int mcd(int a,int b);

int main ()
{
int a,b,d,mcm;
printf("\nEste programa halla el m.c.d. y m.c.m de dos numeros dados.\n");

printf("\n Introduce los dos numeros: \n");
scanf("%d%d",&a,&b);
d=mcd(a,b);
if(d<0) d*=-1; // consideramos el m.c.d. y m.c.m positivos.
printf("\n El m.c.d. es : %d\n",d );

mcm= (a*b)/d;
if(mcm<0) mcm*=-1;
printf("\n El m.c.m. es : %d\n",mcm );

return 0;
}

int mcd(int a,int b) // función recursiva.
{
    return(b==0) ? a : mcd(b,a%b);
  //si b==0 es verdad,devolvemos a = m.c.d.
  //si no,entramos en otra función recursiva (hasta que se resuelva).
}
Esta entrada fue publicada en Informática e Internet. Guarda el enlace permanente.

2 respuestas a Ejemplo de una función recursiva: M.C.D.

  1. Amy Obrian dijo:

    I like this internet site because so much useful stuff on here : D.

  2. carlos dijo:

    esta bien el ejemplo pero solo falta en lenguaje Java

Deja un comentario

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s