Fracciones sin redondear

22

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 ndenota 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 ndígitos (lo que significa n-1dí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 foro whileo gotoetc., así como bucles funcionales como mapo foldque 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
falla
fuente
1
Pero en los lenguajes funcionales no existe un bucle. Un ejemplo de enemigo en Haskell repeatcrea 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.
orgulloso Haskeller
3
No me gusta la definición actual de "bucle". En Python, por ejemplo, for n in numbers: f(g(n))es equivalente a map(f, map(g, numbers)). La versión funcional usa mapdos veces, ¿debería eso realmente no permitirse?
flornquake
1
@ MartinBüttner Hablé sobre el caso de que los lenguajes funcionales no se permitirían debido a la ambigüedad
orgulloso Haskeller el
1
Lamento no poder contribuir realmente a esa discusión ya que mi conocimiento sobre programación funcional es básicamente cero. Si tiene una solución de la que no está seguro de si cumple con las 'reglas', ¡envíela de todos modos! ¡Al final se supone que es un desafío divertido y educativo!
flawr
2
@Dennis No, esa fue una redacción desafortunada, puede enviarla en la forma que desee, la idea principal detrás de ese párrafo era que no debería tener una desventaja si su idioma toma más bytes para 'leer' el número de entrada.
falla

Respuestas:

4

CJam, 41 40 36 bytes

Q'./1=,:L0\{;)_Qd*mo_d2$/LmOQd-}g'/@

Asume 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

$ for d in 1.7 0. 0.001 3.1416; do cjam <(echo "\"$d\":Q;
> Q'./1=,:L0\{;)_Qd*mo_d2$/LmOQd-}g'/@
> "); echo; done
5/3
0/1
1/667
355/113

Cómo funciona

Q'./1=,:L  " Count the number of characters after the dot and store it in L.     ";
0\         " Push 0 (denominator) and swap it with L (dummy value).              ";
{          "                                                                     ";
  ;        " Discard the topmost item from the stack (numerator or dummy value). ";
  )        " Increment the denominator.                                          ";
  _Qd*mo   " Multiply a copy by Double(Q) and round.                             ";
  _d2$/    " Cast a copy to Double and it divide it by the denominator.          ";
  LmO      " Round to L digits.                                                  ";
  Qd       " If the result is not Double(Q),                                     ";
}g         " repeat the loop.                                                    ";
./@        " Push a slash and rotate the denominator on top of it.               ";
Dennis
fuente
15

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 @

WITH e AS(SELECT *FROM(VALUES(1),(2),(3),(4),(5),(6),(7),(8),(9),(0))n(n)),t AS(SELECT ROW_NUMBER()OVER(ORDER BY(SELECT \))N FROM e a,e b,e c,e d)SELECT TOP 1concat(n.n,'/',d.n)FROM t d,t n WHERE round(n.n/(d.n+.0),len(parsename(@,1)))=@ ORDER BY d.n,n.n

Un desglose de la consulta.

WITH                                      -- Start CTE(Common Table Expression)
 e AS(                                    --Create a set of 10 rows
   SELECT *
   FROM(VALUES(1),(2),(3),(4),(5),(6),(7),(8),(9),(0))n(n)
 ),
 t AS(                                    
   SELECT ROW_NUMBER()OVER(ORDER BY(SELECT \))N 
   FROM e a,e b,e c,e d                   --Cross join e to produce 1000 numbered rows
 )
SELECT 
  TOP 1                                   --Grab first result
  concat(n.n,'/',d.n)                     --Build output
FROM t d,t n                              --Cross join t against itself for denominator and numerator
WHERE round(
  n.n/(d.n+.0),                           --Force float division with +.0
  len(parsename(@,1))                     --Get rounding length
  )=@                                     --Filter where the rounded result = input
ORDER BY d.n,n.n                          --Order by denominator then numerator
MickyT
fuente
+1. Me encanta. Lo puse 3.14159y me dio debidamente355/113
Tom Chantler
1
¡¡¡+1 nunca esperé ver un lenguaje SQL aquí !!!
flawr
@TomChantler Sospecho que te refieres eventualmente :)
MickyT
@flawr Para ser honesto, no pensé que iba a funcionar ... aunque el método de fuerza muy bruta.
MickyT
12

