Fracción más cercana

24

Tarea:

Su programa recibe una fracción simple positiva y adecuada en el formato .<numerator>/<denominator>

Para esta entrada, debe encontrar dos fracciones.

  1. Una fracción que es menor que la entrada.
  2. Una fracción que es mayor que la entrada.

Ambas fracciones deben tener un denominador más bajo que la entrada. De todas las fracciones posibles, deberían tener la menor diferencia con la entrada.

Salida:

La salida de su programa debe ser:

  • Una fracción que es más pequeña que la entrada, en el formato <numerator>/<denominator>.
  • Seguido de un carácter de espacio (código ASCII 32).
  • Seguido de una fracción que es mayor que la entrada, en el formato <numerator>/<denominator>.

Como sigue:

«fraction that is < input» «fraction that is > input»

Reglas:

  • Todas las fracciones producidas deben estar en los términos más bajos .
  • Todas las fracciones producidas deben ser fracciones apropiadas.
  • Si no hay posibles fracciones apropiadas permitidas por las reglas, debe generar 0una entrada en lugar de una fracción <entrada, y en 1lugar de una fracción> entrada.
  • Puede elegir si desea recibir la fracción como un argumento de línea de comandos (por ejemplo yourprogram.exe 2/5) o solicitar la entrada del usuario.
  • Puede suponer que su programa no recibirá entradas no válidas.
  • El código más corto (en bytes, en cualquier idioma) gana.
  • Cualquier argumento de línea de comandos no estándar (argumentos que normalmente no se requieren para ejecutar un script) cuentan para el recuento total de caracteres.

  • Lo que su programa no debe hacer:

    • Depende de cualquier recurso externo.
    • Depende de tener un nombre de archivo específico.
    • Salida de cualquier cosa que no sea la salida requerida.
    • Tardar excepcionalmente en correr. Si su programa dura más de un minuto para fracciones con un numerador y un denominador de 6 dígitos (por ejemplo 179565/987657) en la computadora de un usuario doméstico promedio, no es válido.
    • Fracciones de salida con 0como denominador. No puedes dividir por cero.
    • Fracciones de salida con 0el numerador. Su programa debe generar en 0lugar de una fracción.
    • Reducir una fracción ingresada. Si la fracción dada como entrada es reducible, debe usar la fracción tal como se ingresa.
  • Su programa no debe estar escrito en un lenguaje de programación para el que no existía un compilador / intérprete disponible públicamente antes de que se publicara este desafío.

Ejemplos:

Entrada: 2/5
Salida: 1/3 1/2

Entrada: 1/2
Salida: 0 1

Entrada: 5/9
Salida: 1/2 4/7

Entrada: 1/3
Salida: 0 1/2

Entrada: 2/4
Salida: 1/3 2/3

Entrada: 179565/987657
Salida: 170496/937775 128779/708320

usuario2428118
fuente
1
Su primer ejemplo no coincide con la especificación: ambas fracciones deben tener un denominador más bajo que la entrada.
Howard
1
Primer ejemplo, la salida debería ser 1/3 1/2.
Heiko Oberdiek
@HeikoOberdiek Tienes razón. Fijo.
user2428118
1
Definir "computadora de usuario doméstico promedio". ¿Son aceptables 90 segundos en una máquina Intel Atom de 1.6GHz?
John Dvorak
2
Tu último ejemplo es incorrecto. La fracción de entrada es igual a la primera de las fracciones de salida.
DavidC

Respuestas:

3

Sage - 119 117

x,X=map(int,raw_input().split('/'))
a=0
A=c=C=1
while C<X:exec("ab,,AB"[c*X>C*x::2]+"=c,C");c=a+b;C=A+B
print a/A,b/B

Sage solo se necesita en la última línea, que se encarga de la salida. Todo lo demás también funciona en Python.

Reemplace raw_input()con sys.argv[1]para que la entrada se lea desde un argumento de línea de comandos en lugar de una solicitud. Esto no cambia el recuento de caracteres. (No funciona en Python sin importar sysprimero).

