Cuando convierte una fracción a un número decimal y desea almacenar ese número, a menudo tiene que redondearlo, porque solo desea usar una cierta cantidad de memoria. Digamos que solo puede almacenar 5 dígitos decimales, luego 5/3 se convierte en 1.6667. Si puede almacenar solo 2 dígitos decimales, será 1.7 (ahora suponiendo que siempre esté entre 0 y 9.99 ...).
Si ahora intenta revertir ese proceso con 1.7 y desea recuperar su fracción, eso puede ser difícil, ya que sabe que 1.7 es solo un número redondeado. Por supuesto, puedes probar 17/10, pero eso es más bien una fracción "fea" en comparación con el "elegante" 5/3.
Entonces, el objetivo ahora es encontrar la fracción a / b con el mínimo denominador b, que da como resultado el número decimal redondeado cuando se redondea correctamente.
Detalles
La entrada contiene una cadena con un número de 1 a 5 dígitos que está entre 0 (incluido) y 10 (no incluido) con un '.' después del primer dígito. Digamos que n
denota el número de dígitos. La salida debe ser una lista / matriz de dos enteros [numerator, denominator]
o un tipo de datos racional (puede crear el suyo propio o usarlo incorporado) donde el numerador no es negativo y el denominador es positivo. El numerador / denominador de fracción debe ser igual a la entrada cuando se redondea correctamente a n
dígitos (lo que significa n-1
dígitos después del punto decimal).
Restricción: solo se permite una declaración de bucle. Esto significa que puede usar solo una sola declaración de bucle (como for
o while
o goto
etc., así como bucles funcionales como map
o fold
que aplican código a cada elemento de una lista / matriz) en todo su código, pero puede 'abusar' de ella o usar la recursividad, etc.
Deberías escribir una función. Si su idioma no tiene funciones (o incluso si las tiene), puede suponer alternativamente que la entrada se almacena en una variable (o entrada a través de stdin) e imprimir el resultado o escribirlo en un archivo. El menor número de bytes gana.
Redondeo
El redondeo debe seguir las reglas de redondeo 'convencionales', es decir, si el último dígito que se cortará es 5 o mayor, redondeará hacia arriba y redondeará hacia abajo para cualquier otro caso, por ejemplo:
4.5494 resultará al redondear a
- 1 dígito: 5
- 2 dígitos: 4.5
- 3 dígitos: 4.55
- 4 dígitos: 4.549
Ejemplos
Incluya los siguientes casos de prueba y otros 'interesantes':
Input 1.7 Output 5/3
Input 0. Output 0/1
Input 0.001 Output 1/667
Input 3.1416 Output 355/113
repeat
crea una lista infinita de su argumento. Parece que se repite pero en realidad tiene una complejidad de tiempo de O (1). Pero supongo que ordenar cada caso individualmente es mejor que no permitir lenguajes funcionales.for n in numbers: f(g(n))
es equivalente amap(f, map(g, numbers))
. La versión funcional usamap
dos veces, ¿debería eso realmente no permitirse?Respuestas:
CJam,
414036 bytesAsume que la cadena de entrada se almacena en Q, lo cual está explícitamente permitido por la pregunta. Pruébalo en línea.
Casos de prueba
Cómo funciona
fuente
T-SQL 254
Si bien T-SQL no es realmente adecuado para este tipo de cosas, fue divertido intentarlo. El rendimiento se vuelve realmente malo cuanto mayor sea el denominador. Se limita a un denominador de 1000.
La entrada es una variable flotante @
Un desglose de la consulta.
fuente
3.14159
y me dio debidamente355/113
Haskell,
6259si tan solo los nombres no fueran tan largos ...
Esta es una función que devuelve un
Rational
valor.explicación: la función
approxRational
es una función que toma un número flotante y un épsilon flotante y devuelve el racional más simple que está en la distancia épsilon de la entrada. básicamente, devuelve la aproximación más simple del flotador a una distancia racional en un "error perdonable".explotemos esta función para nuestro uso. para esto necesitaremos averiguar cuál es el área de los flotadores que se redondea al número dado. luego de ingresar esto en la
approxRational
función nos dará la respuesta.Probemos 1.7, por ejemplo. el flotador más bajo que se redondea a 1.7 es 1.65. cualquier menor no se redondeará a 1.7. de manera similar, el límite superior de los flotadores que se redondean a 1.7 es 1.75.
ambos límites son los límites son el número de entrada +/- 0.05. se puede demostrar fácilmente que esta distancia es siempre
5 * 10 ^ -(the length of the input - 1)
(el -1 es porque siempre hay un '.' en la entrada). desde aquí el código es bastante simple.Casos de prueba:
desafortunadamente no funciona en "0" porque la función del analizador de Haskell no reconoce un
.
al final de un flotante. Esto se puede arreglar para 5 bytes reemplazandoread s
porread$s++"0"
.fuente
Ruby,
127125bytesDefine una función
f
que devuelve el resultado como aRational
. Por ejemplo, si agrega este códigoUsted obtiene
El ciclo está sobre los denominadores. Estoy comenzando con la fracción completa, por ejemplo,
31416/10000
para el último ejemplo. Luego estoy decrementando el denominador, disminuyo proporcionalmente el numerador (y lo redondeo). Si el resultado racional se redondea al mismo número de entrada, recuerdo una nueva fracción mejor.fuente
Mathematica,
4953 caracteresUso:
Salida:
Casos de prueba:
El caso 0.001 me parece extraño; como la función racionalizar no funcionó de acuerdo con su descripción, cuando no encontró el caso 1/667. Debería generar el número con el denominador más pequeño que esté dentro de los límites especificados.
fuente
0.001
no coincide con el OP porqueRationalize
no está bajo la restricción de minimizar el denominador. Como mencioné al orgulloso Haskeller, una función de aproximación racional sujeta a minimizar el denominador es altamente esotérica (en resumen, porque es una forma pésima e ineficiente de aproximar números). Normalmente no esperaría que fuera una función de biblioteca estándar.1/999
. 999 se convierte en el denominador más bajo (aceptable) solo para un error entre aproximadamente 1e-6 y 2e-6. El error encuadernado es claramente 5e-4. Entonces, sea lo que sea que Mathematica esté haciendo en ese caso, definitivamente no está funcionando según las especificaciones. : PPython 2.7+, 111 caracteres
Prueba de que puedes escribir código horrible en cualquier idioma:
Salida
fuente
APL, 50
Mientras no cuentes
eval
ytoString
como buclesExplicación
El enfoque consiste en iterar de 1 a 10000 como denominador y calcular el numerador que más se aproxime al flotante, luego verificar si el error está dentro de los límites. Por último, seleccione el par más pequeño de todas las fracciones encontradas.
(⍎x←⍞)
Tome la entrada de cadena desde la pantalla, asignex
y evalúe⍳1e5
Genere una matriz de 1 a 10000{...}¨
Para cada elemento de la matriz, llame a la función con ella(⍎x←⍞)
y argumentos (bucle)⍺×⍵
Multiplicar los argumentos⌊.5+
de la Ronda off (mediante la adición de 0,5 a continuación, redondeo hacia abajo)n←
Asignar an
⍺-⍵÷⍨
Dividir por argumento de la derecha, entonces restar de argumento izquierdo(10*⍴x)×
Multiplicar por 10 a la potencia de la "longitud dex
"|
Tomar valor absoluto50>
Comprobar si menos de 50 (longitud dex
es 2 más que el no. de dp, así que use 50 aquí en lugar de 0.5):n ⍵⋄''
Si la verificación anterior devuelve verdadero, entonces devuelve la matriz den
y el argumento correcto, de lo contrario devuelve una cadena vacía.⍎⍕
toString
y luegoeval
para obtener una matriz de todos los números en la matriz2↑
Seleccione solo los 2 primeros elementos, que es el primer par numerador-denominador encontradofuente
GNU dc, 72 bytes
Sin bucles: dc ni siquiera los tiene. En cambio, el control proviene de una sola macro recursiva de cola, idiomática para DC.
Salida:
Uf. Explicación parcial en esta respuesta .
fuente
Mathematica, 111 caracteres
Realmente bastante simple, y no creo que converja en ningún lado tan rápido como las otras soluciones, ya que el numerador y el denominador solo se incrementan en uno. Sobre todo quería encontrar la solución simple a esto. Tendré que ver las otras respuestas y ver qué cosas inteligentes suceden allí.
Salida
¿Alguien aquí celebra el Día de Aproximación Pi ?
fuente
Applescript,> 300 bytes
Quería hacer esto en un lenguaje que nativamente realiza el tipo de redondeo requerido. Resulta que Applescript encaja perfectamente. Luego vi la enumeración
rounding as taught in school
y no pude resistirme a usarla, a pesar de la evidente falta de competitividad de Applescript para el golf:Esto se puede jugar un poco más, pero probablemente no valga la pena.
Salida:
fuente
BC,
151148bytesEditar - versión más rápida y más corta
mismo caso de prueba
Mucho es similar a la versión anterior, pero en lugar de probar todas las combinaciones n / d posibles, subimos los residuos de v y cocientes hacia atrás de múltiplos m == v * d y denominadores d. Nuevamente, la precisión del cálculo es la misma.
Aquí está desenredado:
Esta versión realmente tiene un simple bucle y solo realiza operaciones aritméticas de $ \ Theta \ left (\ operatorname {fraccional_decimales} (v) \ right) $.
Original - versión lenta
Esta función calcula el nominador más pequeño n y el denominador d de modo que la fracción n / d redondeada a dígitos fraccionales_decimales (v) es igual a un valor decimal dado v.
caso de prueba:
Y aquí está desenredado:
Admito que hice un poco de trampa al emular un segundo bucle interno dentro de un solo bucle externo, pero sin usar ninguna otra declaración de bucle. Y es por eso que en realidad hace $ \ Theta \ left (v \ operatorname {fraccional_decimales} (v) ^ 2 \ derecha) $ operaciones aritméticas.
fuente
C, 233
Esto funciona llamando a una función de racionalización r () con un denominador inicial de 1. La función comienza a incrementar un numerador y verifica en cada incremento si el número resultante, cuando se redondea al mismo número de dígitos que el original, tiene la misma cadena representación como el original. Una vez que el numerador se ha incrementado tanto que el resultado es mayor que el original, la función incrementa el denominador y se llama a sí mismo.
Por supuesto, esto usa mucho más código, pero creo que el espíritu del problema exonera este enfoque básico; Por lo que sabemos, las funciones internas de racionalizar () de los lenguajes modernos tienen muchos bucles internos.
Tenga en cuenta que esto no funciona para una entrada de "0". porque esa no es una forma estándar de escribir un flotante, de modo que cuando reescribe el flotante en una cadena, el resultado nunca será un "0".
Las especificaciones quieren una función que devuelva valores en lugar de simplemente imprimir en la pantalla, de ahí el paso de argumentos.
Código (sin golf):
Uso:
Código de golf:
fuente
approxRational
tiene solo una función auxiliar recursiva, y no más bucles que eso.Pure Bash, 92 bytes
Como explicación parcial de esta respuesta , aquí se transfiere a bash:
Notablemente:
Salida:
fuente
int
puerto bastante sencillo, solo para cJavaScript (E6) 85
Sin golf
Prueba en la consola FireFox / FireBug
Salida
fuente