Haskell, 62 59

si tan solo los nombres no fueran tan largos ...

import Data.Ratio
f s=approxRational(read s)$50/10^length s

Esta es una función que devuelve un Rationalvalor.

explicación: la función approxRationales 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 approxRationalfunció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:

*Main> map f ["1.7", "0.001", "3.1416"]
[5 % 3,1 % 667,355 % 113]

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 reemplazando read spor read$s++"0".

orgulloso Haskeller
fuente
Es una función interesante tener. Por lo general, tales funciones existen con el propósito de encontrar la mejor aproximación racional a un número en la menor cantidad de pasos, lo que se puede lograr usando representaciones de fracción continua truncadas. Alternativamente, encontrar una fracción con el mínimo denominador es más una curiosidad académica. Normalmente no se esperaría encontrarlo como una función de biblioteca estándar.
COTO
44
@COTO Bueno, este es Haskell, está lleno de investigación académica.
orgulloso Haskeller
7

Ruby, 127125 bytes

f=->n{b=q=r=(m=n.sub(?.,'').to_r)/d=10**p=n.count('0-9')-1
b=r if(r=(q*d-=1).round.to_r/d).round(p).to_f.to_s==n while d>1
b}

Define una función fque devuelve el resultado como a Rational. Por ejemplo, si agrega este código

p f["1.7"]
p f["0."]
p f["0.001"]
p f["3.1416"]

Usted obtiene

(5/3)
(0/1)
(1/667)
(355/113)

El ciclo está sobre los denominadores. Estoy comenzando con la fracción completa, por ejemplo, 31416/10000para 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.

Martin Ender
fuente
4

Mathematica, 49 53 caracteres

