LCM Рациональных Чисел

18

Наименьшее общее кратное (LCM) набора чисел A- это наименьшее целое число, bтакое что b/aявляется целым числом для всех целых чисел aв A. Это определение можно распространить на рациональные числа!

задача

Найдите наименьшее положительное рациональное b такое, которое b/aявляется целым числом для всех рациональных чисел a во входных данных.

правила

  • Стандартные лазейки запрещены.
  • Вы можете взять числители и знаменатели отдельно во входных данных, но не можете использовать двойные, плавающие и т. Д.
  • Вход не может быть полностью уменьшен.
  • Вы можете принимать целочисленные входные данные как рациональные числа со знаменателем 1.
  • Представления, которые будут передавать рациональные числа во встроенную LCM / GCD, разрешены, но не конкурируют.

Тестовые случаи

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

Это , поэтому заявки, использующие наименьшее количество байтов, выигрывают!

Юнг Хван Мин
источник
4
Примечание: вычисления LCM[numerators]/GCD[denominators]могут не работать, если вход содержит рациональное число без сокращения. например 1/3, 2/8.
ЮнгХван Мин
Так что, если я уменьшу это, это будет работать?
Утренняя монахиня
@ LeakyNun Да, будет.
ЮнгХван Мин
Чтобы побудить людей отправлять не встроенные ответы, я отредактировал вопрос, сделав встроенные ответы неконкурентными (все еще разрешенными). Если это проблема, я вернусь к своему редактированию.
ЮнгХван Мин
Как насчет использования встроенного LCM, но только с целыми числами - конкурирует или нет?
Джонатан Аллан

Ответы:

5

Желе , 19 байт

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

Попробуйте онлайн!

Дрянная Монахиня
источник
1
TFW Jelly сосет с фракциями
Эрик Outgolfer
2
g/:@$€->:g/$€
Джонатан Аллан
2
Сохранить еще два байта с::g/$€ZµḢæl/,Ḣg/$
Джонатан Аллан
@JonathanAllan Это хороший кусок кода ...
Эрик Outgolfer
6

J, 3 байта, не конкурирует.

*./

При наличии списка рациональных входных данных, это перебирает LCM через него.

zgrep
источник
4

sed, 374 (373 + 1) байта

-EФлаг sed считается одним байтом. Примечание: я еще не пробовал играть в гольф, и, вероятно, не буду в течение достаточно долгого времени.
Ввод принимается в унарном виде, а вывод - в унарном. Пробелы должны окружать каждую фракцию. Пример: 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 *,/,

Попробуйте онлайн!

zgrep
источник
3

JavaScript (ES6), 85 байт

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

Не смотри встроенные! Без сомнения, кто-то победит это, используя рекурсивный подход или что-то в этом роде.

Нил
источник
3

Пари / GP , 3 байта, неконкурирующие

lcm

Попробуйте онлайн!

alephalpha
источник
@JungHwanMin Означает ли это, что встроенный GCD разрешен?
алефальфа
Хорошая точка зрения. Да, если его входные данные являются только целыми числами.
ЮнгХван Мин
2

Perl 6 ,  46  42 байта

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

Проверь это

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

Проверь это

Ввод представляет собой список рациональных чисел.

Expanded:

{ # 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
}
Брэд Гилберт b2gills
источник
2

Сетчатка , 117 байт

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

Попробуйте онлайн! Принимает входные данные как разделенные пробелами серии неправильных дробей (без целых или смешанных чисел). Объяснение:

\d+
$*

Преобразует десятичную в одинарную.

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

Это уменьшает каждую фракцию до самых низких сроков. Группа захвата 1 представляет GCD числителя и знаменателя, поэтому мы подсчитываем количество захватов до и после /. \b(1+)+/(\1)+\bкажется, по какой-то причине неправильно подсчитывает количество захватов, поэтому я использую дополнительную группу захвата и добавляю 1 к результату.

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

Это делает несколько вещей. Группа захвата 2 представляет GCD числителей первых двух фракций, в то время как группа захвата 3 представляет GCD знаменателей. $#4поэтому второй числитель делится на их GCD. (Опять же, я не мог определить количество снимков первого числителя, но мне нужно только разделить один числитель по их GCD, так что это не будет стоить мне так много.)

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

Теперь, когда второй числитель разделен на их GCD, мы просто используем это выражение из унарного арифметического учебника, чтобы умножить их вместе, что приводит к LCM. Затем мы повторим упражнение для оставшихся дробей.

1+
$.&

Преобразует унарный обратно в десятичный.

Нил
источник
2

Common Lisp, 154 байта

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

Используемый алгоритм (указан для целых чисел, но работает и для рациональных).

Сначала составьте ассоциативный список входных данных с самим собой, чтобы отследить начальные значения элементов, чтобы рабочая последовательность определялась «машинами» списка.

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

Тестовые случаи:

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

Примечание: решение без использования построения lcmи gcd, которые принимают целые числа.

Renzo
источник
W00t? Попробуйте это на вашем REPL (/ (lcm 1 3 5 7) (gcd 2 4 6 8)).
Каз
@Kaz, поскольку, как сказано в задаче, «представления, которые будут передавать рациональные числа во встроенную LCM / GCD, разрешены, но не конкурируют».
Ренцо
В терминах Лиспа, строго говоря, мы фактически задаем рациональные числа, когда мы вызываем (lcm 1 3 5 7), так как целые числа являются подтипом рациональных чисел, но я думаю, что правило должно исключать использование lcmили, gcdкоторое допускает рациональные входные данные.
Каз
@ Kaz, опс ... Я неправильно истолковал правила! Должен ли я удалить пост? (может быть, это не очень хороший маркетинг для Common Lisp :)
Ренцо
Я бы просто отметил, что это решение без использования встроенного целого числа lcmи gcd.
Каз
1

Mathematica, 3 байта, не конкурирует

LCM

Встроенная LCMфункция Mathematica способна обрабатывать рациональные числовые значения.

Юнг Хван Мин
источник
3
Хотя отвечать на ваш собственный вопрос - это хорошо, я не думаю, что было бы слишком спортивно отвечать на него решением, у которого есть очень реальный шанс на победу: P
Beta Decay
@BetaDecay Да ... Так что теперь он не конкурирует.
ЮнгХван Мин
1

PHP , 194 байта

<?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 байта с PHP> = 7.1 [$n,$d]=$_GETвместоlist($n,$d)=$_GET

Попробуйте онлайн!

Йорг Хюльсерманн
источник
1

Common Lisp, 87 78 байт

Используя lcmи gcd, которые имеют целочисленные входы:

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

Больше игры в гольф:

(defun l(a)(eval`(/(lcm,@(mapcar'numerator a))(gcd,@(mapcar'denominator a))))
Kaz
источник