Binarne sekwencje powtarzania

10

Binarna sekwencja rekurencyjna to rekurencyjnie zdefiniowana sekwencja następującej postaci:

binarna definicja sekwencji rekurencyjnej

Jest to uogólnienie x = 1, y = 2, a = [1, 1], alpha = 1, beta = 1sekwencji Fibonacciego ( ) i sekwencji Lucas ( x = 1, y = 2, a = [2, 1], alpha = 1, beta = 1).

Wyzwanie

Biorąc pod uwagę n, x, y, a, alpha, i betaw każdym rozsądnym formacie wyjście nth określenie odpowiedniego binarnej sekwencji nawrotów.

Zasady

  • Możesz wybrać, aby sekwencja była indeksowana 1 lub 0, ale twój wybór musi być spójny dla wszystkich danych wejściowych i musisz zanotować swój wybór w swojej odpowiedzi.
  • Możesz założyć, że nie zostaną podane żadne nieprawidłowe dane wejściowe (takie jak sekwencja, która kończy się przed nlub sekwencja, która odwołuje się do niezdefiniowanych terminów, takich jak F(-1)lub F(k)gdzie k > n). W wyniku tego xi yzawsze będzie pozytywny.
  • Wejścia i wyjścia będą zawsze liczbami całkowitymi, w granicach naturalnych liczb całkowitych twojego języka. Jeśli twój język ma nieograniczone liczby całkowite, wejścia i wyjścia będą się mieścić w zakresie [2**31, 2**31-1](tj. Zakresie liczby całkowitej z dopełnieniem dwóch znaków ze znakiem 32-bitowym).
  • azawsze będzie zawierał dokładnie ywartości (zgodnie z definicją).

Przypadki testowe

Uwaga: wszystkie przypadki testowe mają indeks 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
źródło
Czy przyjęcie aw odwrotnej kolejności jest uzasadnione?
Dennis
@Dennis Tak, to prawda.
Mego,
OK, dziękuję za wyjaśnienie.
Dennis

Odpowiedzi:

2

Galaretka , 11 bajtów

⁴Cịæ.⁵ṭµ¡⁶ị

Wypróbuj online!  1  |  2  |  3  |  4  |  5 

Jak to działa

⁴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.
Dennis
źródło
2

Python 2, 62 bajty

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

Bezpośrednie rozwiązanie rekurencyjne. Wszystkie dane wejściowe są pobierane z STDIN, z wyjątkiem nargumentu funkcji, który jest domyślnie dozwolony (choć sporny).

Wydaje się, że nie ma sposobu na zaoszczędzenie bajtów and/orzamiast, if/elseponieważ l[n]może być falsey jako 0.

xnor
źródło
2

Python 2, 59 bajtów

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

Przetestuj na Ideone .

Dennis
źródło
2

JavaScript (ES6), 51 44 bajtów

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

Zauważ, że funkcja jest częściowo curry, np. f(1,2,[1,1],1,1)(8)Zwraca 34. Kosztowałoby 2 bajty, aby uniezależnić funkcje pośrednie od siebie (obecnie tylko ostatnia funkcja generowana działa poprawnie).

Edycja: Zapisano 7 bajtów dzięki @Mego wskazując, że przeoczyłem, że przekazana tablica zawsze zawiera pierwsze yelementy wyniku.

Neil
źródło
@Mego Wiem, że często pomijam szczegóły pytań, ale to wydało mi się szczególnie subtelne.
Neil
2

Haskell, 54 48 bajtów

l@(x,y,a,p,q)%n|n<y=a!!n|k<-(n-)=p*l%k x+q*l%k y
Damien
źródło
0

J, 43 bajty

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

Biorąc pod uwagę początkową sekwencję terminów A , oblicza następny termin n razy przy użyciu parametrów x , y , α i β . Następnie wybiera n- ty składnik w sekwencji rozszerzonej i wysyła go jako wynik.

Stosowanie

Ponieważ J obsługuje tylko 1 lub 2 argumenty, pogrupowałem wszystkie parametry jako listę list w ramkach. Początkowe wartości początkowe A są pierwsze, po których następują parametry x i y jako lista, a następnie parametry α i β jako lista, kończące się na wartości 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
mile
źródło