Fracción a decimal exacto

23

Escriba un programa o función que tenga dos enteros a, b emite una cadena que contiene un número decimal que representa exactamente la fracción a / b .

Si a / b es entero, simplemente envíe el valor, sin un punto decimal o ceros a la izquierda:

123562375921304812375087183597 / 2777 -> 44494913907563850333124661
81 / 3 -> 27
-6 / 2 -> -3

Si a / b no es entero pero tiene una representación finita en la base 10, muestre el valor sin ceros iniciales o finales (excepto un cero simple antes del punto):

1 / 2 -> 0.5
3289323463 / -250000000 -> -13.157293852

Finalmente, si y solo si (entonces no 0.999...) a / b no es entero y no tiene una representación finita, envíe la parte finita seguida de la parte repetida entre paréntesis. La parte que se repite debe ser lo más pequeña posible y comenzar lo antes posible.

-1 / 3 -> -0.(3)
235 / 14 -> 16.7(857142)
123 / 321 -> 0.(38317757009345794392523364485981308411214953271028037)
355 / 113 -> 3.(1415929203539823008849557522123893805309734513274336283185840707964601769911504424778761061946902654867256637168)

Su programa debe funcionar para todos los ejemplos anteriores en menos de 10 segundos en una PC de escritorio moderna. El programa más pequeño en bytes gana.

orlp
fuente
@DestructibleWatermelon Esto es posible en casi todos los idiomas, incluidas las lonas de Turing. (Esos podrían luchar con el límite de tiempo sin embargo.)
Dennis
@DestructibleWatermelon Tenía la impresión de que la mayoría de los idiomas están completos.
orlp
¿Podemos suponer con seguridad que la fracción no será algo así como: 0.33333333333336333 ...?
brianush1
2
Esto parece una forma interminable de pedir soluciones a PE26 ;)
Conor O'Brien
1
Generalización de esta pregunta ; También relacionado .
Peter Taylor

Respuestas:

3

Perl 6 ,  63 58  50 bytes

{->$a,$b {$a~"($b)"x?$b}(|($^a.FatRat/$^b).base-repeating(10))}
{->\a,$b {a~"($b)"x?$b}(|($^a.FatRat/$^b).base-repeating)}
{$/=($^a.FatRat/$^b).base-repeating;$0~"($1)"x?$1}

Pruébalo

Si no le importa que solo funcione con denominadores que se ajusten a un entero de 64 bits, puede acortarse a solo 43 bytes:

{$/=($^a/$^b).base-repeating;$0~"($1)"x?$1}

Expandido:

{
  # store in match variable so that we can
  # use 「$0」 and 「$1」
  $/ = (

    # turn the first value into a FatRat so that
    # it will continue to work for all Int inputs
    $^a.FatRat / $^b

  ).base-repeating;

  # 「$0」 is short for 「$/[0]」 which is the non-repeating part
  $0

  # string concatenated with
  ~

  # string repeat once if $1 is truthy (the repeating part)
  # otherwise it will be an empty Str
  "($1)" x ?$1
}
Brad Gilbert b2gills
fuente
La forma en que formateó su respuesta es confusa. Debería eliminar sus programas antiguos, porque en este momento parece un programa de varias líneas.
mbomb007
@ mbomb007 La razón principal que tengo para publicar campos de golf es para el marketing y la educación de Perl 6. Así que dejo versiones antiguas para mostrar más del lenguaje. Es por eso que raramente publico uno hasta que tengo algún tipo de explicación allí. Lo he modificado para que los diferentes ejemplos estén en diferentes bloques de código.
Brad Gilbert b2gills
Las versiones antiguas siempre son visibles en el historial de edición de la publicación.
mbomb007
@ mbomb007 No si espero publicar hasta después de intentar varias formas diferentes de escribirlo.
Brad Gilbert b2gills
Luego solo edite uno de cada 5 minutos.
mbomb007
8

Python 2, 174 bytes

