Nombre Password [ Regístrate ]

Fracciones ordenadas (OIE 2 - 1998) - Código en C
#include<stdio.h>
#include<stdlib.h>

struct frac // Estructura de una fracción
{
	int num,den;
 };

int MCD(int,int); // Función que halla el máximo común divisor de dos números.
int compara(const void *,const void *); // Función de comparación para el qsort.

int main()
{
	int nume,deno,m,total=0,i;
	struct frac sol[3010]; // el número de fracciones para 99 es 3003.

	freopen("frac.dat","r",stdin); // Abrir los ficheros
	freopen("frac.out","w",stdout);

	scanf(" %d",&m); // Lee el denominador máximo
	for(deno=2;deno<=m;deno++) // Genera todas las posibles fracciones
		for(nume=1;nume<deno;nume++)
			if(MCD(nume,deno)==1) // Si es irreducible, esto es, si el
			{ // numerador y el denominador son primos entre sí:
				sol[total].num=nume; // AĄadir a las soluciones.
				sol[total].den=deno;
				total++;
			 }

	qsort(sol,total,sizeof(sol[0]),compara); // Ordenarlas.

	for(i=0;i<total;i++) // e imprimirlas.
		printf("%d %d\n",sol[i].num,sol[i].den);

	return(0);
 }
// Función que halla el máximo común divisor de dos números según el
// algoritmo de Euclides.
int MCD(int a,int b)
{
	int r=1;

//     a =  b*q1 + r1
//     b = r1*q1 + r2
//    r1 = r2*q1 + r3
//    r2 = r3*q1 + r4
//    ...
//    r_{n-1} = rn*q1 + 0
// Entonces rn es el MCD de a y b.

	while(r)
	{
		r=a%b;
		a=b;
		b=r;
	 }
	return(a);
 }
// Función de comparación del qsort.
int compara(const void *a,const void *b)
{
//   a   c
//   - < -   <=>  a*d < c*b   <=>   a*d - c*b < 0  (por ser a,b,c y d positivos)
//   b   d

//   a   c
//   - = -   <=>  a*d = c*b   <=>   a*d - c*b = 0
//   b   d

//   a   c
//   - > -   <=>  a*d > c*b   <=>   a*d - c*b > 0  (por ser a,b,c y d positivos)
//   b   d

// Entonces a*d - c*b es un posible valor que puede devolver la función:
	return((*(struct frac *)a).num*(*(struct frac *)b).den-(*(struct frac *)b).num*(*(struct frac *)a).den);
 }


© (2001-2008) ALGORITMIA.NET - Política de privacidad