LCM dari Angka Rasional

18

Multiple paling umum (LCM) dari satu set angka Aadalah bilangan bulat terkecil bsehingga b/amerupakan bilangan bulat untuk semua bilangan bulat adi A. Definisi ini dapat diperluas ke bilangan rasional!

Tugas

Temukan rasional positif terkecil bsehingga b/amerupakan bilangan bulat untuk semua rasional a dalam input.

Aturan

  • Celah standar dilarang.
  • Anda dapat mengambil pembilang dan penyebut secara terpisah dalam input, tetapi mungkin tidak mengambil ganda, mengapung, dll.
  • Input mungkin tidak sepenuhnya berkurang.
  • Anda dapat mengambil input integer sebagai rasional dengan penyebut dari 1.
  • Pengajuan yang akan memberi makan nomor rasional ke builtin LCM / GCD diperbolehkan, tetapi tidak bersaing.

Uji Kasus

In:  3
Out: 3

In:  1/17
Out: 1/17

In:  1/2, 3/4
Out: 3/2

In:  1/3, 2/8
Out: 1

In:  1/4, 3
Out: 3

In:  2/5, 3
Out: 6

In:  1/2, 3/4, 5/6, 7/8
Out: 105/2

Ini adalah , jadi pengiriman menggunakan byte paling sedikit menang!

JungHwan Min
sumber
4
Catatan: komputasi LCM[numerators]/GCD[denominators]mungkin tidak berfungsi ketika input berisi angka rasional yang tidak dikurangi. mis 1/3, 2/8.
JungHwan Min
Jadi jika saya menguranginya, itu akan berhasil?
Leaky Nun
@ LeakyNun Ya, itu akan.
JungHwan Min
Untuk mendorong orang agar mengirimkan jawaban yang tidak built-in, saya telah mengedit pertanyaan, menjadikan jawaban built-in tidak bersaing (masih diizinkan). Jika ini masalah, saya akan mengembalikan hasil edit saya.
JungHwan Min
Bagaimana dengan built-in LCM yang digunakan tetapi hanya dengan bilangan bulat - bersaing atau tidak?
Jonathan Allan

Jawaban:

5

Jelly , 19 byte

g/:@$€Z©Ḣæl/;®Ḣg/$¤

Cobalah online!

Biarawati Bocor
sumber
1
tfw Jelly menyebalkan dengan pecahan
Erik the Outgolfer
2
g/:@$€->:g/$€
Jonathan Allan
2
Simpan dua byte lagi dengan::g/$€ZµḢæl/,Ḣg/$
Jonathan Allan
@ JonathanAllan Itu kode yang bagus ...
Erik the Outgolfer
6

J, 3 byte, tidak bersaing.

*./

Diberikan daftar input rasional, ini melipat LCM melaluinya.

zgrep
sumber
4

sed, 374 (373 +1) byte

-EBendera sed dihitung sebagai satu byte. Catatan: Saya belum mencoba bermain golf ini, dan mungkin tidak akan lama.
Input diambil di unary, dan output di unary. Spasi harus mengelilingi setiap fraksi. Contoh: echo " 1/111 111/11111 111111/111 ".

:d;s, (1*)/\1(1*), \1/\22,;s,(1*)(1*)/\2 ,2\1/\2 ,;td;s,1*(1/22*),\1,g;s,(22*/1)1*,\1,g;:r;s,((1*)/1*)2,\1\2,;s,2(1*/(1*)),\2\1,;tr;h;s,1*/,,g;:g;s/^(1*) 1(1*) 1(1*)/1\1 \2 \3/;tg;s/  */ /g;s/^/ /;/1 1/bg;x;s,/1*,,g;s/^( 1*)( 1*)/\1\2\2/;:l;s/^(1*) (1*) \2(1*)/\1\2 \2 \3/;tl;/  $/be;/  /{s/^(1*) 1*  1*( 1*)/ \1\2\2/;bl};s/^(1* 1* )(1*) (1*)/\1\2\3 \3/;bl;:e;G;s, *\n *,/,

