Последовательности двоичных повторений

10

Бинарная рекуррентная последовательность является рекурсивно определенной последовательностью следующего вида:

определение последовательности двоичных повторений

Это обобщение последовательности Фибоначчи ( x = 1, y = 2, a = [1, 1], alpha = 1, beta = 1) и последовательности Лукаса ( x = 1, y = 2, a = [2, 1], alpha = 1, beta = 1).

Соревнование

Принимая во внимание n, x, y, a, alpha, и beta, в любом подходящем формате, выводить nй член соответствующей двоичной последовательности повторения.

правила

  • Вы можете выбрать последовательность с 1 или 0 индексами, но ваш выбор должен быть одинаковым для всех входных данных, и вы должны отметить свой выбор в своем ответе.
  • Вы можете предположить, что недопустимые входные данные не будут предоставлены (например, последовательность, которая заканчивается до nили последовательность, которая ссылается на неопределенные термины, например F(-1)или F(k)где k > n). В результате этого xи yвсегда будет позитив.
  • Входные и выходные данные всегда будут целыми числами, в границах естественного целочисленного типа вашего языка. Если ваш язык имеет неограниченные целые числа, входы и выходы будут в пределах диапазона [2**31, 2**31-1](т. Е. Диапазона для 32-разрядного целого числа с двоичным знаком со знаком).
  • aвсегда будет содержать точно yзначения (согласно определению).

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

Примечание. Все тестовые примеры имеют индекс 0.

x = 1, y = 2, a = [1, 1], alpha = 1, beta = 1, n = 6 => 13
x = 1, y = 2, a = [2, 1], alpha = 1, beta = 1, n = 8 => 47
x = 3, y = 5, a = [2, 3, 5, 7, 11], alpha = 2, beta = 3, n = 8 => 53
x = 1, y = 3, a = [-5, 2, 3], alpha = 1, beta = 2, n = 10 => -67
x = 5, y = 7, a = [-5, 2, 3, -7, -8, 1, -9], alpha = -10, beta = -7, n = 10 => 39
Mego
источник
Считает ли aразумным принятие в обратном порядке?
Деннис
@ Денис Да, это так.
Мего
ОК, спасибо за разъяснения.
Деннис

Ответы:

2

Желе , 11 байт

⁴Cịæ.⁵ṭµ¡⁶ị

Попробуйте онлайн!  1  |  2  |  3  |  4  |  5 

Как это работает

⁴Cịæ.⁵ṭµ¡⁶ị  Main link. Arguments: a; [x, y]; [α, β]; n (1-based)

       µ     Combine the links to the left into a chain.
        ¡    Execute that chain n times, updating a after each execution.
⁴              Yield [x, y].
 C             Complement; yield [1 - x, 1 - y].
  ị            Retrieve the elements of a at those indices.
               Indexing is 1-based and modular in Jelly, so this retrieves
               [a[-x], a[-y]] (Python syntax).
     ⁵         Yield [α, β].
   æ.          Take the dot product of [a[-x], a[-y]] and [α, β].
         ⁶   Yield n.
          ị  Retrieve the element of a at index n.
Деннис
источник
2

Python 2, 62 байта

x,y,l,a,b=input();f=lambda n:l[n]if n<y else a*f(n-x)+b*f(n-y)

Прямое рекурсивное решение. Все входные данные взяты из STDIN, кроме nкак в качестве аргумента функции, разделение, которое разрешено по умолчанию (хотя и постоянно).

Кажется, нет способа сохранить байты с помощью and/orвместо, if/elseпотому что l[n]может быть ложным, как 0.

XNOR
источник
2

Python 2, 59 байт

x,y,A,a,b,n=input()
exec'A+=a*A[-x]+b*A[-y],;'*n
print A[n]

Проверьте это на Ideone .

Деннис
источник
2

JavaScript (ES6), 51 44 байта

(x,y,z,a,b)=>g=n=>n<y?z[n]:a*g(n-x)+b*g(n-y)

Обратите внимание, что функция частично каррирована, например f(1,2,[1,1],1,1)(8)возвращает 34. Было бы стоить 2 байта, чтобы сделать промежуточные функции независимыми друг от друга (в настоящее время корректно работает только последняя сгенерированная функция).

Изменить: Сохранено 7 байт благодаря @Mego, указав, что я упустил из виду, что переданный массив всегда содержит первые yэлементы результата.

Нил
источник
@ Мне известно, что я часто пропускаю детали вопросов, но этот вопрос показался мне особенно тонким.
Нил
2

Haskell, 54 48 байтов

l@(x,y,a,p,q)%n|n<y=a!!n|k<-(n-)=p*l%k x+q*l%k y
Damien
источник
0

J, 43 байта

{:{](],(2>@{[)+/ .*]{~1-@>@{[)^:(3>@{[)>@{.

Учитывая начальную последовательность слагаемых A , вычисляет следующий слагаемый n раз, используя параметры x , y , α и β . После этого он выбирает n- й член в расширенной последовательности и выводит его в качестве результата.

Применение

Поскольку J поддерживает только 1 или 2 аргумента, я группирую все параметры в виде списка в штучной упаковке. Начальные начальные значения A являются первыми, за которыми следуют параметры x и y в виде списка, за которыми следуют параметры α и β в виде списка, и заканчивающиеся значением n .

   f =: {:{](],(2>@{[)+/ .*]{~1-@>@{[)^:(3>@{[)>@{.
   2 3 5 7 11;3 5;2 3;8
┌──────────┬───┬───┬─┐
│2 3 5 7 11│3 5│2 3│8│
└──────────┴───┴───┴─┘
   f 2 3 5 7 11;3 5;2 3;8
53
   f _5 2 3 _7 _8 1 _9;5 7;_10 _7;10
39
миль
источник