LCM de números racionais

18

O mínimo múltiplo comum (LCM) de um conjunto de números Aé o menor número inteiro b, que b/aé um número inteiro para todos os números inteiros aem A. Esta definição pode ser estendida a números racionais!

Tarefa

Encontre o menor racional positivo btal que b/aseja um número inteiro para todos os racionais a na entrada.

Regras

  • As brechas padrão são proibidas.
  • Você pode usar numeradores e denominadores separadamente na entrada, mas não pode usar duplos, flutuadores, etc.
  • A entrada pode não estar totalmente reduzida.
  • Você pode usar entradas inteiras como racionais com denominador de 1.
  • Os envios que alimentariam números racionais para um LCM / GCD embutido são permitidos, mas não são concorrentes.

Casos de teste

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

Isso é , então envios usando o menor número de bytes ganham!

JungHwan Min
fonte
4
Nota: a computação LCM[numerators]/GCD[denominators]pode não funcionar quando a entrada contém um número racional não reduzido. por exemplo 1/3, 2/8.
JungHwan Min 18/06/19
Então, se eu reduzir, funcionará?
Leaky Nun
@LeakyNun Sim, será.
JungHwan Min 18/06/19
Para incentivar as pessoas a enviar respostas não integradas, editei a pergunta, tornando as respostas integradas não concorrentes (ainda permitidas). Se isso for um problema, reverteremos minha edição.
JungHwan Min 18/06/19
Que tal um LCM embutido ser usado, mas apenas com números inteiros - competindo ou não?
Jonathan Allan

Respostas:

5

Geléia , 19 bytes

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

Experimente online!

Freira Furada
fonte
1
tfw geléia suga com fracções de
Erik a Outgolfer
2
g/:@$€->:g/$€
Jonathan Allan
2
Salve outros dois bytes com::g/$€ZµḢæl/,Ḣg/$
Jonathan Allan
@JonathanAllan Isso é um bom pedaço de código ...
Erik o Outgolfer
6

J, 3 bytes, não concorrente.

*./

Dada uma lista de entradas racionais, isso inclui o LCM.

zgrep
fonte
4

sed, 374 (373 + 1) bytes

A -Ebandeira do sed conta como um byte. Nota: ainda não tentei jogar golfe, e provavelmente não vou jogar há algum tempo.
A entrada é recebida em unário e a saída é em unário. Os espaços devem envolver cada fração. Exemplo: 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 *,/,

Experimente online!

zgrep
fonte
4

Python 2 , 65 bytes (não concorrente)

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

Experimente online!

ovs
fonte
3

JavaScript (ES6), 85 bytes

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])

Não procure embutidos! Sem dúvida, alguém vai superar isso usando uma abordagem recursiva ou algo assim.

Neil
fonte
3

Pari / GP , 3 bytes, não concorrente

lcm

Experimente online!

alefalpha
fonte
@JungHwanMin Isso significa que um GCD embutido é permitido?
alephalpha
Bom ponto. Sim, desde que suas entradas sejam apenas números inteiros.
JungHwan Min
2

Perl 6 ,  46  42 bytes

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

teste-o

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

teste-o

Entrada é uma lista de números do Rational .

Expandido:

{ # 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
fonte
2

Retina , 117 bytes

\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+
$.&

Experimente online! Recebe entrada como uma série separada por espaços de frações impróprias (sem números inteiros ou números mistos). Explicação:

\d+
$*

Converte decimal em unário.

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

Isso reduz cada fração aos seus termos mais baixos. O grupo de captura 1 representa o MDC do numerador e denominador, portanto, contamos o número de capturas antes e depois da /. \b(1+)+/(\1)+\bparece não contar o número de capturas corretamente por algum motivo, então eu uso um grupo de captura extra e adiciono 1 ao resultado.

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

Isso faz várias coisas. O grupo de captura 2 representa o CDG dos numeradores das duas primeiras frações, enquanto o grupo de captura 3 representa o CDG dos denominadores. $#4é, portanto, o segundo numerador dividido por seu GCD. (Mais uma vez, não consegui o número de capturas do primeiro numerador, mas só preciso dividir um numerador pelo seu GCD, para que não me custe muito.)

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

Agora que o segundo numerador foi dividido pelo seu GCD, apenas usamos esta expressão do tutorial aritmético unário para multiplicar os dois juntos, resultando no LCM. Em seguida, repetimos o exercício para todas as frações restantes.

1+
$.&

Converte unário de volta para decimal.

Neil
fonte
2

Lisp comum, 154 bytes

(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))))))

Algoritmo usado (especificado para números inteiros, mas funciona também para racionais).

Primeiro faça uma lista associativa dos dados de entrada consigo mesmo, para rastrear os valores iniciais dos elementos, para que a sequência operacional seja dada pelos “carros” da lista.

(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)

Casos de teste:

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

Nota: A solução é sem o uso do builting lcme gcd, que aceita números inteiros.

Renzo
fonte
W00t? Tente isso no seu REPL (/ (lcm 1 3 5 7) (gcd 2 4 6 8)).
Kaz
@Kaz, uma vez que, como foi dito no problema, "envios que alimentariam números racionais para um LCM / GCD embutido são permitidos, mas não concorrentes".
Renzo
Em termos de Lisp, a rigor, estamos alimentando os racionais quando chamamos (lcm 1 3 5 7), pois números inteiros são um subtipo de racionais, mas acho que a regra deve excluir o uso de a lcmou gcdque permite entradas racionais.
`
@Kaz, ops ... interpretei mal as regras! Devo remover a postagem? (talvez não seja um bom marketing para Common Lisp :)
Renzo
Eu apenas colocaria uma nota que esta é uma solução sem usar o número inteiro interno lcme gcd.
Kaz
1

Mathematica, 3 bytes, não concorrente

LCM

Mathematica de built-in LCMfunção é capaz de lidar com as entradas dos números racionais.

JungHwan Min
fonte
3
Embora responder a sua própria pergunta seja bom, não acho muito esportivo respondê-la com uma solução com chances muito reais de vencer: P
Beta Decay
@BetaDecay Sim ... Portanto, não está competindo agora.
JungHwan Min
1

PHP , 194 bytes

<?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 com PHP> = 7.1 em [$n,$d]=$_GETvez delist($n,$d)=$_GET

Experimente online!

Jörg Hülsermann
fonte
1

Lisp comum, 87 78 bytes

Usando lcme gcd, que possuem entradas inteiras:

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

Mais jogado:

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