x,y=input()
a=abs(x)
b=abs(y)
r=a%b*10
L=[]
M=''
while~-(r in L):L+=r,;M+=str(r/b);r=r%b*10
i=L.index(r)
t=M[:i]+"(%s)"%M[i:]*(M[i:]>'0')
print"-%d."[x*y>=0:(t>'')+3]%(a/b)+t

No estoy muy convencido de la validez de esta respuesta, pero funcionó para los casos de prueba anteriores y otros casos de prueba que le he presentado. Sin embargo, parece un desastre, así que estoy seguro de que hay mucho espacio para jugar al golf.

La configuración inicial toma valores absolutos de ambos argumentos para garantizar que estamos tratando con números no negativos (guardando el cálculo del signo para más adelante), y delega la parte del cociente del resultado en la aritmética de precisión arbitraria de Python. La parte fraccionaria se realiza con el algoritmo de división de la escuela primaria hasta que obtengamos una repetición en el resto. Luego miramos hacia arriba cuando vimos esta repetición por última vez para obtener el período, y construimos la cadena en consecuencia.

Tenga en cuenta que el algoritmo en realidad es bastante lento debido a la inoperación O (n) , pero es lo suficientemente rápido para los ejemplos.

Sp3000
fuente
5

Lote, 349344 bytes

@echo off
set/ad=%2,i=%1/d,r=%1%%d
if not %r%==0 set i=%i%.&if %r% leq 0 set/ar=-r&if %i%==0 set i=-0.
set d=%d:-=%
set/ae=d
:g
if %r%==0 echo %i%&exit/b
set/ag=-~!(e%%2)*(!(e%%5)*4+1)
if not %g%==1 set/ae/=g&call:d&goto g
set/as=r
set i=%i%(
:r
call:d
if %r%==%s% echo %i%)&exit/b
goto r
:d
set/ar*=10,n=r/d,r%%=d
set i=%i%%n%

Editar: guardado 5 bytes eliminando caracteres innecesarios. "Sin golf":

@echo off
set /a d = %2
set /a i = %1 / d
set /a r = %1 % d
if not %r%==0 (
    set i=%i%.                  Decimal point is required
    if %r% leq 0 (
        set /a r = -r           Get absolute value of remainder
        if %i%==0 set i=-0.     Fix edge case (-1/3 = 0 remainder -1)
    )
)
set d = %d:-=%                  Get absolute value of divisor
set /a e = d
:g
if %r%==0 echo %i% & exit /b    Finished if there's no remainder
set /a g = gcd(e, 10)           Loop through nonrecurring decimals
if not %g%==1 (
    set /a e /= g
    call :d
    goto g
)
set /a s = r                    Save remainder to know when loop ends
set i=%i%(
:r
call :d
if %r%==%s% echo %i%)&exit/b
goto r
:d                              Add the next decimal place
set /a r *= 10
set /a n = r / d
set /a r %= d
set i=%i%%n%
Neil
fuente
2
No tengo idea de cómo funciona todo esto, pero lo felicito por hacerlo en el lote lmao
Alexander - Reinstale a Monica el
Estoy impresionado con las capacidades de set /a.
Joe
2

Java, 625 605

Código de golf:

import static java.math.BigInteger.*;
String f(BigInteger a, BigInteger b){BigInteger[]r=a.divideAndRemainder(b);String s=r[0].toString();if(r[1].signum()<0)s="-"+s;if(!ZERO.equals(r[1])){s+='.';List<BigInteger>x=new ArrayList();List<BigInteger>y=new ArrayList();for(BigInteger d=TEN.multiply(r[1].abs());;){BigInteger[]z=d.divideAndRemainder(b.abs());int i=y.indexOf(z[1]);if(i>-1&&i==x.indexOf(z[0])){for(int j=0;j<i;++j)s+=x.get(j);s+='(';for(int j=i;j<x.size();++j)s+=x.get(j);s+=')';break;}x.add(z[0]);y.add(z[1]);if(ZERO.equals(z[1])){for(BigInteger j:x)s+=j;break;}d=TEN.multiply(z[1]);}}return s;}

