Продолженные дроби - это выражения, которые описывают дроби итеративно. Они могут быть представлены графически:
Или они могут быть представлены в виде списка значений: [a0; a1, a2, a3, ... an]
Соревнование:
возьмите базовое число: и список значений знаменателя: и упростите непрерывную дробь до упрощенной рациональной дроби: возвращайте или печатайте числитель и знаменатель отдельно.a0
[a1, a2, a3, ... an]
Примеры:
√19 : [4;2,1,3,1,2]: 170/39
ℯ: [1;0,1,1,2,1,1]: 19/7
π: [3;7,15,1,292,1]: 104348/33215
ϕ: [1;1,1,1,1,1]: 13/8
Пример реализации: (python)
def foo(base, sequence):
numerator = 1
denominator = sequence[-1]
for d in sequence[-2::-1]:
temp = denominator
denominator = d * denominator + numerator
numerator = temp
return numerator + base * denominator, denominator
2.002
может быть выражен как2002/1000
. Технически это «единая дробь», вы, вероятно, хотите сказать, «единственная дробь в ее самой простой форме».Ответы:
J,
85 байтТо же самое, что и это , но использует встроенную для рациональных.
Аргументом является {a0, a1, a2, a3, ...} как список J рациональных чисел с расширенной точностью. Результатом является дробь как J рационального числа с повышенной точностью.
(+%)
плюс-взаимность/
сокращение сверхПопробуйте онлайн!
-3 благодаря милям .
источник
∘
.Haskell,
373618 байтЭта функция ожидает
Ratio
тип Haskell в качестве ввода. Пример использования:Примечание: достаточно одного явного
Ratio
в input list (4%1
), системы типов выясняют, что остальные тоже должны бытьRatio
s.Редактировать: @Lynn сохранил байт. Благодарность!
Редактировать II: удалены
import
(см. Это обсуждение на мета ).источник
import
. Однако, чтобы назвать это, вы должны кормитьRatio
его, который действительно нуждается вimport
. Должен ли я добавитьimport
к числу байтов или нет?from fractions import Fraction
для выполнения операций сFraction
объектами также учитывается оператор import.Ratio
которые могут быть построены только через%
, что требует импорта. Обычно мы не считаем байты для вызова служебной информации, просто для самой функции.GolfScript , 13 байт
Попробуйте онлайн!
Yay для скрытых рациональных решений GolfScript . :)
объяснение
Единственный «официальный» тип числа в GolfScript - целые числа. Но оператор возведения в степень не приводит его к целочисленному результату, и удобно, что нативный результат возведения целочисленного значения в Ruby (язык интерпретатора GolfScript) является рациональным числом. Таким образом, мы можем легко получить дроби, подняв что-то до степени -1. Удобно, мы все равно хотим взаимности ...
источник
Mathematica,
2322 байтаПо сути это порт моего ответа на GolfScript . Вот несколько альтернатив:
Для 24 байтов мы можем написать рекурсивную переменную функцию:
Для 21 байта мы можем даже определить «оператор переменной», но его соглашение о вызовах было бы настолько странным, что я не хотел бы считать это:
Вы должны вызывать это с помощью последовательности входных значений, например,
±Sequence[3, 7, 15, 1, 292, 1]
или±##&[3, 7, 15, 1, 292, 1]
.А также для 21 байта, было бы (запрещено) встроенным:
источник
LabVIEW, 36 эквивалентных байтов
Довольно прямолинейная наивная реализация с использованием алгоритма OP. Есть ли лучший способ сделать это?
источник
Dyalog APL , 10 байт
Даже не использует встроенный для рациональных.
Принимает {a 0 , a 1 , a 2 , a 3 , ...} в качестве аргумента, возвращает {знаменатель, числитель}.
1(,÷∨)
1-предваренный-деленный на GCD 1 и+∘÷
плюс заместитель обратной из/
сокращение сверхПопробуй APL онлайн!
источник
Python 2, 62 байта
К сожалению, это не так, как в гольфе (см . Ответ @ xnor для краткости ), но он рассчитывает долю без необходимости реверсирования ввода. При этом используется подход «магический стол» для конвергентов - с учетом последних двух дробей
a/c
иb/d
следующей дроби(n*b+a)/(n*c+d)
.Например, для пи:
Мы можем видеть , что
15*22 + 3 = 333
,15*7 + 1 = 106
,1*333 + 22 = 355
,1*106 + 7 = 113
и т.д.источник
М 5 байт
Вход представляет собой список значений
[a0, a1, ..., aN]
и выводит рациональное число.Попробуйте онлайн! или Проверьте все контрольные примеры.
объяснение
источник
Haskell, 30 байт
Рекурсивно добавляет каждый слой, идущий наружу, обновляя
n/d
доh+(1/(n/d))
, что равноh+d/n
или(h*n+d)/n
. Фракция хранится в виде кортежа(num,denom)
. Начальная доля(1,0)
сальто к0/1
которой есть0
.источник
Python, 50 байт
Создает непрерывную дробь с конца списка, возвращаясь назад, многократно обновляя дробь
n/d
на последнем элементеx
какn/d -> 1+1/(n/d) == (x*n+d)/n
.источник
Common Lisp, 54
Несколько многословный сгиб справа
тесты
источник
Юлия (53 байта)
Я впервые использую Джулию, если я пропустил итератор, который мог бы потерять еще несколько байтов, дайте мне знать. Вот подсказка для любого, кто не знает, какой язык выбрать для этой конкретной задачи: https://en.wikipedia.org/wiki/Rational_data_type
источник
∘
) вместо функцииx∘c=(a=0;while x!=[];a=1//(pop!(x)+a);end;a+c;)
x->foldr((x,y)->x+1//y,x)
(так же, как решение Haskell). использование:(x->foldr((x,y)->x+1//y,x))([4//1,2,1,3,1,2])
Javascript (ES6), 55 байт
Контрольные примеры
источник
CJam ,
1816 байтовОнлайн переводчик .
источник
05AB1E ,
1917 байтобъяснение
Ввод взят в виде списка чисел
Попробуйте онлайн!
источник
JavaScript (ES6), 44 байта
источник
Javascript (ES6), 50 байт
Это благодаря ответу Арно, прежде чем я увидел его, я застрял в 66 байтах:
Пример:
Вызов:
f([1, 0, 1, 1, 2, 1, 1])
Выход:
Array [ 19, 7 ]
источник
Perl 6 , 24 байта
Объяснение:
1 / * + *
лямбда с двумя параметрами (*
), которая берет обратную величину первого и добавляет второй. (возвращает Крысу )R[&(…)]
использует это, как если бы это был инфиксный оператор, и переворачивает его.(в том числе сделать его ассоциативно правильным)
[…](@_)
берет это и использует это, чтобы уменьшить ввод.… .nude
возвращает ню merator и де числитель от Крысы .{ … }
сделать лямбду с пустым блоком с неявным параметром@_
.Использование:
источник
Зефир , 145 байт
Zephyr - первый язык программирования, который я создал. Это было разработано, чтобы быть интуитивным и иметь чистый синтаксис - скорее за счет краткости. Вы спросите, почему я играю в гольф с этим? Потому что, в отличие от любого языка, который я написал с тех пор, он имеет встроенный
Fraction
тип. Вы даже можете использовать оператор деления/
в качестве унарного оператора для «обратного» (функция, которую я позаимствовал для Пипа).Теперь есть значительные ограничения. Самая большая проблема для этой проблемы состоит в том, что массивы должны быть определены с фиксированным размером, что означает, что программа запускается с чтения размера массива от пользователя. (Надеюсь, что все в порядке; альтернативой является жесткое кодирование размера.) Существует также небольшая проблема, заключающаяся в том, что приоритет оператора не существует, то есть выражения с несколькими операторами должны иметь круглые скобки.
Вот пример запуска:
источник
Рубин, 34 байта
При этом выполняется сгибание вправо (путем реверса, а затем сгибания влево), добавление каждого элемента к 1 над промежуточной суммой (элементы справа). В Ruby есть тип Rational, который действительно хорош. И буквальные рациональные числа с суффиксом числа
r
.источник
Stax , 4 байта
Запустите и отладьте его
Как бы он ни был маленьким, он не встроенный. Встроенные рациональные числа помогают совсем немного. Распаковывается в ascii, программа есть
rksu+
.(a, b) => (a + 1/b)
.источник
APL (NARS), 15 + 1 символ, 30 + 2 байта
Перевод в Apl (Nars) из решения Адама J ... вход, разрешенный для этой функции, будет весь список целых чисел, где первый элемент будет иметь тип рациональный. Тест:
так что это будет 15 символов в качестве длины функции и 1 символ для «x» для ввода типа ввода, который я хочу, и выхода из типа, который я хочу ...
источник