Fração para decimal exato

23

Escreva um programa ou função que, com dois números inteiros a, b, produza uma sequência contendo um número decimal que representa exatamente a fração a / b .

Se a / b for inteiro, basta gerar o valor, sem um ponto decimal ou zeros à esquerda:

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

Se a / b não for inteiro, mas tiver uma representação finita na base 10, imprima o valor sem zeros à esquerda ou à direita (exceto um único zero antes do ponto):

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

Finalmente, se e somente se (então não 0.999...) a / b não é um número inteiro e não possui uma representação finita, produza a parte finita seguida pela parte repetida entre parênteses. A parte repetida deve ser a menor possível e começar o mais cedo possível.

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

Seu programa deve funcionar para todos os exemplos acima em menos de 10 segundos em um PC de mesa moderno. O menor programa em bytes vence.

orlp
fonte
@DestructibleWatermelon Isso é possível em praticamente todos os idiomas, incluindo tarpits de Turing. (Aqueles pode lutar com o limite de tempo embora.)
Dennis
@DestructibleWatermelon Fiquei com a impressão de que a maioria dos idiomas está completa.
orlp
Podemos assumir com segurança que a fração não será algo como: 0,33333333333336333 ...?
Brianush1
2
Esta parece ser uma forma prolixa de pedir soluções para PE26 ;)
Conor O'Brien
1
Generalização desta questão ; também relacionado .
Peter Taylor

Respostas:

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}

Teste-o

Se você não se importa que ele funcione apenas com denominadores que se encaixam em um número inteiro de 64 bits, pode ser reduzido para apenas 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
fonte
A maneira como você formatou sua resposta é confusa. Você deve remover seus programas antigos, porque agora parece um programa de várias linhas.
mbomb007
@ mbomb007 O principal motivo que eu tenho para postar golfe é o marketing e a educação do Perl 6. Portanto, deixo as versões antigas para mostrar mais do idioma. É também por isso que raramente posto um até ter algum tipo de explicação. Eu a alterei para que os diferentes exemplos estejam em diferentes blocos de código.
Brad Gilbert b2gills
As versões antigas estão sempre visíveis no histórico de edições da postagem.
mbomb007
@ mbomb007 Não se eu esperar para postar até depois de tentar várias maneiras diferentes de escrevê-lo.
Brad Gilbert b2gills
Em seguida, basta editar um a 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

Não estou muito convencido sobre a validade dessa resposta, mas ela funcionou para os casos de teste acima e outros casos de teste que joguei para ela. Parece uma bagunça certa, então eu tenho certeza que há muito espaço para jogar golfe.

A configuração inicial usa valores absolutos de ambos os argumentos para garantir que estamos lidando com números não negativos (salvando o cálculo de sinal para mais tarde) e delega a parte quociente do resultado na aritmética de precisão arbitrária do Python. A parte fracionária é feita com o algoritmo da divisão da escola primária até obtermos uma repetição no restante. Em seguida, olhamos quando vimos essa repetição pela última vez para obter o período e construímos a sequência de acordo.

Observe que o algoritmo é realmente muito lento devido à inoperação O (n) , mas é rápido o suficiente para os exemplos.

Sp3000
fonte
5

Lote, 349 344 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: salvou 5 bytes removendo caracteres desnecessários. "Ungolfed":

@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
fonte
2
Não tenho idéia de como isso funciona, mas recomendo que você faça isso no lote lmao #
Alexander - Reinstate Monica
Estou impressionado com as capacidades de set /a.
Joe
2

Java, 625 605

Código de golfe:

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: Conto a importação estática como parte da função para fins de golfe.

Esta função começa obtendo o resultado da divisão. Ele adiciona a parte integral e o sinal, se necessário. Então, se houver um restante, ele executa a divisão longa da base 10. Em cada etapa, execute a divisão. Armazene o dígito calculado e o restante em duas listas. Se encontrarmos o mesmo dígito e o restante novamente, haverá uma porção repetida e saberemos em que índice ele começa. O código adiciona os dígitos (sem repetição) ou os dígitos de pré-repetição e os dígitos repetidos entre parênteses.

Isso é um pouco grande principalmente por causa de BigInteger. Se as entradas não transbordarem, mesmo longassim, poderá ser um pouco menor. Ainda assim, espero que haja maneiras de melhorar essa entrada.

Código ungolfed com método principal de teste:

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
}

Saída do 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)

fonte
Agradável! Eu acho que você pode salvar alguns bytes, tornando isso uma função que retorna uma string e removendo esse espaço a, BigInteger. Eu também acho que você poderia apelido BigInteger.TENe BigInteger.ZERO.
FryAmTheEggman
@FryAmTheEggman obrigado, eu não percebi que a importação estática economizava espaço nas referências mais detalhadas. Faz. Eu também encontrei algumas outras coisas que eu perdi, como while (true)-> for (;;)que também me permitiram colocar coisas no forinicializador, economizando outro byte.
Primeiro, que tal estender o BigInteger? Segundo, um restante repetido é suficiente para mostrar que se repete; se você limitar a entrada a int, poderá usar um int [] com o restante como índice e o índice como valor, se isso fizer sentido.
JollyJoker #
A @JollyJoker estendendo o BigInteger exigiria escrever uma classe inteira para tentar economizar espaço, e eu duvido seriamente que a troca funcione. Além disso, não posso restringir a entrada. De qualquer forma, há oito instâncias do texto BigIntegerno meu código e não vejo como a adição de mais código para reduzi-los a um único nome de classe de caractere será recompensada. E certamente adicionando código para lidar comint[] (o que o BigInteger já faz internamente) apenas inchará a minha resposta.
@JollyJoker também vale a pena mencionar que, a menos que eu substitua todos os BigInteger métodos que chamo para retornar uma instância da subclasse, precisarei adicionar vários elencos que aumentam ainda mais o código. Além dos bytes desperdiçados pela sobrecarga de uma subclasse, isso certamente aumentaria o tamanho do 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
fonte
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}}}

UnGolfed

(* 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}}}

Testes

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
fonte