Cálculo del máximo común divisor MCD por el método de Euclides en C

Publicado en Informática Etiquetado con

– Prog066

/* Prog066.cpp */
/* Cálculo del M.C.D de dos números */
#include <stdio.h>
void main()
{
int x,y; int aux; int resto;
printf(«n Escribe un número x: «); scanf(«%d»,&x);
printf(«n Escribe otro número y: «); scanf(«%d»,&y); if(x<y)
{
aux=x;
x=y;
y=aux;
}
if((x % y) == 0) resto=y;
while ((x % y) != 0)
{
resto=x-y*(x/y); x=y;
y=resto;
}
printf(«n El M.C.D es: %d»,resto);
}

El programa anterior pero utilizando una función

– Prog067

/* Prog067.cpp */

#include <stdio.h>
int MCD(int,int); void main()
{
int a,b;
int mcd;
printf(«n Número: «);
scanf(«%d»,&a); printf(«n Número: «); scanf(«%d»,&b); mcd=MCD(a,b);
printf(«nn El MCD de %d y %d es %d»,a,b,mcd);
}
int MCD(int x,int y)
{
int aux; int resto; if(x<y)
{
aux=x;
x=y;
y=aux;
}
if((x % y) == 0) resto=y; while ((x % y) != 0)
{
resto=x-y*(x/y); x=y;
y=resto;
}
return resto;
}

A partir del Fich001.c escribe el siguiente fichero, que deberás grabar donde siempre – Fich002.c

/* Fich002.c */
/* Determinación de un número primo
*/ int primo(int num)
{
int resto,i,result; for(i=2;i<num-1;i++)
{
resto=num % i;
if ((resto==0) && (num != 2)) return 0;
}
return 1;
}

/* Determinación del M.C.D de dos números
*/ int MCD(int x,int y)
{
int aux;
int resto;
if (x<y)
{
aux=x;
x=y;
y=aux;
}
if ((x % y)==0) resto=y;
while ((x % y) != 0)
{
resto=x-y*(x/y); x=y;
y=resto;
}
return resto;
}

No compiles el fichero anterior ya que se trata de un fichero biblioteca

Vamos a probar la función MCD, que acabamos de incluir en Fich002.c

– Prog068

/* Prog068.cpp */

#include <stdio.h>
#include «c:TuCarpetaFich002.c»
void main()
{
int a,b;
int mcd;
char otra[1];
otra[0]=’s’;
while (otra[0]==’s’)
{
printf(«n Número: «);
scanf(«%d»,&a);
printf(«n Número: «);
scanf(«%d»,&b); mcd=MCD(a,b);
printf(«nn El MCD de %d y %d es %d»,a,b,mcd);
printf(«nn Quieres otro MCD (s/n)? «);
scanf(«%s»,otra);
}
}

Vamos a hacer el mismo programa anterior pero que calcule también el mínimo común múltiplo.

– Prog069

/* Prog069.cpp */

#include <stdio.h>
#include «c:TuCarpetaFich002.c»
void main()
{
int a,b;
int mcd;
int prod;
char otra[1];
otra[0]=’s’;
while (otra[0]==’s’)
{
printf(«n Número: «); scanf(«%d»,&a);
printf(«n Número: «); scanf(«%d»,&b);
prod=a*b;
mcd=MCD(a,b);
printf(«nn El MCD de %d y %d es %d»,a,b,mcd);
printf(«nn El mcm de %d y %d es %d»,a,b,prod/mcd);
printf(«nn Quieres otro cálculo (s/n)? «); scanf(«%s»,otra);
}
}

Programa que simplifica una fracción, utilizando la función MCD, que tenemos enFich002.c

– Prog070

/* Prog070.cpp */

#include <stdio.h>
#include «c:TuCarpetaFich002.c»
void main()
{
int a,b;
int div;
printf(«n Escribe el numerador: «); scanf(«%d»,&a);
printf(«n Escribe el denominador: «); scanf(«%d»,&b);
div=MCD(a,b);
printf(«n Fracción simplificada: %d / %d»,a/div,b/div);
}

Vamos a hacer el programa anterior pero con arrays.

– Prog071

/* Prog071.cpp */

#include <stdio.h>
#include «c:TuCarpetaFich002.c»
void main()
{
int f [2],fs [2]; int i,div;
printf («n Escribe el numerador: «); scanf(«%d»,&f[0]);
printf («n Escribe el denominador: «); scanf(«%d»,&f[1]); div=MCD(f[0],f[1]);
for (i=0;i<2;i++) fs[i]=f[i]/div;
printf(«n Fracción simplificada: %d / %d»,fs[0],fs[1]);
}

Vamos a hacer el mismo programa pero a través de una función: simplifica

– Prog072

/* Prog072.cpp */

#include <stdio.h>
#include «c:TuCarpetaFich002.c»
void simplifica(int ,int );
void main()
{
int f [1];
int i;
printf(«n Escribe el numerador: «); scanf(«%d»,&f[0]);
printf(«n Escribe el denominador: «); scanf(«%d»,&f[1]); simplifica(f[0],f[1]);
}
void simplifica(int a,int b)
{
int div; div=MCD(a,b);
printf(«n Fracción Simplificada: %d / %d»,a/div,b/div);
}

A partir del Fich002.c escribe el siguiente:

– Fich003.c

/* Fich003.c */
/* Determinación de un número primo
*/ int primo(int num)
{
int resto,i,result; for(i=2;i<num-1;i++)
{
resto=num % i;
if ((resto==0) && (num != 2)) return 0;
}
return 1;
}
/* Determinación del M.C.D de dos números
*/ int MCD(int x,int y)
{
int aux;
int resto;
if (x<y)
{
aux=x;
x=y;
y=aux;
}
if ((x % y)==0) resto=y;
while ((x % y) != 0)
{
resto=x-y*(x/y); x=y;
y=resto;
}
return resto;
}
/* Simplifica una fracción
*/ void simplifica(int a,int b)
{
int div;
div=MCD(a,b);
printf(«nFracción Simplificada: %d / %d»,a/div,b/div);
}
Vamos a probar la función simplifica que tenemos en Fich003.c

– Prog073

/* Prog073.cpp */
#include <stdio.h>
#include «c:TuCarpetaFich003.c»
void main()
{
int f[1];
int i;
printf(«n Escribe el numerador: «); scanf(«%d»,&f[0]);
printf(«n Escribe el denominador: «); scanf(«%d»,&f[1]); simplifica(f[0],f[1]);
}

Vamos a hacer un programa que sume dos fracciones.

– Prog074

/* Prog074.cpp */

#include <stdio.h>
#include «c:TuCarpetaFich003.c»
void main()
{
int f1[2],f2[2];
int mcd,num;
printf(«Escribe la 1ª fracción: n»); scanf(«%d %d»,&f1[0],&f1[1]); printf(«Escribe la 2ª fracción: n»); scanf(«%d %d»,&f2[0],&f2[1]); mcd=(f1[1]*f2[1])/MCD(f1[1],f2[1]); num=(mcd/f1[1])*f1[0]+(mcd/f2[1])*f2[0];
printf(«nn Suma de %d/%d + %d/%d = «,f1[0],f1[1],f2[0],f2[1]); printf(» %d / %d»,num,mcd);
printf(«nn»);
simplifica(num,mcd);
}

Fuente: Programación en C/C++ (Manual FV) de Fermí Vilà