Ganti beberapa bagian periodik dan non-periodik

21

Dalam representasi desimal dari setiap bilangan rasional p/q, Anda memiliki ekor periodik, kepala non-periodik, dan bagian sebelum titik desimal dalam format berikut:

(before decimal point).(non-periodic)(periodic)

Beberapa contoh termasuk:

1/70 = 0.0142857... = (0).(0)(142857)
10/7 = 1.428571... = (1).()(428571)            ## no non-periodic part
1/13 = 0.076923... = (0).()(076923)
3/40 = 0.075 = (0).(075)()                    ## no periodic part
-2/15 = -0.13... = -(0).(1)(3)                ## negative
75/38 = 1.9736842105263157894... = (1).(9)(736842105263157894)
                                              ## periodic part longer than float can handle
25/168 = 0.148809523... = (0).(148)(809523)
120/99 = 40/33 = 1.212121... = (1).()(21)
2/1 = 2 = (2).()()                            ## no periodic, no non-periodic
0/1 = 0 = (0).()()
0/2 = 0 = (0).()()
299/792 = 0.37752... = (0).(377)(52)
95/-14 = -6.7857142... = -(6).(7)(857142)
-95/-14 = 6.7857142... = (6).(7)(857142)

Tantangannya adalah untuk menukar bagian-bagian periodik dan non-periodik, meninggalkan yang before decimal pointsendirian, untuk membuat nomor baru. Sebagai contoh:

25/168 = 0.148809523... = (0).(148)(809523)
       => (0).(809523)(148) = 0.809523148148... = 870397/1080000

Jika suatu angka tidak memiliki bagian periodik seperti 0.25ubahlah angka itu menjadi angka periodik baru, dan sebaliknya.

1/4 = 0.25 = (0).(25)() => (0).()(25) = 0.252525... = 25/99
4/9 = 0.444444... = (0).()(4) => (0).(4)() = 0.4 = 2/5
5/1 = 5 = (5).()() => (5).()() = 5 = 5/1

Tantangan

  • Ambil sebagian kecil xsebagai input, sebagai string, dua input, angka rasional, atau metode apa pun yang sesuai dengan bahasa Anda.
  • Tukar bagian periodik dan non-periodik dari representasi desimal xuntuk membuat angka baru, dan tinggalkan bagian sebelum desimal saja. Bagian periodik selalu dimulai sesegera mungkin sehingga bagian non-periodik sesingkat mungkin. Contohnya di bawah ini.
  • Kembalikan nomor yang ditukar sebagai fraksi baru. Input tidak harus dikurangi meskipun output seharusnya. Format input diperbolehkan berbeda dari format output.
  • Pembilang pdari xakan integer dengan nilai absolut dari satu juta atau kurang dan penyebut qdari xakan menjadi non-nol bilangan bulat dengan nilai absolut dari satu juta atau kurang.
  • Pembilang rdan penyebut shasilnya tidak dijamin kurang dari satu juta. Mengingat panjang bagian periodik dari angka-angka ini, disarankan agar Anda tidak langsung mengkonversi menjadi pelampung.
  • Ini kode golf. Jawaban terpendek dalam byte menang.

Contohnya

1/70 = (0).(0)(142857)     => (0).(142857)(0) = (0).(142857)() = 0.142857 = 142857/1000000
10/7 = (1).()(428571)      => (1).(428571)() = 1.428571 = 1428571/1000000
1/13 = (0).()(076923)      => (0).(076923)() = 0.076293 = 76923/1000000
3/40 = (0).(075)()         => (0).()(075) = 0.075075... = 75/999 = 25/333
-2/15 = -(0).(1)(3)        => -(0).(3)(1) = -0.311111... = -28/90 = -14/45
75/38 = (1).(9)(736842105263157894)
      => (1).(736842105263157894)(9) = (1).(736842105263157895)()  ## since 0.999... = 1
      = 1.736842105263157895 = 1736842105263157895/1000000000000000000
      = 347368421052631579/200000000000000000
25/168 = (0).(148)(809523) => (0).(809523)(148) = 0.809523148148... = 870397/1080000
120/99 = (1).()(21)        => (1).(21)() = 1.21 = 121/100
2/1 = (2).()()             => (2).()() = 2 = 2/1
0/1 = (0).()()             => (0).()() = 0 = 0/1
0/2 = (0).()()             => (0).()() = 0 = 0/1
299/792 = (0).(377)(52)    => (0).(52)(377) = 0.52377377... = 2093/3996
95/-14 = -(6).(7)(857142)  => -(6).(857142)(7) = -6.857142777... = -12342857/1800000
-95/-14 = (6).(7)(857142)  => (6).(857142)(7) = 6.857142777... = 12342857/1800000
Sherlock9
sumber
Ada yang hilang 0pada akhir uji kasus 2 ( 10/7): 1428571/100000seharusnya 1428571/1000000.
JungHwan Min
1
Sebagaimana dinyatakan tidak akan ada jawaban unik untuk input yang diberikan. 1/7dapat direpresentasikan sebagai (0).()(142857) atau (0).(1)(428571), 1bisa direpresentasikan sebagai (1).()(), (0).()(9), (0).()(99), (0).(9)(9), dll
ngenisis
@ngenisis Itu tersirat dalam contoh, tapi saya telah membuatnya eksplisit. Terima kasih atas umpan baliknya :)
Sherlock9
@ R. Kap Saya sudah menyatakan dalam tantangan bahwa yang terbaik adalah menghindari menggunakan pelampung di sini. Ada cara untuk menemukan angka desimal angka tanpa mengkonversi ke float. Saya harap ini menjawab pertanyaan Anda :)
Sherlock9
dapatkah p dan q negatif?
edc65

