Упростить продолжение дроби

21

Продолженные дроби - это выражения, которые описывают дроби итеративно. Они могут быть представлены графически:

введите описание изображения здесь

Или они могут быть представлены в виде списка значений: [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. Технически это «единая дробь», вы, вероятно, хотите сказать, «единственная дробь в ее самой простой форме».
Волшебная урна осьминога
@carusocomputing точка взята .. хотя я бы не чувствовал себя слишком плохо в отношении 2/4 (или аналогичного), так как он все еще упростил структуру с несколькими фракциями до одной фракции
Aaron
Хм ... Я думаю, что есть способ использовать это, но с 13-байтовым ответом на сценарий игры в гольф мне, вероятно, придется использовать MATL, чтобы выиграть.
Волшебная Урна Осьминога
@carusocomputing Я бы сказал, пойти на это ... Если вы можете побить 13-байтовый ответ, это было бы здорово
Аарон
Вы можете сделать остановку пи раньше - 355/113.
Турбьерн Равн Андерсен

Ответы:

15

J, 8 5 байт

То же самое, что и это , но использует встроенную для рациональных.

Аргументом является {a0, a1, a2, a3, ...} как список J рациональных чисел с расширенной точностью. Результатом является дробь как J рационального числа с повышенной точностью.

(+%)/

(+%) плюс-взаимность

/ сокращение сверх

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

-3 благодаря милям .

Адам
источник
Если вы берете входные данные как список расширенных целых чисел, вы можете сохранить 3 байта. Также вы использовали раздел APL в объяснении.
миль
@ Майлз Спасибо. Не могу приблизиться к встроенному запрету. Жаль, что у J нет такого персонажа, как Dyalog APL .
августа
Ссылка на попытку J не работает
Chiel ten Brinke
@ChieltenBrinke Спасибо. Исправлена.
Адам
12

Haskell, 37 36 18 байт

foldr1$(.(1/)).(+)

Эта функция ожидает Ratioтип Haskell в качестве ввода. Пример использования:

Prelude Data.Ratio> ( foldr1$(.(1/)).(+) )  [4%1,2,1,3,1,2] 
170 % 39

Примечание: достаточно одного явного Ratioв input list ( 4%1), системы типов выясняют, что остальные тоже должны быть Ratios.

Редактировать: @Lynn сохранил байт. Благодарность!

Редактировать II: удалены import(см. Это обсуждение на мета ).

Ними
источник
1
Ооо, хороший крайний случай. Сама функция полиморфна, поэтому ей не нужно import. Однако, чтобы назвать это, вы должны кормить Ratioего, который действительно нуждается в import. Должен ли я добавить importк числу байтов или нет?
Ними,
1
Это звучит как хороший вопрос для мета.
Мартин Эндер
Я никогда не использовал Haskell, так что поправьте меня, если я ошибаюсь, но если Python равнозначен: from fractions import Fractionдля выполнения операций с Fractionобъектами также учитывается оператор import.
Аарон
.. у нас было это раньше .
Ними,
@ Аарон: проблема в том, что определение функции не нуждается в импорте, потому что оно полиморфно. Когда вы хотите позвонить, вам нужно предоставить номера типа, Ratioкоторые могут быть построены только через %, что требует импорта. Обычно мы не считаем байты для вызова служебной информации, просто для самой функции.
Ними,
11

GolfScript , 13 байт

~]-1%{\-1?+}*

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

Yay для скрытых рациональных решений GolfScript . :)

объяснение

Единственный «официальный» тип числа в GolfScript - целые числа. Но оператор возведения в степень не приводит его к целочисленному результату, и удобно, что нативный результат возведения целочисленного значения в Ruby (язык интерпретатора GolfScript) является рациональным числом. Таким образом, мы можем легко получить дроби, подняв что-то до степени -1. Удобно, мы все равно хотим взаимности ...