Nota: Cuento la importación estática como parte de la función para fines de golf.

Esta función comienza obteniendo el resultado de la división. Agrega la parte integral y el signo, si es necesario. Luego, si hay un resto, realiza una división larga de base 10. En cada paso, realiza la división. Almacene el dígito calculado y el resto en dos listas. Si nos encontramos con el mismo dígito y el resto nuevamente, hay una porción repetida y sabemos en qué índice comienza. El código agrega los dígitos (sin repetición) o los dígitos de repetición previa, luego los dígitos repetidos encerrados entre paréntesis.

Esto es un poco grande principalmente debido a BigInteger. Si las entradas no se desbordan ni siquiera a, longentonces podría ser un poco más corto. Aún así, espero que haya formas de mejorar esta entrada.

Código no protegido con método principal para probar:

import java.math.BigInteger;
import java.util.ArrayList;
import java.util.List;

import static java.math.BigInteger.*;

public class FractionToExactDecimal {

  public static void main(String[] args) {
    // @formatter:off
    String[][] testData = new String[][] {
      { "123562375921304812375087183597", "2777", "44494913907563850333124661" },
      { "81", "3", "27" },
      { "-6", "2", "-3" },
      { "1", "2", "0.5" },
      { "3289323463", "-250000000", "-13.157293852" },
      { "-1", "3", "-0.(3)" },
      { "235", "14", "16.7(857142)" },
      { "123", "321", "0.(38317757009345794392523364485981308411214953271028037)" },
      { "355", "113", "3.(1415929203539823008849557522123893805309734513274336283185840707964601769911504424778761061946902654867256637168)" }
    };
    // @formatter:on

    for (String[] data : testData) {
      System.out.println(data[0] + " / " + data[1]);
      System.out.println("  Expected -> " + data[2]);
      System.out.print("    Actual -> ");
      System.out.println(new FractionToExactDecimal().f(new BigInteger(data[0]), new BigInteger(data[1])));
      System.out.println();
    }
  }

  // Begin golf
  String f(BigInteger a, BigInteger b) {
    BigInteger[] r = a.divideAndRemainder(b);
    String s = r[0].toString();
    if (r[1].signum() < 0) s = "-" + s;
    if (!ZERO.equals(r[1])) {
      s += '.';
      List<BigInteger> x = new ArrayList();
      List<BigInteger> y = new ArrayList();
      for (BigInteger d = TEN.multiply(r[1].abs());;) {
        BigInteger[] z = d.divideAndRemainder(b.abs());
        int i = y.indexOf(z[1]);
        if (i > -1 && i == x.indexOf(z[0])) {
          for (int j = 0; j < i; ++j)
            s += x.get(j);
          s += '(';
          for (int j = i; j < x.size(); ++j)
            s += x.get(j);
          s += ')';
          break;
        }
        x.add(z[0]);
        y.add(z[1]);
        if (ZERO.equals(z[1])) {
          for (BigInteger j : x)
            s += j;
          break;
        }
        d = TEN.multiply(z[1]);
      }
    }
    return s;
  }
  // End golf
}

Salida del programa:

123562375921304812375087183597 / 2777
  Expected -> 44494913907563850333124661
    Actual -> 44494913907563850333124661

81 / 3
  Expected -> 27
    Actual -> 27

-6 / 2
  Expected -> -3
    Actual -> -3

1 / 2
  Expected -> 0.5
    Actual -> 0.5

3289323463 / -250000000
  Expected -> -13.157293852
    Actual -> -13.157293852

-1 / 3
  Expected -> -0.(3)
    Actual -> -0.(3)

235 / 14
  Expected -> 16.7(857142)
    Actual -> 16.7(857142)

123 / 321
  Expected -> 0.(38317757009345794392523364485981308411214953271028037)
    Actual -> 0.(38317757009345794392523364485981308411214953271028037)