Jawaban:

5

Python 2, 292 byte

def x(n,d):
 L=len;s=cmp(n*d,0);n*=s;b=p=`n/d`;a={};n%=d
 while not n in a:
  a[n]=p;q=n/d;n=n%d
  if q==0:n*=10;p+=' '
  p=p[:-1]+`q`
 p=p[L(a[n]):];a=a[n][L(b):]
 if n==0:p=''
 n=int(b+p+a);d=10**L(p+a)
 if a!='':n-=int(b+p);d-=10**L(p)
 import fractions as f;g=f.gcd(n,d);return(n/g*s,d/g)

Versi tidak disatukan, bekerja di kedua python 2 & 3. Juga mencetak representasi desimal.

def x(n,d):
# sign handling
 s=n*d>0-n*d<0
 n*=s
# b, a, p: BEFORE decimal, AFTER decimal, PERIODIC part
 b=p=str(n//d)
 a={}
 n%=d
# long division
 while not n in a:
  a[n]=p
  q=n//d
  n=n%d
  if q==0:
   n*=10
   p+=' '
  p=p[:-1]+str(q)
# a/p still contain b/ba as prefixes, remove them
 p=p[len(a[n]):]
 a=a[n][len(b):]
 if n==0: p=''
# print decimal representation
 print("(" + b + ").(" + a + ")(" + p + ")")
# reassemble fraction (with a and p exchanged)
 n=int(b+p+a)
 d=10**len(p+a)
 if a!='':
  n-=int(b+p)
  d-=10**len(p)
# reduce output
 from fractions import gcd
 g=gcd(n,d)
 return(n//g*s,d//g)
Rainer P.
sumber
Cobad=10**len(p+a)
Sherlock9
1
Berikut ini adalah tautan TIO untuk pengujian mudah: Cobalah secara online!
Kritixi Lithos
Bagus atas jawaban Anda: D. Beberapa kiat bermain golf lebih lanjut: gunakan lebih banyak titik koma di mana mungkin, singkirkan ruang di garis if n==0: p='', gunakan ``di setiap tempat yang Anda gunakan str, seperti sebagai `n/d`ganti str(n/d), dan ganti nama lenmenjadi Ldengan L=len;di awal fungsi.
Sherlock9
@ Sherlock9 Aku bahkan tidak tahu tentang backticks. Terima kasih untuk semua sarannya.
Rainer P.
Bukan masalah. Berikut ini beberapa lainnya: D Dua tempat untuk titik koma: n=int(b+p+a);d=10**L(p+a)dan import fractions as f;g=f.gcd(n,d);return(n/g*s,d/g). Juga, saya mendapatkan 295 byte untuk hasil edit Anda saat ini. Apakah ada baris baru tambahan yang Anda lupa tinggalkan?
Sherlock9
2

Jelly , 102 101 89 87 83 81 79 78 77 74 byte

Ini butuh waktu lama untuk menulis, terlalu lama untuk men-debug, dan tentu saja membutuhkan banyak golf ( delapan tujuh enam lima empat tautan, sapi suci), tetapi, sejauh pengetahuan saya, benar. Banyak, banyak terima kasih kepada Dennis untuk bantuannya di sini, terutama dengan dua tautan pertama. Banyak terima kasih kepada Rainer P. juga, karena saya akhirnya meminjam banyak algoritma dalam jawaban Python mereka.

Suntingan golf: -1 byte berkat Xanderhall. Perbaikan bug dari tidak menggunakan logika TIDAK benar builtin. -13 byte dari bermain golf pada tautan pembilang. +1 byte dari memperbaiki bug untuk negatif ddengan terima kasih kepada Dennis. Merestrukturisasi tautan sehingga generasi pembilang semuanya dalam satu tautan. -2 byte dari menggabungkan tautan kedua dan ketiga. -4 byte dari memindahkan beberapa elemen umum dari tautan ketiga dan keempat ke tautan kedua dan tautan utama. -2 byte dari menghapus beberapa operator rantai berlebihan. -2 byte dari mengatur ulang tautan pembilang. -1 byte dari pemindahan Ḣ€ke ujung tautan kedua. Memperbaiki bug di tautan utama. -1 byte dari pengubahan Ṫ ... ,Ḣke Ḣ ... ṭ. -3 byte dari memindahkan tautan pembilang ke tautan utama.

Selamat datang saran bermain golf! Cobalah online!

2ị×⁵d⁴
ÇÐḶ,ÇÐĿḟ@\µḢḅÐfıṭµḢḊṭµḢ€€µF,ḢQ
ÇL€⁵*
×Ṡ©⁸×%µ³,⁴A:/;Ѐ2ĿḌ×®,Ç_/€µ:g/

Penjelasan

Pertama, saya akan menjelaskan tautan utama , yang memanggil tautan lain.

×Ṡ©⁸×%µ³,⁴A:/;Ѐ2ĿḌ×®,Ç_/€µ:g/  Main link. Left argument: n (int), right argument: d (int)
                                Split into three chains.
×Ṡ©⁸×%  First chain
×       Multiply n by d.
 Ṡ©     Yield sign(n*d) and save it to the register.
   ⁸×   Multiply by n.
     %  Yield n*sgn(n*d) modulo d.

µ³,⁴A:/;Ѐ2ĿḌ×®,Ç_/€  Second chain
                        What follows is the formula for the numerator.
                        (+) means combining the digits of two numbers into one number.
                        ( `integer (+) periodic (+) non-periodic` - `integer (+) periodic` )
µ                     Start a new monadic chain with n*sgn(n*d)%d.
 ³,⁴                  Pair the original two arguments as a nilad.
    A                 Get their absolute values.
     :/               Integer divide to get the integer part of abs(n)/abs(d).
          2Ŀ          Yield the results of the second link.
       ;Ѐ            Append the integer part to each item in the right argument.
                        This appends to both lists from the second link.
            Ḍ         Convert each list from decimal to integer.
             ×®       Multiply by sign(n*d) retrieved from the register.
               ;Ç     Concatenate with the result of the third link (our new denominator).
                 _/€  Reduced subtract over each list.
                        Yields the proper numerator and denominator.

µ:g/  Third chain
µ     Start a new monadic chain with [numerator, denominator].
  g/  Yield gcd(numerator, denominator).
 :    Divide [numerator, denominator] by the gcd.
      Return this as our new fraction.

Lalu, tautan pertama yang mendapat digit.

2ị×⁵d⁴  First link: Gets the decimal digits one at a time in the format:
          [digit, remainder to use in the next iteration]
2ị      Gets the second index (the remainder).
  ×⁵    Multiply by 10.
    d⁴  Divmod with d.

Sekarang, link kedua yang mendapat bagian periodik dan non-periodik n/d, dan banyak mengangkat berat lainnya.

ÇÐḶ,ÇÐĿḟ@\µḢḅÐfıṭµḢḊṭµḢ€€µF,ḢQ  Second link: Loops the first link,
                                  separates the periodic digits and non-periodic digits,
                                  removes the extras to get only the decimal digits,
                                  and prepares for the third and fourth links.
                                Split into five chains.
ÇÐḶ,ÇÐĿḟ@\  First chain
ÇÐḶ         Loop and collect the intermediate results **in the loop**.
    ÇÐĿ     Loop and collect **all** of the intermediate results.
   ,        Pair into one list.
       ḟ@\  Filter the loop results out the list of all results,
              leaving only [[periodic part], [non-periodic part]].

µḢḅÐfıṭµḢḊṭ  Second and third chains
µ            Start a new monadic chain.
 Ḣ           Get the head [periodic part].
   Ðf        Filter out any [0, 0] lists from a non-periodic number,
  ḅ  ı        by converting to a complex number before filtering.
               Only removes 0+0j. This removes extra zeroes at the end.
      ṭ      Tack the result onto the left argument again.
       µ     Start a new monadic chain.
        Ḣ    Get the head [non-periodic and extra baggage].
         Ḋ   Dequeue the extra baggage.
          ṭ  Tack the result onto the left argument again.

µḢ€€µF,ḢQ  Fourth and fifth chains
µ          Start a new monadic chain with the processed periodic and non-periodic parts.
 Ḣ€€       Get the head of each list (the digits)
            in both the periodic and non-periodic parts.
    µ      Start a new monadic chain with these lists of digits.
     F     Left argument flattened.
       Ḣ   Head of the left argument.
      ,    Pair the flattened list and the head into one list.
        Q  Uniquify this list. (Only removes if non-periodic part is empty)
             Removes any duplicates resulting from a purely periodic n/d.

The Link ketiga , yang menghasilkan denominator baru.

ÇL€⁵*  Third link: Generate the denominator.
         What follows is the formula for the denominator.
         ( 10**(num_digits) - ( 10**(num_periodic_digits) if len(non-periodic) else 0 ) )
Ç      Yield the results of the second link.
 L€    Get the length of each item in the list.
         The number of digits in total and the number of digits in the periodic part.
   ⁵*  10 to the power of each number of digits.
Sherlock9
sumber