~]     # Evaluate input and wrap all a_i in a list.
-1%    # Reverse the list so that a_n is at the start and a_0 at the end.
{      # Fold... (apply this block to each element from a_n-1 down to a_0, with
       # the previous result on the stack)
  \    #   Swap previous result with current a_i.
  -1?  #   Raise previous result to the power of -1, computing its reciprocal
       #   as a rational number.
  +    #   Add a_i.
}*
Мартин Эндер
источник
11

Mathematica, 23 22 байта

Fold[#2+1/#&]@*Reverse

По сути это порт моего ответа на GolfScript . Вот несколько альтернатив:

Для 24 байтов мы можем написать рекурсивную переменную функцию:

f@n_=n
n_~f~m__:=n+1/f@m

Для 21 байта мы можем даже определить «оператор переменной», но его соглашение о вызовах было бы настолько странным, что я не хотел бы считать это:

±n_=n
n_ ±m__:=n+1/±m

Вы должны вызывать это с помощью последовательности входных значений, например, ±Sequence[3, 7, 15, 1, 292, 1]или ±##&[3, 7, 15, 1, 292, 1].

А также для 21 байта, было бы (запрещено) встроенным:

FromContinuedFraction
Мартин Эндер
источник
10

LabVIEW, 36 эквивалентных байтов

Довольно прямолинейная наивная реализация с использованием алгоритма OP. Есть ли лучший способ сделать это?

введите описание изображения здесь

ijustlovemath
источник
5
Ваша электротехническая степень показывает.
Волшебная Урна Осьминога
1
@ijustlovemath Реквизит, но ..... актуально
Аарон
Да, это спорный язык, чтобы быть уверенным. Я вижу LabVIEW как «я ненавижу математику» мира программистов. Проблема не в самой математике, а в том, как ее учат (или часто в отсутствии обучения).
16:02
6

Dyalog APL , 10 байт

Даже не использует встроенный для рациональных.

Принимает {a 0 , a 1 , a 2 , a 3 , ...} в качестве аргумента, возвращает {знаменатель, числитель}.

1(,÷∨)+∘÷/

1(,÷∨) 1-предваренный-деленный на GCD 1 и

+∘÷ плюс заместитель обратной из

/ сокращение сверх

Попробуй APL онлайн!

Адам
источник
6

Python 2, 62 байта

a=d=0
b=c=1
for n in input():a,b=b,n*b+a;c,d=d,n*d+c
print b,d

К сожалению, это не так, как в гольфе (см . Ответ @ xnor для краткости ), но он рассчитывает долю без необходимости реверсирования ввода. При этом используется подход «магический стол» для конвергентов - с учетом последних двух дробей a/cи b/dследующей дроби (n*b+a)/(n*c+d).

Например, для пи:

          3    7    15     1      292        1

  0   1   3   22   333   355   103993   104348
  1   0   1    7   106   113    33102    33215

Мы можем видеть , что 15*22 + 3 = 333, 15*7 + 1 = 106, 1*333 + 22 = 355, 1*106 + 7 = 113и т.д.

Sp3000
источник
4

М 5 байт

Ṛİ+¥/

Вход представляет собой список значений [a0, a1, ..., aN]и выводит рациональное число.

Попробуйте онлайн! или Проверьте все контрольные примеры.

объяснение

Ṛİ+¥/  Input: list A
Ṛ      Reverse A
    /  Reduce A from left to right using
   ¥     A dyadic chain
 İ         Take the reciprocal of the left value
  +        Add the reciprocal to the right value
       Return and print implicitly
миль
источник
1
Что это? Какой-нибудь новый желейный диалект?
августа
@miles на самом деле 9 байтов извините :(
Аарон
@ Adám Это старая вилка из желе, предназначенная для математики и символики. Вот его репозиторий Github .
миль
1
@Aaron M использует ту же кодовую страницу, что и Jelly, и она может быть закодирована с использованием байта для каждого символа.
миль
@Miles хорошо, добавил .
Адам
4

Haskell, 30 байт

foldr(\h(n,d)->(h*n+d,n))(1,0)

Рекурсивно добавляет каждый слой, идущий наружу, обновляя n/dдо h+(1/(n/d)), что равно h+d/nили (h*n+d)/n. Фракция хранится в виде кортежа (num,denom). Начальная доля (1,0)сальто к 0/1которой есть 0.

XNOR
источник
3

Python, 50 байт

f=lambda l,n=1,d=0:l and f(l,l.pop()*n+d,n)or(n,d)

Создает непрерывную дробь с конца списка, возвращаясь назад, многократно обновляя дробь n/dна последнем элементе xкак n/d -> 1+1/(n/d) == (x*n+d)/n.

XNOR
источник
3

 Common Lisp, 54

Несколько многословный сгиб справа

(lambda(s)(reduce(lambda(a r)(+(/ r)a))s :from-end t))

тесты

PASS  NAME  ACTUAL               EXPECTED
===============================================
T     √19   170/39               170/39              
T     ℯ     19/7                 19/7                
T     π     104348/33215         104348/33215        
T     ϕ     13/8                 13/8                
CoreDump
источник
2

Юлия (53 байта)

Я впервые использую Джулию, если я пропустил итератор, который мог бы потерять еще несколько байтов, дайте мне знать. Вот подсказка для любого, кто не знает, какой язык выбрать для этой конкретной задачи: https://en.wikipedia.org/wiki/Rational_data_type

f(x,c)=(a=0;for b in x[end:-1:1];a=1//(b+a);end;a+c;)
  • Обратный входной массив.
  • Итерируйте это с рациональным делением.
  • Добавьте c к десятичному результату.
Урна волшебного осьминога
источник
Вы можете сохранить два байта, определив оператор (например ) вместо функции
Tasos Papastylianou
также, поменяйте цикл for на некоторое время и поп:x∘c=(a=0;while x!=[];a=1//(pop!(x)+a);end;a+c;)
Tasos Papastylianou
1
25: x->foldr((x,y)->x+1//y,x)(так же, как решение Haskell). использование:(x->foldr((x,y)->x+1//y,x))([4//1,2,1,3,1,2])
Фэнъян Ван
Ооо ... Функция обратного складывания? Это красиво! Я не заслуживаю признания за это, хотя, ха-ха.
Волшебная Урна Осьминога
2

Javascript (ES6), 55 байт

s=>eval('for(F=[1,0];s+"";)F=[s.pop()*F[0]+F[1],F[0]]')

Контрольные примеры

var f =
s=>eval('for(F=[1,0];s+"";)F=[s.pop()*F[0]+F[1],F[0]]')

console.log(f([4, 2, 1, 3, 1, 2]));
console.log(f([1, 0, 1, 1, 2, 1, 1]));
console.log(f([3, 7, 15, 1, 292, 1]));
console.log(f([1, 1, 1, 1, 1, 1]));

Arnauld
источник
2

CJam , 18 16 байтов

XUq~W%{2$*+\}/]p

Онлайн переводчик .

XU                  Push 1 and 0 to the stack
  q~W%              Push input, eval and reverse it
      {     }/      For each n in the reversed input...
       2$             Copy numerator
         *+           Calculate n*denominator + numerator
           \          Swap numerator and denominator
              ]p   Wrap in array and output
Sp3000
источник
2

05AB1E , 19 17 байт

R¬V¦vyY*X+YUV}YX)

объяснение

Ввод взят в виде списка чисел

                     # variable X is initialized as 1
R¬V¦                 # reverse the list, remove the first item and store it in variable Y
    v        }       # for each item N left in list
     yY*X+  V        # store N*Y+X in Y
          YU         # store Y in X
              YX)    # wrap X and Y in a list

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

