Fraction à la décimale exacte

23

Écrivez un programme ou une fonction qui, étant donné deux entiers a, b, émet une chaîne contenant un nombre décimal représentant exactement la fraction a / b .

Si a / b est un entier, affichez simplement la valeur, sans point décimal ni zéros non significatifs:

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

Si a / b n'est pas un entier mais a une représentation finie en base 10, sortez la valeur sans zéros de tête ou de fin (sauf un zéro unique avant le point):

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

Enfin, si et seulement si (donc non 0.999...) a / b n'est pas entier et n'a pas de représentation finie, sortez la partie finie suivie de la partie répétitive entre parenthèses. La partie répétée doit être aussi petite que possible et commencer le plus tôt possible.

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

Votre programme doit fonctionner pour tous les exemples ci-dessus en moins de 10 secondes sur un ordinateur de bureau moderne. Le plus petit programme en octets gagne.

orlp
la source
@DestructibleWatermelon Ceci est possible dans à peu près toutes les langues, y compris les bâches de Turing. (Cependant, ceux-ci pourraient avoir du mal à respecter le délai imparti.)
Dennis
@DestructibleWatermelon J'avais l'impression que la plupart des langues sont complètes.
orlp
Pouvons-nous supposer que la fraction ne sera pas quelque chose comme: 0,33333333333336333 ...?
brianush1
2
Cela semble être une façon longue de demander des solutions au PE26 ;)
Conor O'Brien
1
Généralisation de cette question ; également lié .
Peter Taylor

Réponses:

3

Perl 6 ,  63 58  50 octets

{->$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}

Essaye-le

Si vous ne vous souciez pas que cela ne fonctionne qu'avec des dénominateurs qui tiennent dans un entier 64 bits, il peut être raccourci à seulement 43 octets:

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

Étendu:

{
  # 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
la source
La façon dont vous avez formaté votre réponse prête à confusion. Vous devez supprimer vos anciens programmes, car en ce moment, il ressemble à un programme multiligne.
mbomb007
@ mbomb007 La principale raison pour laquelle j'ai publié des golfs est pour le marketing et l'éducation de Perl 6. Je laisse donc les anciennes versions pour montrer plus de la langue. C'est aussi pourquoi j'en poste rarement un jusqu'à ce que j'aie une sorte d'explication là-dedans. Je l'ai modifié pour que les différents exemples soient dans différents blocs de code.
Brad Gilbert b2gills
Les anciennes versions sont toujours visibles dans l'historique des modifications de l'article.
mbomb007
@ mbomb007 Pas si j'attends de poster après avoir essayé plusieurs façons de l'écrire.
Brad Gilbert b2gills
Ensuite, modifiez-en un toutes les 5 minutes.
mbomb007
8

Python 2, 174 octets

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

Je ne suis pas tout à fait convaincu de la validité de cette réponse, mais cela a fonctionné pour les cas de test ci-dessus et d'autres cas de test que j'ai lancés dessus. Cela ressemble à un bon bordel, donc je suis sûr qu'il y a beaucoup de place pour le golf.

La configuration initiale prend les valeurs absolues des deux arguments pour garantir que nous avons affaire à des nombres non négatifs (en enregistrant le calcul du signe pour plus tard) et délègue la partie quotient du résultat à l'arithmétique de précision arbitraire de Python. La partie fractionnaire se fait avec l'algorithme de division scolaire jusqu'à ce que nous obtenions une répétition dans le reste. Nous recherchons ensuite la dernière fois que nous avons vu cette répétition afin d'obtenir le point et construisons la chaîne en conséquence.

Notez que l'algorithme est en fait assez lent en raison de l'opération O (n) in, mais il est assez rapide pour les exemples.

Sp3000
la source
5

Lot, 349 344 octets

@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%

Modifier: enregistré 5 octets en supprimant les caractères inutiles. "Non 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
la source
2
Je n'ai aucune idée de la façon dont tout cela fonctionne, mais je vous félicite de l'avoir fait en lot lmao
Alexander - Reinstate Monica
Je suis impressionné par les capacités de set /a.
Joe
2

Java, 625 605

Code 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;}

Remarque: Je compte l'importation statique comme faisant partie de la fonction à des fins de golf.

Cette fonction commence par obtenir le résultat de la division. Il ajoute la partie intégrale et le signe, si nécessaire. S'il reste, il effectue une division longue en base 10. À chaque étape, effectuez la division. Stockez le chiffre calculé et le reste dans deux listes. Si nous rencontrons le même chiffre et le reste à nouveau, il y a une partie répétée et nous savons à quel indice il commence. Le code ajoute les chiffres (pas de répétition) ou les chiffres de pré-répétition, puis les chiffres répétés entre parenthèses.

C'est un peu gros principalement à cause de BigInteger. Si les entrées ne débordaient même pas, longcela pourrait être un peu plus court. Pourtant, je m'attends à ce qu'il existe des moyens d'améliorer cette entrée.

Code non golfé avec méthode principale de test:

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
}

Sortie du programme:

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)

la source
Agréable! Je pense que vous pouvez économiser quelques octets en en faisant une fonction qui renvoie une chaîne et en supprimant cet espace a, BigInteger. Je pense aussi que vous pourriez alias BigInteger.TENet BigInteger.ZERO.
FryAmTheEggman
@FryAmTheEggman merci, je ne me suis pas rendu compte de l'espace enregistré pour l'importation statique sur les références les plus verbeuses. Cela fait. J'ai également trouvé quelques autres choses que j'avais manquées, telles que while (true)-> for (;;)qui m'a également permis de mettre des choses dans l' forinitialiseur, en économisant un autre octet.
Tout d'abord, que diriez-vous d'étendre BigInteger? Deuxièmement, un reste répété suffit pour montrer qu'il se répète; si vous limitez l'entrée à int, vous pouvez utiliser un int [] avec le reste comme index et l'index comme valeur, si cela a du sens.
JollyJoker
@JollyJoker étendant BigInteger nécessiterait d'écrire toute une classe pour essayer d'économiser de l'espace, et je doute sérieusement que le compromis fonctionnerait. De plus, je ne peux pas restreindre la saisie. Quoi qu'il en soit, il y a huit instances du texte BigIntegerdans mon code, et je ne vois pas comment l'ajout de plus de code pour les réduire à un nom de classe de caractère unique sera payant. Et certainement ajouter du code à traiter int[](ce que BigInteger fait déjà en interne) ne fera que gonfler ma réponse.
@JollyJoker, il convient également de mentionner qu'à moins de remplacer toutes les BigInteger méthodes que j'appelle pour renvoyer une instance de la sous-classe, je devrai ajouter plusieurs transtypages qui alourdissent encore le code. En plus des octets gaspillés pour la surcharge d'une sous-classe, cela augmenterait certainement la taille du code.
1

PHP, 277 octets

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
la source
0

Mathematica 198 octets

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

Les tests

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
la source