El método de resolución utilizado es sencillo, consiste en generar todas las fracciones con denominador menor o igual que n, y entre ellas seleccionar las irreducibles (fuerza bruta).

Para generar todas las fracciones basta con dos bucles for anidados, uno designando el numerador y otro el denominador. La dificultad del problema está en ver si una fracción es irreducible o no. Para esto hay varios métodos:

1.- Ver si hay algún número entre 2 y el denominador que sea divisor a la vez del numerador y del denominador, con lo que el tiempo de ejecución sería de O(n³). Una mejora a este método sería mirar sólo los números primos entre 2 y el denominador, con lo que habría que generar una tabla con los números primos menores que N. Como el número de primos menores que N es casi proporcional a N (más o menos una décima parte), el tiempo de ejecución sigue siendo de O(n³).

2.- El método utilizado para resolver el problema tiene tiempo casi constante. El método se basa en que una fracción es irreducible si el numerador y el denominador son primos entre sí, esto es, el máximo común divisor (MCD) del numerador y el denominador es 1. Ahora, para hallar el MCD de dos números se puede utilizar el algoritmo de Euclides, que se basa en que si:
     a = b*q + r , donde q = floor(a/b), y r = a mod b = a%b
entonces:
     MCD(a,b) = MCD(b,r)
Tanto b como r son más pequeños que a, con lo que tendríamos el mismo problema con dos números más pequeños. Si se aplica este método sucesivamente:
     a = b*q₁ + r₁
     b = r₁*q₂ + r₂
     r₁ = r₂*q₃ + r₃
     r₂ = r₃*q₄ + r₄
     ...
     r_n-2 = r_n-1*q_n + r_n
     r_n-1 = r_n*q_n+1 + 0
llega un momento en el que la división es exacta. Al llegar a ese instante, se sabe que:
     MCD(r_n-1,r_n) = r_n
pero como:
     MCD(r_n-1,r_n) = MCD(r_n-2,r_n-1)
aplicando esto sucesivamente se tiene que:
     r_n = MCD(r_n-1,r_n) = MCD(r_n-2,r_n-1) = MCD(r_n-3,r_n-2) = ... = MCD(r₂,r₃) = MCD(r₁,r₂) = MCD(b,r₁) = MCD(a,b)
esto es,
     r_n = MCD(a,b)
Por ejemplo, para hallar el MCD de 75 y 20, los pasos a dar serían:
     75 = 20*3 + 15
     20 = 15*1 + 5
     15 = 5*3 + 0
por lo que MCD(75,20) = 20.
Este método para hallar el MCD de dos número utiliza un número de iteraciones muy pequeño, casi despreciable frente a n, por lo que el tiempo de ejecución utilizando este método sería de O(n²).

Lo único que queda hacer es ordenar las fracciones. Para ello utilizamos la función qsort implementada ya en C (en stdlib.h), que tiene un tiempo de ejecución de O(n*log(n)), despreciable frente al tiempo de ejecución del programa entero. Sólo queda crear la función de comparación, último argumento de la función qsort. Para ello se puede utilizar el valor con decimales de la función, pero si no se quiere utilizar números reales basta con fijarse en que:

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

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

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

con lo que la función sólo tendría que devolver el número a*d - c*b. La función de comparación:

int compar(const void *A,const void *B)

del qsort tiene que devolver un valor menor que 0 si AB, y 0 si A=B.

Temas relacionados

Algoritmos de ordenación

Código

Código fuente en C

Código fuente en Pascal