Cobalah online!

zgrep
sumber
4

Python 2 , 65 byte (tidak bersaing)

lambda x:reduce(lambda x,y:x*y/gcd(x,y),x)
from fractions import*

Cobalah online!

ovs
sumber
3

JavaScript (ES6), 85 byte

a=>a.reduce(([b,c],[d,e,g=(b,c)=>c?g(c,b%c):b,h=g(b*e,c*d),i=g(b*d,h)])=>[b*d/i,h/i])

Lihatlah tidak ada builtin! Tidak diragukan lagi seseorang akan mengalahkan ini menggunakan pendekatan rekursif atau sesuatu.

Neil
sumber
3

Pari / GP , 3 byte, tidak bersaing

lcm

Cobalah online!

alephalpha
sumber
@JungHwanMin Apakah ini berarti bahwa built-in GCD diperbolehkan?
alephalpha
Poin bagus. Ya, selama inputnya hanya bilangan bulat.
JungHwan Min
2

Perl 6 ,  46  42 byte

{[lcm](@_».numerator)/[gcd] @_».denominator}

menguji

{[lcm](($/=@_».nude)[*;0])/[gcd] $/[*;1]}

menguji

Input adalah daftar angka Rasional .

Diperluas:

{ # bare block lambda with implicit parameter list 「@_」

  [lcm](            # reduce using &infix:<lcm>
    (
      $/ = @_».nude # store in 「$/」 a list of the NUmerators and DEnominiators
                    # ((1,2), (3,4))

    )[
      *;            # from all of the first level 「*」,
      0             # but only the 0th of the second level (numerators)
    ]
  )
  /
  [gcd] $/[ *; 1 ]  # gcd of the denominators
}
Brad Gilbert b2gills
sumber
2

Retina , 117 byte

