Pecahan menjadi desimal tepat

23

Tulis program atau fungsi yang memberikan dua bilangan bulat a, b menghasilkan string yang berisi angka desimal yang mewakili fraksi a / b secara tepat .

Jika a / b adalah bilangan bulat, cukup output nilainya, tanpa titik desimal atau nol di depan:

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

Jika a / b bukan bilangan bulat tetapi memiliki representasi terbatas di basis 10, output nilai tanpa memimpin atau membuntuti nol (kecuali nol tunggal sebelum titik):

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

Akhirnya, jika dan hanya jika (jadi tidak 0.999...) a / b tidak bilangan bulat dan tidak memiliki representasi yang terbatas, output bagian yang terbatas diikuti oleh bagian berulang dalam tanda kurung. Bagian berulang harus sekecil mungkin, dan mulai sedini mungkin.

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

Program Anda harus bekerja untuk semua contoh di atas dalam waktu kurang dari 10 detik pada PC desktop modern. Program terkecil dalam byte menang.

orlp
sumber
@DestructibleWatermelon Ini dimungkinkan di hampir semua bahasa, termasuk Turing tarpits. (Mereka mungkin berjuang dengan batas waktu.)
Dennis
@DestructibleWatermelon Saya mendapat kesan bahwa sebagian besar bahasa sedang selesai.
orlp
Bisakah kita dengan aman menganggap fraksi tidak akan menjadi sesuatu seperti: 0,33333333333336333 ...?
brianush1
2
Ini sepertinya cara bertele-tele untuk meminta solusi untuk PE26 ;)
Conor O'Brien
1
Generalisasi pertanyaan ini ; juga terkait .
Peter Taylor

Jawaban:

3

Perl 6 ,  63 58  50 byte

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

Menguji

Jika Anda tidak peduli bahwa itu hanya akan bekerja dengan penyebut yang cocok dengan integer 64 bit, itu dapat disingkat menjadi hanya 43 byte:

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

Diperluas:

{
  # 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
sumber
Cara Anda memformat jawaban Anda membingungkan. Anda harus menghapus program lama Anda, karena sekarang ini terlihat seperti program multi-line.
mbomb007
@ mbomb007 Alasan utama saya memposting golf adalah untuk pemasaran, dan pendidikan Perl 6. Jadi saya meninggalkan versi lama untuk menunjukkan lebih banyak bahasa. Itu juga sebabnya saya jarang memposting satu sampai saya punya semacam penjelasan di sana. Saya telah mengubahnya sehingga contoh yang berbeda ada di blok kode yang berbeda.
Brad Gilbert b2gills
Versi lama selalu terlihat dalam riwayat edit pos.
mbomb007
@ mbomb007 Tidak jika saya menunggu untuk mengirim sampai setelah mencoba beberapa cara untuk menulisnya.
Brad Gilbert b2gills
Kemudian cukup edit satu dalam setiap 5 menit.
mbomb007
8

Python 2, 174 byte

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

Saya tidak begitu yakin tentang validitas jawaban ini, tetapi ini berhasil untuk kasus uji di atas dan kasus uji lain yang saya berikan. Ini terlihat seperti kekacauan yang tepat, jadi saya yakin ada banyak ruang untuk bermain golf.

Penyiapan awal mengambil nilai absolut dari kedua argumen untuk memastikan bahwa kita berhadapan dengan bilangan non-negatif (menyimpan perhitungan tanda untuk nanti), dan mendelegasikan bagian hasil bagi hasil ke aritmatika presisi sewenang-wenang Python. Bagian fraksional dilakukan dengan algoritma pembagian kelas-sekolah sampai kita mendapatkan pengulangan dalam sisanya. Kami kemudian melihat ke atas ketika kami terakhir kali melihat pengulangan ini untuk mendapatkan periode, dan membangun string yang sesuai.

Perhatikan bahwa algoritma ini sebenarnya cukup lambat karena operasi O (n) in, tetapi cukup cepat untuk contoh.

Sp3000
sumber
5

Batch, 349 344 byte

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

Sunting: Disimpan 5 byte dengan menghapus karakter yang tidak perlu. "Tidak Disatukan":

@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
sumber
2
Saya tidak tahu bagaimana semua ini bekerja, tetapi saya memuji Anda untuk melakukannya dalam batch lmao
Alexander - Reinstate Monica
Saya terkesan dengan kemampuan set /a.
Joe
2

Jawa, 625 605

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

Catatan: Saya menghitung impor statis sebagai bagian dari fungsi untuk tujuan bermain golf.

Fungsi ini dimulai dengan mendapatkan hasil pembagian. Itu menambahkan bagian integral dan tanda, jika perlu. Kemudian jika ada sisanya, ia melakukan basis 10 divisi panjang. Di setiap langkah, lakukan pembagian. Simpan digit yang dihitung dan sisanya dalam dua daftar. Jika kita menemukan angka yang sama dan tetap lagi, ada bagian yang berulang dan kita tahu indeksnya dimulai dari mana. Kode dapat menambahkan digit (tanpa pengulangan) atau digit pra-pengulangan, lalu digit yang berulang diapit tanda kurung.

Ini agak besar karena sebagian besar BigInteger. Jika inputnya tidak melimpah bahkan longmungkin sedikit lebih pendek. Meski begitu, saya berharap ada cara untuk meningkatkan entri ini.

Kode tidak dikumpulkan dengan metode utama untuk pengujian:

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
}

Output program:

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)

sumber
Bagus! Saya pikir Anda dapat menyimpan beberapa byte dengan membuat ini fungsi yang mengembalikan string, dan dengan menghapus satu spasi a, BigInteger. Saya juga berpikir Anda bisa alias BigInteger.TENdan BigInteger.ZERO.
FryAmTheEggman
@FryAmTheEggman terima kasih, saya tidak menyadari impor statis menghemat ruang atas referensi yang lebih banyak. Itu benar. Saya juga menemukan beberapa hal lain yang saya lewatkan, seperti while (true)-> for (;;)yang juga memungkinkan saya untuk meletakkan barang-barang di forpenginisialisasi, menghemat byte lain.
Pertama, bagaimana dengan memperpanjang BigInteger? Kedua, sisa yang berulang cukup untuk menunjukkannya berulang; jika Anda membatasi input ke int Anda dapat menggunakan int [] dengan sisanya sebagai indeks dan indeks sebagai nilai, jika itu masuk akal.
JollyJoker
@JollyJoker memperluas BigInteger akan membutuhkan penulisan seluruh kelas untuk mencoba menghemat ruang, dan saya serius ragu pengorbanannya akan berhasil. Plus, saya tidak dapat membatasi input. Bagaimanapun, ada delapan contoh teks BigIntegerdalam kode saya, dan saya tidak melihat bagaimana menambahkan lebih banyak kode untuk mengecilkannya ke nama kelas karakter tunggal akan membayar. Dan tentu saja menambahkan kode untuk menangani int[](yang sudah dilakukan BigInteger secara internal) hanya akan mengasapi jawaban saya.
@ JollyJoker juga perlu disebutkan bahwa kecuali saya mengganti setiap BigInteger metode yang saya panggil untuk mengembalikan instance dari subclass, saya akan perlu menambahkan beberapa gips yang selanjutnya mengasapi kode. Di atas byte yang terbuang untuk overhead subclass, yang tentunya akan meningkatkan ukuran kode.
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
sumber
0

Mathematica 198 byte

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

Tidak disatukan

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

Tes

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
sumber