Es mejor usar un ejemplo para describir el problema. Digamos que tengo un valor decimal 100.227273.Dado un número decimal, encuentre el multiplicador de enteros más pequeño que dé un resultado entero
100.227273 * X = Y
Necesito encontrar el más pequeño número entero X positivo que da número entero Y.
Si el 100.227273 es solo una aproximación y desea obtener la mejor aproximación racional, use continued fractions.
Tome 100.227273 como ejemplo.
para que pueda obtener
1
100.227273 = 100 + —————————
1
4 + —————
1
2 + —
2
simplificar esta expresión para obtener 2205/22.
+1 por tratar de ir más allá de lo que preguntó el interrogador, a lo que probablemente intentan hacer. –
+1 para fracciones continuas. IIRC hay un algoritmo simple que usa solo 3 variables de estado para ir arbitrariamente profundo. – phkahler
1000000/gcd(1000000,227273). También conocido como lcm(1000000,227273)/227273. En este caso, 1 millón.
Lo que quiere hacer es convertir 0.227273 en una fracción en su mínima expresión. El número que estás buscando es el denominador de esa fracción. Como el 227273/1000000 ya está en su forma más simple, listo. Pero si su entrada fue 100.075, entonces 75/1000 no está en la forma más simple. La forma más simple es 3/40, por lo que la solución para X es 40.
Como una optimización, se puede simplificar el cálculo, porque usted sabe que el denominador de partida es una potencia de 10, por lo que sus únicos factores primos son 2 y 5. Entonces, todo lo que necesita buscar en el numerador es la divisibilidad entre 2 y 5, que es más fácil que el algoritmo de Euclides. Por supuesto, si ya tienes una implementación de gcd y/o lcm, entonces esto es más esfuerzo de tu parte, no menos.
Tenga en cuenta cuando obtenga el resultado, que los números de coma flotante no pueden en general representar fracciones decimales con precisión. Así que una vez que tenga la respuesta matemáticamente correcta, no será necesariamente le dará una respuesta entera cuando realice una multiplicación de coma flotante. La otra cara de esto es que, por supuesto, la pregunta solo se aplica si hay una expresión decimal finita del número que le interesa.
Si tiene el número como cociente en primer lugar, entonces necesita encuentra el denominador de su forma más simple directamente, no convirtiéndola a decimal y truncándola. Por ejemplo, para resolver este problema para el número "6 y un tercio", la respuesta es 3, no cualquier potencia de 10. Si la entrada es "la raíz cuadrada de 2", entonces no hay solución para X.
Bueno, en realidad, el entero X pequeño con la característica que necesita es 0, pero supongo que no quieres decir que ;-)
y OP significa entero positivo. –
Por supuesto. Dar la respuesta "correcta pero incorrecta" es solo mi pequeña forma de señalar la imprecisión en la pregunta. –
No, -10,000,000,000 es mucho más pequeño que 0.;) – kennytm
Si su valor decimal positivo D tiene n dígitos a la derecha del punto decimal , entonces D * 10^n es un número entero y X = 10^n/gcf (10^n, D * 10^n) = lcm (10^n, D * 10^n) es el entero positivo más pequeño X.
Excepto que parece que no sabe cuántos dígitos dura la parte fraccionaria de antemano. –
Supongo que la entrada decimal r es un número racional positivo r con una representación decimal de terminación.
Sea d el número de dígitos después del punto decimal (supongamos que hemos recortado todos los ceros superfluos de la representación decimal de r). A continuación, tenga en cuenta que 10^d * r es un número entero m. Deje g = gcd(10^d, m). Entonces 10^d/g * r = m/g es un número entero p. Deje q = 10^d/g. Reclamo que q es el número entero positivo más pequeño.
Tengo la sensación de que en realidad quiere decir esto:
How to convert floats to human-readable fractions?
Después de un examen creo que esto es exactamente lo que usaré :) – Davorin
¿Realmente quiere decir decimal o de coma flotante? –
La representación no importa, al menos no para mí. – Davorin