355 / 113
  Expected -> 3.(1415929203539823008849557522123893805309734513274336283185840707964601769911504424778761061946902654867256637168)
    Actual -> 3.(1415929203539823008849557522123893805309734513274336283185840707964601769911504424778761061946902654867256637168)

fuente
¡Agradable! Creo que puede guardar algunos bytes haciendo que esta sea una función que devuelve una cadena y eliminando ese espacio a, BigInteger. También creo que podrías alias BigInteger.TENy BigInteger.ZERO.
FryAmTheEggman
@FryAmTheEggman gracias, no me di cuenta de que la importación estática ahorró espacio en las referencias más detalladas. Lo hace. También encontré algunas otras cosas que me había perdido, como while (true)-> for (;;)que también me permitió poner cosas en el forinicializador, guardando otro byte.
Primero, ¿qué hay de extender BigInteger? Segundo, un resto repetido es suficiente para mostrar que se repite; si limita la entrada a int puede usar un int [] con el resto como índice y el índice como valor, si eso tiene sentido.
JollyJoker
@JollyJoker extender BigInteger requeriría escribir una clase completa para tratar de ahorrar espacio, y dudo seriamente que la compensación funcione. Además, no puedo restringir la entrada. De todos modos, hay ocho instancias del texto BigIntegeren mi código, y no veo cómo valdrá la pena agregar más código para reducirlos a un solo nombre de clase de caracteres. Y ciertamente agregar código para tratar int[](lo que BigInteger ya hace internamente) solo aumentará mi respuesta.
@JollyJoker también vale la pena mencionar que, a menos que anule todos los BigInteger métodos que llamo para devolver una instancia de la subclase, necesitaré agregar varios lanzamientos que inflarán aún más el código. Además de los bytes desperdiciados para la sobrecarga de una subclase, eso ciertamente aumentaría el tamaño del código.
1

PHP, 277 bytes

list(,$n,$d)=$argv;$a[]=$n;$n-=$d*$r[]=$n/$d^0;!$n?:$r[]=".";while($n&&!$t){$n*=10;$n-=$d*$r[]=$n/$d^0;$t=in_array($n%=$d,$a);$a[]=$n;}if($t){$l=count($a)-($p=array_search(end($a),$a));echo join(array_slice($r,0,2+$p))."(".join(array_slice($r,2+$p,$l)).")";}else echo join($r);
Jörg Hülsermann
fuente
0

Mathematica 198 bytes

i=Integer;t=ToString;a_~h~b_:=f[a/b];f@q_i:= t@q;
f@q_:=""<>{t@IntegerPart[q],".",RealDigits[FractionalPart[q]][[1]]//.{{x___,{k__i}}:> {x,"("<>(t/@{k})<>")"},{x__i,j___String}:>""<> {""<>t/@{x},j}}}

Sin golf

(* hand over quotient of a, b to function f *)
h[a_, b_] := f[a/b];

(* if the quotient is an integer, return it as a string *)
f[q_Integer] := ToString@q;

(* otherwise, return the integer part, followed by a decimal point ...*)
f[q_] := "" <> {ToString@IntegerPart[q], ".", 

   (* replacing the repeating part (if it exists) between parentheses *)
   RealDigits[FractionalPart[q]][[1]] //. {{x___, {i__Integer}} :> {x, "(" <>(ToString /@ {i}) <> ")"},

   (* and the non-repeating part (if it exists) without parentheses *)
   {x__Integer, i___String} :> "" <> {"" <> ToString /@ {x}, i}}}

Pruebas

h @@@ {{81, 3}, {-81, 3}, {1, 4}, {-13, 3}, {19, 7}, {3289323463, 25000}, {235, 14}, {1325, 14}}

{"27", "-27", "0.25", "-4. (3)", "2. (714285)", "131572.93852", "16.7 (857142)", "94.6 (428571)"}

DavidC
fuente