\d+
$*
\b(1+)(\1)*/(\1)+\b
$#2$*11/$#3$*
{`^((1+)\2*)/(1+)+ (\2)+/\3+\b
$1 $#4$*1/$3
}`\G1(?=1* (1+))|\G 1+
$1
1+
$.&

Cobalah online! Mengambil input sebagai serangkaian fraksi yang tidak tepat yang dipisahkan ruang (tidak ada bilangan bulat atau angka campuran). Penjelasan:

\d+
$*

Mengkonversi desimal ke unary.

\b(1+)(\1)*/(\1)+\b
$#2$*11/$#3$*

Ini mengurangi setiap fraksi ke ketentuan terendah. Grup tangkapan 1 menunjukkan GCD pembilang dan penyebut, jadi kami menghitung jumlah tangkapan sebelum dan sesudah /. \b(1+)+/(\1)+\btampaknya tidak menghitung jumlah tangkapan dengan benar karena beberapa alasan, jadi saya menggunakan grup penangkapan tambahan dan menambahkan 1 ke hasilnya.

{`^((1+)\2*)/(1+)+ (\2)+/\3+\b
$1 $#4$*1/$3

Ini melakukan sejumlah hal. Grup tangkap 2 mewakili GCD pembilang dari dua fraksi pertama, sedangkan kelompok tangkap 3 mewakili GCD penyebut. $#4Oleh karena itu pembilang kedua dibagi dengan GCD mereka. (Sekali lagi, saya tidak bisa mendapatkan jumlah tangkapan dari pembilang pertama, tetapi saya hanya perlu membagi satu pembilang dengan GCD mereka, sehingga tidak perlu terlalu mahal.)

}`\G1(?=1* (1+))|\G 1+
$1

Sekarang pembilang kedua telah dibagi oleh GCD mereka, kami hanya menggunakan ungkapan ini dari tutorial aritmatika unary untuk melipatgandakan keduanya, menghasilkan LCM. Kami kemudian mengulangi latihan untuk fraksi yang tersisa.

1+
$.&

Mengubah unary kembali ke desimal.

Neil
sumber
2

Common Lisp, 154 byte

(defun f(l &aux(s(pairlis l l)))(loop(and(eval`(=,@(mapcar'car s)))(return(caar s)))(let((x(assoc(reduce'min s :key'car)s)))(rplaca x(+(car x)(cdr x))))))

Algoritma digunakan (ditentukan untuk bilangan bulat, tetapi berfungsi juga untuk rasional).

Pertama buat daftar asosiatif dari data input dengan dirinya sendiri, untuk melacak nilai awal elemen, sehingga urutan operasi diberikan oleh "mobil" dari daftar.

(defun f(l &aux (s (pairlis l l)))        ; make the associative list
  (loop
     (when (eval `(= ,@(mapcar 'car s))) ; when the car are all equal
       (return (caar s)))                 ; exit with the first one
     (let ((x (assoc (reduce 'min s :key 'car) s))) ; find the (first) least element
       (rplaca x (+ (car x) (cdr x))))))  ; replace its car adding the original value (cdr)

Kasus uji:

CL-USER> (f '(3))
3
CL-USER> (f '(1/17))
1/17
CL-USER> (f '(1/2 3/4))
3/2
CL-USER> (f '(1/3 2/8))
1
CL-USER> (f '(1/4 3))
3
CL-USER> (f '(2/5 3))
6
CL-USER> (f '(1/2 3/4 5/6 7/8))
105/2

Catatan: Solusinya adalah tanpa menggunakan builting lcmdan gcd, yang menerima bilangan bulat.

Renzo
sumber
W00t? Coba ini di REPL Anda (/ (lcm 1 3 5 7) (gcd 2 4 6 8)).
Kaz
@ Ka, karena, seperti yang dikatakan dalam masalah, "Pengajuan yang akan memberi makan nomor rasional ke builtin LCM / GCD diperbolehkan, tetapi non-bersaing".
Renzo
Dalam istilah Lisp, sebenarnya, kita sebenarnya memberi makan rasional ketika kita memanggil (lcm 1 3 5 7), karena bilangan bulat adalah subtipe rasional, tapi saya pikir aturan seharusnya mengecualikan penggunaan lcmatau gcdyang memungkinkan input rasional.
Kaz
@ Ka, ops ... Saya salah menafsirkan aturan! Haruskah saya menghapus posting? (mungkin itu bukan pemasaran yang baik untuk Common Lisp :)
Renzo
Saya baru saja mencatat bahwa ini adalah solusi tanpa menggunakan bilangan bulat bawaan lcmdan gcd.
Kaz
1

Mathematica, 3 byte, tidak bersaing

LCM

LCMFungsi built-in Mathematica mampu menangani input bilangan rasional.

JungHwan Min
sumber
3
Meskipun menjawab pertanyaan Anda sendiri baik-baik saja, saya tidak berpikir itu sangat olahraga untuk menjawabnya dengan solusi yang memiliki peluang sangat nyata untuk menang: P
Beta Decay
@BetaDecay Yap ... Jadi sekarang ini tidak bersaing.
JungHwan Min
1

PHP , 194 byte

<?for(list($n,$d)=$_GET,$p=array_product($d);$x=$n[+$k];)$r[]=$x*$p/$d[+$k++];for($l=1;$l&&++$i;$l=!$l)foreach($r as$v)$l*=$i%$v<1;for($t=1+$i;$p%--$t||$i%$t;);echo$p/$t>1?$i/$t."/".$p/$t:$i/$t;

-4 Bytes dengan PHP> = 7.1 [$n,$d]=$_GETbukanlist($n,$d)=$_GET

Cobalah online!

Jörg Hülsermann
sumber
1

Common Lisp, 87 78 byte

Menggunakan lcmdan gcd, yang memiliki input bilangan bulat:

(defun l(a)(/(apply #'lcm(mapcar #'numerator a))(apply #'gcd(mapcar #'denominator a))))

Lebih banyak bermain golf:

(defun l(a)(eval`(/(lcm,@(mapcar'numerator a))(gcd,@(mapcar'denominator a))))
Kaz
sumber