Rationalize[ToExpression@#,5 10^(1-StringLength@#)]&@

Uso:

Rationalize[ToExpression@#,5 10^(1-StringLength@#)]&@"1.7"

Salida:

5/3

Casos de prueba:

input: 1.7     output: 5/3
input: 0.      output: 0
input: 0.001   output: 1/999
input: 3.1416  output: 355/113

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.

Cuenta
fuente
2
jaja utilicé exactamente la misma solución. Lástima que en Haskell sea más largo. por cierto, no parece que su solución tome una cadena como entrada como lo requiere la especificación.
orgulloso Haskeller
Espera, ¿la entrada fue una cadena? Dang, eso significa que puedo sacar algunas cosas del código.
Tally
Su salida para 0.001no coincide con el OP porque Rationalizeno 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.
COTO
@COTO De acuerdo con los documentos que no minimizar el denominador sin embargo.
Martin Ender
@ MartinBüttner: Es interesante que salga a la luz 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. : P
COTO
4

Python 2.7+, 111 caracteres

Prueba de que puedes escribir código horrible en cualquier idioma:

def f(s):
 t,e,y=float(s),50*10**-len(s),1;n=d=x=0
 while x|y:n,d=n+x,d+y;a=1.*n/d;x,y=a<t-e,a>t+e
 return n,d

Salida

>>> [f(s) for s in ("1.7", "0.", "0.001", "3.1416")]
[(5, 3), (0, 1), (1, 667), (355, 113)]
Steve
fuente
3

APL, 50

2↑⍎⍕(⍎x←⍞){50>|(10*⍴x)×⍺-⍵÷⍨n←⌊.5+⍺×⍵:n ⍵⋄''}¨⍳1e5

Mientras no cuentes evaly toStringcomo bucles

Explicació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, asigne xy evalúe
⍳1e5Genere 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 a n
⍺-⍵÷⍨Dividir por argumento de la derecha, entonces restar de argumento izquierdo
(10*⍴x)×Multiplicar por 10 a la potencia de la "longitud de x"
|Tomar valor absoluto
50>Comprobar si menos de 50 (longitud de xes 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 de ny el argumento correcto, de lo contrario devuelve una cadena vacía.

⍎⍕ toStringy luego evalpara obtener una matriz de todos los números en la matriz
2↑Seleccione solo los 2 primeros elementos, que es el primer par numerador-denominador encontrado

TwiNight
fuente
2

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.

?dXAr^d2*sf*sq1sd0[ld1+sd]sD[r1+r]sN[dlf*ld/1+2/dlq>Ndlq<Dlq!=m]dsmxpldp

Salida:

$ for n in 1.7 0. 0.001 3.1416; do echo "    n = $n:"; dc unround.dc <<< $n; done
    n = 1.7:
5
3
    n = 0.:
0
1
    n = 0.001:
1
667
    n = 3.1416:
355
113
$ 

Uf. Explicación parcial en esta respuesta .

Trauma digital
fuente
2

Mathematica, 111 caracteres

f=Module[{a=0,b=1,k},While[Round[a/b,10^-(StringLength[#]-2)]!=(k=ToExpression)@#,If[N[a/b]>k@#,b++,a++]];a/b]&

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

f/@{"1.7","0.0","0.001","3.1416","3.14"}
{5/3, 0, 1/667, 355/113, 22/7}

¿Alguien aquí celebra el Día de Aproximación Pi ?

krs013
fuente
No, solo estoy celebrando el día de aproximación tau. = P Pero acabo de notar que | 355/113 - pi | <10 ^ -6 =)
error
2

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 schooly no pude resistirme a usarla, a pesar de la evidente falta de competitividad de Applescript para el golf:

on u(q)
    set n to 0
    set d to 1
    set x to 0
    set AppleScript's text item delimiters to "."
    set f to 10 ^ (q's text item 2's length)
    repeat until x = q as real
        set x to (round n * f / d rounding as taught in school) / f
        if x < q then set n to n + 1
        if x > q then set d to d + 1
    end repeat
    return {n, d}
end u

log my u("1.7")
log my u("0.")
log my u("0.001")
log my u("3.1416")

Esto se puede jugar un poco más, pero probablemente no valga la pena.

Salida:

(*5, 3*)
(*0, 1*)
(*1, 667*)
(*355, 113*)
Trauma digital
fuente
2

BC, 151148 bytes

Editar - versión más rápida y más corta

define f(v){s=scale(x=v);for(i=r=1;i<=10^s;i+=1){t=v*i+1/2;scale=0;p=t/=1;scale=s+1;t=t/i+10^-s/2;scale=s;t=t/1-v;if((t*=-1^(t<0))<r){r=t;n=p;d=i}}}

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:

define f(v)
{
    s= scale(x=v)
    for( i=r=1; i <= 10^s; i+=1 ){
        t= v * i +1/2
        scale=0
        m=t/=1 # this rounded multiple becomes nominator if
               # backward quotient is first closest to an integer
        scale=s+1
        t= t / i +10^-s/2 # divide multiple back by denominator, start rounding again...
        scale=s
        t= t/1 - v # ...rounding done. Signed residue of backward quotient
        if( (t*= -1^(t < 0)) < r ){
            r=t
            n=m
            d=i
        }
    }
}

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.

define f(v){s=scale(v);j=0;for(i=r=1;j<=v*10^s;){scale=s+1;t=j/i+10^-s/2;scale=s;t=t/1-v;if((t*=-1^(t<0))<r){r=t;n=j;d=i};if((i+=1)>10^s){i=1;j+=1}};v}

caso de prueba:

define o(){ print "Input ",x,"\tOutput ",n,"/",d,"\n" }
f(1.7); o()
> 0
> Input 1.7       Output 5/3
> 0
f(0.); o()
> 0
> Input 0 Output 0/1
> 0
f(0.001); o()
> 0
> Input .001      Output 1/667
> 0
f(3.1416); o()
> 0
> Input 3.1416    Output 355/113
> 0

Y aquí está desenredado:

define f(v)
{
    s=scale(x=v) # save in global for later print
    j=0
    # do a full sequential hill-climb over the residues r of v and all possible
    # fractions n / d with fractional_decimals(v) == s precision.
    for( i=r=1; j <= v * 10^s; ){
        scale=s+1
        t= j / i +10^-s/2 # start rounding...
        scale=s
        t= t/1 - v # ...rounding done. New residue, but still signed
        if( (t*= -1^(t < 0)) < r ){ # absolute residue better?
            # climb hill
            r=t
            n=j
            d=i
        }
        if( (i+=1) > 10^s ){ # next inner step. End?
            # next outer step
            i=1
            j+=1
        }
    }
    v
}

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.

Franki
fuente
1
probablemente deberías mover la nueva versión al frente de la publicación
orgulloso haskeller
@proudhaskeller hecho
Franki
1

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):

void r(char* x, int* a, int* b) {
    int i = -1;
    char z[32];
    double v =atof(x);
    while(1) {
        i++;
        double y = ((double)i)/((double)(*b));
        double w;
        sprintf(z, "%.*f", strlen(strchr(x,'.'))-1, y);
        if(strcmp(x, z)==0) {
            *a = i;
            return;
        }
        w = atof(z);
        if(w > v) {
            (*b)++;
            r(x, a, b);
            return;
        }
    }
}

Uso:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main(int argc, char* argv[]) {
    int num;
    int denom = 1; // start with a denominator of 1
    r(argv[1], &num, &denom);
    printf("%d/%d\n", num, denom);
    return 0;
}

Código de golf:

typedef double D;
void r(char*x,int*a,int*b){int i=-1;char z[32];D v=atof(x);while(1){i++;D y=((D)i)/((D)(*b));D w;sprintf(z,"%.*f",strlen(strchr(x,'.'))-1,y);if(!strcmp(x,z)){*a=i;return;}w=atof(z);if(w>v){(*b)++;r(x,a,b);return;}}}
RT
fuente
en realidad, en la implementación de la biblioteca Haskell ( hackage.haskell.org/package/base-4.7.0.1/docs/src/… ), la definición de approxRationaltiene solo una función auxiliar recursiva, y no más bucles que eso.
orgulloso Haskeller
bueno, estaba equivocado, en realidad tiene dos funciones de ayuda recursivas, pero según las especificaciones está bien
orgulloso Haskeller
No estaba tratando de decir que las soluciones de nadie eran inválidas, solo quería publicar una sin racionalización integrada :)
RT
por supuesto, pero el hecho de que la definición en sí no tenga bucles es agradable, y de hecho, usted escribió en su publicación "por lo que sabemos, las funciones internas de racionalización () de los lenguajes modernos tienen muchos bucles internos". así que lo revisé
orgulloso Haskeller
de todos modos, ¿cómo funciona la solución?
orgulloso Haskeller
1

Pure Bash, 92 bytes

Como explicación parcial de esta respuesta , aquí se transfiere a bash:

f=${1#*.}
q=${1//.}
for((n=0,d=1;x-q;x=2*10**${#f}*n/d+1>>1,n+=x<q,d+=x>q));{ :;}
echo $n/$d

Notablemente:

  • bash tiene aritmética de enteros. Así que escalamos todo apropiadamente en 2 * 10 ^ (número de dígitos fraccionarios).
  • bash redondea hacia abajo al entero más cercano; el 2 en la expresión anterior es para que podamos redondear al entero más cercano ( arriba o abajo ).
  • Solo un bucle
  • comprobamos si el racional sobrepasa o subestima el decimal e incrementamos el denominador o numerador en consecuencia.

Salida:

$ for n in 1.7 0. 0.001 3.1416; do echo "    n = $n:"; ./unround.sh $n; done
    n = 1.7:
5/3
    n = 0.:
0/1
    n = 0.001:
1/667
    n = 3.1416:
355/113
$ 
Trauma digital
fuente
Debería ser un intpuerto bastante sencillo, solo para c
Digital Trauma
1

JavaScript (E6) 85

F=r=>(l=>{for(n=r,d=1;l&&r!=((n=r*d+1/2|0)/d).toFixed(l);d++);})(r.length-2)||[n|0,d]

Sin golf

F=r=>{
  l = r.length-2; // decimal digits
  if (l==0) return [r|0, 1] // if no decimal return the same (conv to number) with denominator 1

  // loop for increasing denominator 
  for(d = 2; 
      r != ( // loop until find an equal result
      // given R=N/D ==> N=R*D
      (n=r*d+1/2|0) // find possible numerator, rounding (+0.5 and trunc)
      /d).toFixed(l); // calc result to given decimals
      d++);
  return [n,d]
}

Prueba en la consola FireFox / FireBug

;["1.7","0.","0.001","3.1416","9.9999"].forEach(v => console.log(v,F(v)))

Salida

1.7 [5, 3]
0. [0, 1]
0.001 [1, 667]
3.1416 [355, 113]
9.9999 [66669, 6667]
edc65
fuente