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 a
em A
. Esta definição pode ser estendida a números racionais!
Tarefa
Encontre o menor racional positivo b
tal que b/a
seja 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 é código-golfe , então envios usando o menor número de bytes ganham!
code-golf
number
arithmetic
rational-numbers
JungHwan Min
fonte
fonte
LCM[numerators]/GCD[denominators]
pode não funcionar quando a entrada contém um número racional não reduzido. por exemplo1/3, 2/8
.Respostas:
Geléia , 19 bytes
Experimente online!
fonte
g/:@$€
->:g/$€
:g/$€ZµḢæl/,Ḣg/$
J, 3 bytes, não concorrente.
Dada uma lista de entradas racionais, isso inclui o LCM.
fonte
sed, 374 (373 + 1) bytes
A
-E
bandeira 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 "
.Experimente online!
fonte
Python 2 , 65 bytes (não concorrente)
Experimente online!
fonte
JavaScript (ES6), 85 bytes
Não procure embutidos! Sem dúvida, alguém vai superar isso usando uma abordagem recursiva ou algo assim.
fonte
Pari / GP , 3 bytes, não concorrente
Experimente online!
fonte
Perl 6 ,
4642 bytesteste-o
teste-o
Entrada é uma lista de números do Rational .
Expandido:
fonte
Retina , 117 bytes
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:
Converte decimal em unário.
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)+\b
parece 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.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.)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.
Converte unário de volta para decimal.
fonte
Lisp comum, 154 bytes
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.
Casos de teste:
Nota: A solução é sem o uso do builting
lcm
egcd
, que aceita números inteiros.fonte
(/ (lcm 1 3 5 7) (gcd 2 4 6 8))
.(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 alcm
ougcd
que permite entradas racionais.lcm
egcd
.Mathematica, 3 bytes, não concorrente
Mathematica de built-in
LCM
função é capaz de lidar com as entradas dos números racionais.fonte
PHP , 194 bytes
-4 bytes com PHP> = 7.1 em
[$n,$d]=$_GET
vez delist($n,$d)=$_GET
Experimente online!
fonte
Lisp comum,
8778 bytesUsando
lcm
egcd
, que possuem entradas inteiras:Mais jogado:
fonte