/****************************************************************************/ /* Encuentra el mcd de n números expresado como combinación lineal de ellos */ /* */ /* Jaime Suarez <mcripto@bigfoot.com> 2003 */ /* en http://elparaiso.mat.uned.es */ /****************************************************************************/ #include <stdio.h> #include <stdlib.h> void mcd(long *a, long *c, long *m, int n); void mcd_aux(long a, long b, long *alfa, long *beta, long *m); main(int argc, char *argv[]) { long *a, *c, alfa, beta, m; int n,i; /* Tomar datos de la linea de comandos */ n=argc-1; if (n < 2) { printf ("%s n1 n2 ... nk calcula el mcd de los numeros\n",argv[0]); printf ("y lo expresa como combinación lineal de ellos.\n"); return 1; } a=(long *)malloc(n*sizeof(long)); c=(long *)malloc(n*sizeof(long)); if (c==NULL) { printf("No hay suficiente memoria.\n"); return 1;} for (i=0; i<n; i++) *(a+i)=atol(argv[i+1]); /* Llamada a la función */ mcd(a,c,&m,n); /* Escribir resultados */ putchar('('); for (i=0; i<n-1; i++) printf("%ld,",*(a+i)); printf("%ld) = %ld = ",*(a+n-1),m); for (i=0; i<n-1; i++) printf("%s%ld*%ld",(*(c+i)>=0)?" +":" ",*(c+i),*(a+i)); printf("%s%ld*%ld\n",(*(c+n-1)>=0)?" +":" ",*(c+n-1),*(a+n-1)); return 0; } /* ---------------------------------------------------------------- * Entrada: a puntero a un array de n long, c idem, * n numero de enteros, m puntero a long * Salida : ninguna * Efecto : *m contiene el mcd de a[0],a[1]...a[n] * c[0]...c[n] los coeficientes de la combinación lineal * igual al mcd. ------------------------------------------------------------------*/ void mcd(long *a, long *c, long *m, int n) { long i,j,m1,alfa,beta; long *b; /* Hacemos una copia de a en b */ b=(long *)malloc(n*sizeof(long)); if (b==NULL) {printf("No hay suficiente memoria.\n"); exit (1);} memcpy(b,a,n*sizeof(long)); /* Comienzo del algoritmo */ *(c+n-1)=1; for (i=n-2; i>=0; i--) { mcd_aux(*(b+i),*(b+i+1),&alfa,&beta,&m1); *(b+i)=m1; *(c+i)=alfa; for (j=i+1; j<n; j++) *(c+j) *= beta; } *m = *b; return; } /* ------------------------------------------------------------------ * Entrada: a y b enteros long, alfa, beta y m punteros a long * Salida : ninguna * Efecto : *m contendrá el mcd de a y b * *alfa y *beta los enteros tales que m=alfa*a+beta*b --------------------------------------------------------------------*/ void mcd_aux(long a, long b, long *alfa, long *beta, long *m) { long s0,t0,s1,t1,s,t,q,r=1; if (a<b) return mcd_aux(b,a,beta,alfa,m); s0=1; t0=0; s1=0; t1=1; while (r != 0) { q = a/b; r = a%b; s = s0 - q*s1; t = t0 - q*t1; s0=s1; t0=t1; s1=s ; t1=t ; a =b ; b =r ; } *m=a; *alfa=s0; *beta=t0; return; }