Esto esencialmente construye recursivamente la secuencia de Farey respectiva utilizando mediantes de los elementos existentes, pero se limita a los elementos más cercanos a la entrada. Desde otro punto de vista, ejecuta una búsqueda de intervalo anidado en las respectivas secuencias de Farey.

Procesa correctamente todos los ejemplos en menos de un segundo en mi máquina.

Aquí hay una versión sin golf:

x,X = map(Integer,sys.argv[1].split('/'))
x = x/X
a = 0
c = b = 1
while c.denominator() < X:
    if c > x:
        b = c
    else:
        a = c
    c = ( a.numerator() + b.numerator() ) / ( a.denominator() + b.denominator() )
print a,b
Wrzlprmft
fuente
Ya tenía miedo de no recibir nuevas presentaciones para esta recompensa. Buen trabajo.
user2428118
Buen truco con el exec!
xnor
Como la única respuesta presentada dentro del período de recompensa, le otorgo la recompensa. Felicidades.
user2428118
Acabo de corregir un error en uno de los ejemplos. Es posible que desee corregir su envío (aunque ha pasado medio año desde que lo envió).
user2428118
12

Python 2.7 - 138

x,y=n,d=map(int,raw_input().split('/'))
while y:x,y=y,x%y
def f(p,a=d):
 while(a*n+p)%d:a-=1
 print`(a*n+p)/d`+('/'+`a`)*(a>1),
f(-x);f(x)

Comencé con la obvia solución de fuerza bruta, pero me di cuenta de que, dado que el OP quería poder resolver instancias con numeradores y denominadores de seis dígitos en menos de un minuto, necesito una solución mejor que probar un billón de posibilidades. Encontré una fórmula útil en la página de Wikipedia para la secuencia de Farey: si a / b, c / d son vecinos en una de las secuencias de Farey, con a/b<c/d, entonces b*c-a*b=1. El ciclo while dentro de f en mi programa extiende este hecho a números no reducidos, usando el mcd, que calcula el otro ciclo while.

Ya jugué bastante duro, pero me encantaría escuchar cualquier sugerencia.

Ediciones:

166-> 162: eliminado ay bdel programa externo. Eran innecesarios.
162-> 155: str()-> ``
155-> 154: Añadido k.
154-> 152: Eliminado xdesde el interior de la función, lo pasó como argumento
152-> 150: dio aun valor predeterminado en lugar de pasarlo como argumento.
150-> 146: Se modificó la inicialización de xy y.
146-> 145: eliminado k.
145-> 144: Cambiado ... y ... o ... a (..., ...) [...], ahorrando así un espacio.
144-> 138: Cambiado (..., ...) [...] a ... + ... * (...). Gracias a @ mbomb007.

Casos de prueba:

2/5
1/3 1/2

1/2
0 1

2/4
1/3 2/3

179565/987657
170496/937775 128779/708320

12345678/87654321
12174209/86436891 11145405/79132382

La penúltima prueba tardó menos de un segundo en mi computadora, mientras que la última tardó unos 5-10 segundos.

isaacg
fuente
Esto k=1es pura maldad.
Evpok
1
@Evpok: estaba tratando de hacer que k = y = n funcione, pero aparentemente si modifica una variable dentro de una función, python quiere que sea local. Esta era la única forma de obtener una variable local en 4 caracteres. Además, dado que la fracción es positiva y adecuada, el denominador no puede ser 1.
isaacg
Los argumentos de la línea de comandos son fáciles con Python, por lo que deberían haberse utilizado para la entrada como se indica aquí.
Alex Thornton
1
" Puede elegir si desea recibir la fracción como un argumento de línea de comandos (por ejemplo, yourprogram.exe 2/5) o solicitar la entrada del usuario ".
isaacg
Ahorre 6 caracteres:print`(a*n+p)/d`+('/'+`a`)*(a>1),
mbomb007
5

Mathematica, 163 bytes