Emigna
источник
2

JavaScript (ES6), 44 байта

a=>a.reduceRight(([n,d],v)=>[v*n+d,n],[1,0])
Нил
источник
1

Javascript (ES6), 50 байт

f=(s,n=1,d=s.pop())=>s+""?f(s,d,s.pop()*d+n):[d,n]

Это благодаря ответу Арно, прежде чем я увидел его, я застрял в 66 байтах:

f=(b,s,i=s.length-1,n=1,d=s[i])=>i?f(b,s,--i,d,s[i]*d+n):[n+b*d,d]

Пример:
Вызов: f([1, 0, 1, 1, 2, 1, 1])
Выход:Array [ 19, 7 ]

Хеди
источник
1

Perl 6 , 24 байта

{[R[&(1/*+*)]](@_).nude}

Объяснение:

  • 1 / * + *лямбда с двумя параметрами ( *), которая берет обратную величину первого и добавляет второй. (возвращает Крысу )

  • R[&(…)]использует это, как если бы это был инфиксный оператор, и переворачивает его.
    (в том числе сделать его ассоциативно правильным)

  • […](@_) берет это и использует это, чтобы уменьшить ввод.

  • … .nudeвозвращает ню merator и де числитель от Крысы .

  • { … }сделать лямбду с пустым блоком с неявным параметром @_.

Использование:

say {[R[&(1/*+*)]](@_).nude}(3,7,15,1,292,1) #*/# (104348 33215)

my &code = {[R[&(1/*+*)]](@_).nude}; # stupid highlighter */

say code 4,2,1,3,1,2;    # (170 39)
say code 1,0,1,1,2,1,1;  # (19 7)
say code 1,1,1,1,1,1;    # (13 8)
Брэд Гилберт b2gills
источник
1

Зефир , 145 байт

input n as Integer
set a to Array(n)
for i from 1to n
input a[i]as Integer
next
set r to a[n]
for i from 1to n-1
set r to(/r)+a[n-i]
next
print r

Zephyr - первый язык программирования, который я создал. Это было разработано, чтобы быть интуитивным и иметь чистый синтаксис - скорее за счет краткости. Вы спросите, почему я играю в гольф с этим? Потому что, в отличие от любого языка, который я написал с тех пор, он имеет встроенный Fractionтип. Вы даже можете использовать оператор деления /в качестве унарного оператора для «обратного» (функция, которую я позаимствовал для Пипа).

Теперь есть значительные ограничения. Самая большая проблема для этой проблемы состоит в том, что массивы должны быть определены с фиксированным размером, что означает, что программа запускается с чтения размера массива от пользователя. (Надеюсь, что все в порядке; альтернативой является жесткое кодирование размера.) Существует также небольшая проблема, заключающаяся в том, что приоритет оператора не существует, то есть выражения с несколькими операторами должны иметь круглые скобки.

Вот пример запуска:

C:\Zephyr> python zephyr.py contfrac.zeph
6
1
1
1
1
1
1
13/8
DLosc
источник
1

Рубин, 34 байта

->a{a.reverse.inject{|b,i|i+1r/b}}

При этом выполняется сгибание вправо (путем реверса, а затем сгибания влево), добавление каждого элемента к 1 над промежуточной суммой (элементы справа). В Ruby есть тип Rational, который действительно хорош. И буквальные рациональные числа с суффиксом числа r.

IMP1
источник
1

Stax , 4 байта

╣╩┼►

Запустите и отладьте его

Как бы он ни был маленьким, он не встроенный. Встроенные рациональные числа помогают совсем немного. Распаковывается в ascii, программа есть rksu+.

  1. Обратный массив.
  2. Сложите массив, используя (a, b) => (a + 1/b).
рекурсивный
источник
1

APL (NARS), 15 + 1 символ, 30 + 2 байта

{1=≢⍵:↑⍵⋄+∘÷/⍵}

Перевод в Apl (Nars) из решения Адама J ... вход, разрешенный для этой функции, будет весь список целых чисел, где первый элемент будет иметь тип рациональный. Тест:

  f←{1=≢⍵:↑⍵⋄+∘÷/⍵}      
  f 4x 2 1 3 1 2
170r39 
  f 1x 0 1 1 2 1 1
19r7 
  f 3x 7 15 1 292 1
104348r33215 
  f 1x 1 1 1 1 1
13r8 
  f 3x 89 888 999 11 222 373 7282 9272 3839 2828 
158824716824887954093160207727r52744031585005490644982548907 
  f ,0x
0 
  f ,9x
9 

так что это будет 15 символов в качестве длины функции и 1 символ для «x» для ввода типа ввода, который я хочу, и выхода из типа, который я хочу ...

RosLuP
источник