Secuencias de recurrencia binaria

10

Una secuencia de recurrencia binaria es una secuencia definida recursivamente de la siguiente forma:

definición de secuencia de recurrencia binaria

Esta es una generalización de la x = 1, y = 2, a = [1, 1], alpha = 1, beta = 1secuencia de Fibonacci ( ) y la secuencia de Lucas ( x = 1, y = 2, a = [2, 1], alpha = 1, beta = 1).

El reto

Dada n, x, y, a, alpha, y beta, en cualquier formato razonable, salida de la nésimo término de la secuencia de recurrencia binario correspondiente.

Reglas

  • Puede elegir que la secuencia sea indexada en 1 o indexada en 0, pero su elección debe ser coherente en todas las entradas y debe tomar nota de su elección en su respuesta.
  • Puede suponer que no se darían entradas inválidas (como una secuencia que termina antes no una secuencia que hace referencia a términos indefinidos, como F(-1)o F(k)dónde k > n). Como resultado de esto, xy ysiempre será positivo.
  • Las entradas y salidas siempre serán números enteros, dentro de los límites del tipo entero natural de su idioma. Si su idioma tiene enteros ilimitados, las entradas y salidas estarán dentro del rango [2**31, 2**31-1](es decir, el rango para un entero de dos con signo de 32 bits).
  • asiempre contendrá exactamente los yvalores (según la definición).

Casos de prueba

Nota: todos los casos de prueba están indexados a 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
fuente
¿Tomar aen orden inverso cuenta como razonable?
Dennis
@ Dennis Sí, lo hace.
Mego
OK, gracias por aclarar.
Dennis

Respuestas:

2

Jalea , 11 bytes

⁴Cịæ.⁵ṭµ¡⁶ị

Pruébalo en línea!  1  |  2  |  3  |  4  |  5 5 

Cómo funciona

⁴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
fuente
2

Python 2, 62 bytes

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

Una solución recursiva directa. Todas las entradas se toman de STDIN, excepto ncomo argumento de función, una división que está permitida de manera predeterminada (aunque contenciosa).

No parece haber una manera de guardar bytes and/oren lugar de if/elseporque l[n]podría ser falsey como 0.

xnor
fuente
2

Python 2, 59 bytes

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

Pruébelo en Ideone .

Dennis
fuente
2

JavaScript (ES6), 51 44 bytes

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

Tenga en cuenta que la función tiene un currículum parcial, por ejemplo, f(1,2,[1,1],1,1)(8)devuelve 34. Costaría 2 bytes hacer que las funciones intermedias sean independientes entre sí (actualmente solo la última función generada funciona correctamente).

Editar: ahorré 7 bytes gracias a @Mego que señaló que había pasado por alto que la matriz que se pasa siempre contiene los primeros yelementos del resultado.

Neil
fuente
@Mego Sé que a menudo paso por alto los detalles de las preguntas, pero esa me pareció particularmente sutil.
Neil
2

Haskell, 54 48 bytes

l@(x,y,a,p,q)%n|n<y=a!!n|k<-(n-)=p*l%k x+q*l%k y
Damien
fuente
0

J, 43 bytes

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

Dada una secuencia inicial de términos A , calcula el siguiente término n veces usando los parámetros de x , y , α y β . Posteriormente, se selecciona el n º término de la secuencia extendida y la emite como el resultado.

Uso

Como J solo admite 1 o 2 argumentos, agrupo todos los parámetros como una lista de listas en recuadro. Los valores iniciales A son primero, seguidos por los parámetros de x e y como una lista, seguidos por los parámetros de α y β como una lista, y terminando con el valor 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
millas
fuente