{a,b}=FromDigits/@InputString[]~StringSplit~"/";r=Range[b-1];""<>Riffle[#~ToString~InputForm&/@(#@DeleteCases[#2[a/b*r]/r,a/b]&@@@{{Max,Floor},{Min,Ceiling}})," "]

Esto está severamente limitado por el requisito de entrada / salida como entrada y cadenas de usuario. Tratar con cuerdas es realmente engorroso en Mathematica (al menos cuando quieres jugar al golf). Haciendo esto de la manera natural en Mathematica, (usando solo enteros y racionales) probablemente lo reduciría al 50% del tamaño.

Puede hacer números de 6 dígitos en unos segundos en mi máquina.

Ligeramente más legible (aunque en realidad no es un golf):

{a, b} = FromDigits /@ InputString[]~StringSplit~"/";
r = Range[b - 1];
"" <> Riffle[#~ToString~
     InputForm & /@ (#[DeleteCases[#2[a/b*r]/r, a/b]] & @@@ {{Max, 
       Floor}, {Min, Ceiling}}), " "]

Por diversión, hacer esto "de forma natural", es decir, como una función que toma el numerador y el denominador y devuelve dos racionales, esto es solo 84 caracteres (por lo que mi estimación del 50% estaba bastante cerca):

f[a_,b_]:=#@DeleteCases[#2[a/b*(r=Range[b-1])]/r,a/b]&@@@{{Max,Floor},{Min,Ceiling}}
Martin Ender
fuente
3

Julia - 127125 bytes

He abordado esto desde una perspectiva matemática para evitar la necesidad de bucles, por lo que este código se ejecuta bastante rápido para entradas grandes (nota: si a / b es la entrada, entonces a * b debe caber dentro de Int64 (Int32 en sistemas de 32 bits) , de lo contrario, se generan respuestas sin sentido: si a y b son expresables en Int32 (Int16 en sistemas de 32 bits), no se producen problemas).

ACTUALIZACIÓN: Ya no es necesario sobrecargar la barra diagonal inversa para div, usando ÷, un ahorro neto de 2 bytes.

a,b=int(split(readline(),"/"));k=gcd(a,b);f=b-invmod(a÷k,b÷k);d=2b-f-b÷k;print(a*d÷b,d<2?" ":"/$d ",a*f÷b+1,"/$f"^(f>1))

Sin golf:

a,b=int(split(readline(),"/")) # Read in STDIN in form a/b, convert to int
k=gcd(a,b)           # Get the greatest common denominator
f=b-invmod(a÷k,b÷k)  # Calculate the denominator of the next biggest fraction
d=2b-f-b÷k           # Calculate the denominator of the next smallest fraction
print(a*d÷b,d<2?" ":"/$d ",a*f÷b+1,"/$f"^(f>1)) # Calculate numerators and print

Idea básica: encuentre la d y f más grande menor que b que satisfaga ad-bc = gcd (a, b) (siguiente más pequeña) y be-af = gcd (a, b) (siguiente más grande), luego calcule c y e a partir de allí. La salida resultante es c / de / f, a menos que d o f sea 1, en cuyo caso se omite / d o / f.

Curiosamente, esto significa que el código también funciona para fracciones impropias positivas, siempre que la entrada no sea un número entero (es decir, mcd (a, b) = a).

En mi sistema, ingresar 194857602/34512958303no requiere tiempo perceptible para generar171085289/30302433084 23772313/4210525219

Glen O
fuente
Prueba con 55552/999999me da -396/920632 486/936509.
user2428118
@ user2428118 - ¿Está en un sistema de 32 bits (o está utilizando una Julia de 32 bits)? He usado "int", lo que significa que en un sistema de 32 bits, usará Int32 en lugar de Int64. int32(55552*999999)da -282630400. Para mí, con esa prueba, obtengo 51143/920632 52025/936509: tenga en cuenta que los denominadores son los mismos y que 52025-51143 = 486 - (- 396). Agregaré una nota para mencionar este problema.
Glen O
Si desea asegurarse de que el código funcionará para todas las entradas de tamaño Int64, puede reemplazar "int" con "int128". Con ese cambio, ingresando 1234567891234567/2145768375829475878resultados en 869253326028691/1510825213275018197 365314565205876/634943162554457681. Este cambio agrega solo 3 caracteres adicionales.
Glen O
Sí, estoy usando una computadora de 32 bits. Lo intentaré en una máquina de 64 bits en algún momento cuando tenga tiempo para hacerlo.
user2428118
Las pruebas en una computadora de 64 bits dan el resultado correcto, por lo que acepto esta respuesta.
user2428118
2

