2010-11-26 33 views
5

Este es un problema de tarea. Dada la clase "Racional" con dos campos enteros, numerador y denominador, escriba una función para comparar dos instancias "Racionales". Deje r1 = a/b y r2 = c/d. La solución trivial es comparar a*d y b*c. ¿Podemos hacerlo mejor?¿Cómo comparar números racionales?

+5

¿Cuál es la definición de "mejor"? Me parece bastante óptimo. –

Respuesta

3

Por lo general, el costo de una rama es más que el costo de una multiplicación, por lo que no vale la pena tratar de ser inteligente aparte de eso. Si por enteros quieres decir int32, entonces promueve a int64 para realizar la multiplicación; si te refieres a enteros más grandes, entonces necesitas administrar la multiplicación usando los mecanismos habituales, en cuyo punto las suposiciones sobre las ramas pueden ser invalidadas.

+0

-2 (a * d) es igual a -2 (b * c). –

4

En el caso general, no. Si espera hacer muchas comparaciones, un paso de procesamiento preliminar podría ocuparse de normalizar todo (dividiendo el numerador y el denominador por su gcd, y haciendo que el denominador sea positivo), de modo que las comparaciones de igualdad compararían a = c y b = d, pero calcular a * d = b * c ciertamente no es prohibitivo por ningún medio.

1

No me gusta a*d b*c solución porque puede provocar un desbordamiento de número entero innecesario si algunos de los numeradores y denominadores son grandes. Aunque no tengo una mejor solución.

0

Si está utilizando Java, puede utilizar la clase java.math.BigInteger en caso de que se produzca un desbordamiento; de lo contrario, puede implementar sus propios arreglos de bytes.

4

Si desea la solución sofisticada, convierta cada una de las dos fracciones en una fracción continua (utilizando una variante del algoritmo GCD). Este algoritmo simple genera un número entero a la vez. Compara cada par de enteros de las dos fracciones continuas parciales. Si son diferentes, salga. De lo contrario, genere el siguiente par y continúe mientras haya más. Para racionales, la secuencia es finita, por lo que terminará pronto. Creo que este es el mejor método cuando a, b, c, d son grandes.

Se ha demostrado que las continuas expansiones de fracciones para todas las raíces cuadradas irracionales son recurrentes. De modo que puede usar esto también para comparar esos elementos irracionales, incluso si sus representaciones binarias de computadora le darían un resultado incorrecto (debido a un truncamiento). Eso significa que tan pronto como detecte la repetición en el patrón, puede terminar, probando la igualdad de los dos irracionales.

2

Desde mi punto de vista, la solución trivial es incorrecto en caso de que existan números negativos permitidos:

¿Qué hay de r1=1/3 y b=1/(-3) que debería ser un tanto números racionales correctas. y, por supuesto matemáticamente se cumple que: 1/(- 3) < 1/3

Sin embargo, los rendimientos de soluciones propuestas 1*3 > 1*(-3) lo que conduce a la solución incorrecta que 1/3 < 1/(-3).

Me encontré con ese problema durante mi curso de Scala :-) Todavía no tengo una buena solución para eso.

Tal vez, como tan a menudo ayuda a mirar hacia el BOOST-Biblioteca: Allí se dice:

La operación de comparación-con-racional hace dos operaciones de tamaño doble GCD, dos adiciones y disminuciones adicionales, y tres comparaciones en el peor de los casos.(Las operaciones GCD son de tamaño doble, ya que se realizan en poco sistemática y los cocientes provisionales se retienen y se comparan, mientras que una función GCD directa sólo conserva y compara los residuos.)

http://www.boost.org/doc/libs/1_55_0/libs/rational/rational.html

Hasta ahora no tuve la oportunidad de investigar ese código.

Cheers, Felix

Mientras tanto yo tuvimos un vistazo en el código Boost y se hace lo mismo como Liberio describe en su respuesta anterior. https://stackoverflow.com/a/4288890/2682209 Así que este es definitivamente el camino "correcto" (pero engorroso) a seguir.

Cuestiones relacionadas