JavaScript, 131

Con notación de flecha gruesa y evalllamadas:

m=>{for(e=eval,n=e(m),i=p=0,q=1;++i</\d+$/.exec(m);)if(n*i>(f=n*i|0))g=f+1,p=f/i>e(p)?f+'/'+i:p,q=g/i<e(q)?g+'/'+i:q;return p+' '+q}

La 179565/987657prueba de esfuerzo se ejecuta en aproximadamente 35 segundos en Firefox, mucho más en Chrome (~ 6 minutos)

Método más rápido y sin evalnotación de flecha gruesa

for(n=eval(m=prompt(a=i=p=0,b=c=d=q=1));++i<m.match(/\d+$/);)if(n*i>(f=n*i|0))g=f+1,p=f*c>i*a?(a=f)+'/'+(c=i):p,q=g*d<i*b?(b=g)+'/'+(d=i):q;alert(p+' '+q)

La 179565/987657prueba de esfuerzo se ejecuta en aproximadamente 5 segundos.

No golfizado:

m=prompt(); //get input
a=0; c=1; //first fraction
b=1; d=1; //second fraction
n=eval(m); //evaluate input
for (i=1; i<m.match(/\d+$/); i++) { //loop from 1 to input denominator
  f=Math.floor(n*i);
  if (n*i > f) { //if fraction not equal to simplification of input
    g=f+1; // f/i and g/i are fractions closer to input
    if (f/i>a/c) a=f, c=i;
    if (g/i<b/d) b=g; d=i; 
  }
}
alert(a+'/'+c+' '+b+'/'+d); //output values handling 0 and 1 correctly
Michael M.
fuente
también ... mucho ... eval. EEK
John Dvorak
3
Sin embargo, la prueba con 2/6da 1/3 2/5no 1/3es menor sino igual a 2/6 .
user2428118
@ user2428118 corregido
Michael M.
¿Por qué se ha aceptado esta respuesta tan temprano?
Evpok
1
@ user2428118: Sabes, puedes dejar pasar un par de días antes de aceptar soluciones. Además, esta solución ya no es la más corta.
isaacg
2

perl, 142 bytes (155 sin CPAN)

use bare A..Z;$/="/";N=<>;D=<>;F=N/D;K=G=1;for$H(1..D){J<F&&J>E?(E,I):J>F&&J<G?(G,K):()=(J=$_/H,"$_/$H")for(Z=int F*H)..Z+1}print I||0," $K\n"

O si los módulos CPAN no están permitidos / se necesita un código 3-4 veces más rápido:

$/="/";$N=<>;$D=<>;$F=$N/$D;$g=$G=1;for$d(1..$D){$f<$F&&$f>$E?($E,$e):$f>$F&&$f<$G?($G,$g):()=($f=$_/$d,"$_/$d")for($z=int$F*$d)..$z+1}print$e||0," $g\n"

La primera versión toma 9.55 segundos en mi máquina, la última versión 2.44 segundos.

Menos ilegible:

($N, $D) = split(m[/], <>);
$F = $N / $D;
$G = 1;
foreach $d (1 .. $D) {
    $z = int $F * $d;
    foreach $_ ($z .. $z + 1) {
        $f = $_ / $d;
        ($f < $F && $f > $E ? ($E, $e) :
        ($f > $F && $f < $G ? ($G, $g) : ())) = ($f, "$_/$d");
    }
}
print $e || 0, ' ', $g || 1, "\n";
skibrianski
fuente