Si escribimos una secuencia de números como los coeficientes de una serie de potencias, entonces esa serie de potencia se denomina función generadora (ordinaria) (o Gf) de esa secuencia. Es decir, si para alguna función F(x)
y serie de enteros a(n)
tenemos:
a(0) + a(1)x + a(2)x^2 + a(3)x^3 + a(4)x^4 + ... = F(x)
Entonces F(x)
es la función generadora de a
. Por ejemplo, la serie geométrica nos dice que:
1 + x + x^2 + x^3 + x^4 + ... = 1/(1-x)
Entonces la función generadora de 1, 1, 1, ...
es 1/(1-x)
. Si diferenciamos ambos lados de la ecuación anterior y multiplicamos por x
, obtenemos la siguiente igualdad:
x + 2x^2 + 3x^3 + 4x^4 + ... = x/(1-x)^2
Entonces la función generadora de 1, 2, 3, ...
es x/(1-x)^2
. Generar funciones es una herramienta muy poderosa, y puede hacer muchas cosas útiles con ellas. Aquí se puede encontrar una breve introducción , pero para una explicación realmente exhaustiva existe la sorprendente función de generación de libros.
En este desafío, tomará una función racional (el cociente de dos polinomios con coeficientes enteros) como entrada como dos conjuntos de coeficientes enteros, primero el numerador y luego el denominador. Por ejemplo, la función f(x) = x / (1 - x - x^2)
se codificará como [0, 1], [1, -1, -1]
en la entrada.
Dada esta entrada, su programa debe imprimir infinitamente los coeficientes de la serie de potencia que equivale a la función de generación, uno por línea, comenzando en el coeficiente de x
, luego x^2
, etc.
Ejemplos:
[1], [1, -1] -> 1, 1, 1, 1, 1, 1, 1, ...
[1], [2, -2] -> 0.5, 0.5, 0.5, 0.5, 0.5, 0.5, 0.5, ...
[0, 1], [1, -2, 1] -> 1, 2, 3, 4, 5, 6, 7, 8, ...
[0, 1], [1, -1, -1] -> 1, 1, 2, 3, 5, 8, 13, 21, 34, ...
[1], [1, -2] -> 1, 2, 4, 8, 16, 32, 64, 128, ...
[0, 1, 1], [1, -3, 3, -1] -> 1, 4, 9, 16, 25, 36, ...
fuente
Respuestas:
Haskell , 63 bytes
Pruébalo en línea!
Define un operador que
%
devuelve una lista infinita de coeficientes perezosos. La lista está indexada a cero, por lo que se incluye el coeficiente constante.fuente
Mathematica, 64
8390bytesGracias a @ngenisis y @Jenny_mathy!
Tome la entrada como dos listas.
Necesita
Alt+.
terminar la ejecución para ver el resultado. La interfaz puede bloquearse debido a la salida rápida.Versión de 83 bytes (@Jenny_mathy):
fuente
64
bytes:Do[Echo@Limit[D[#/#2/i!&@@Fold[x#+#2&]/@#,{x,i}],x->0],{i,∞}]&
. Esto supone que la entrada es una lista de dos listas y los coeficientes están en orden descendente. Lo único que conozco para hacer lo quev
hace esInternal`FromCoefficientList
i
dentro de la lambda. (Por otro lado, no estoy realmente seguro de si la capacidad de correr repetidamente es relevante cuando el objetivo es imprimir una lista infinita ... ¿ha habido un meta consenso sobre esto?)Iterator {i,∞} does not have appropriate bounds
.CJam (22 bytes)
Demo en línea . Tenga en cuenta que, como muchas de las respuestas existentes, esto incluye el coeficiente 0 en la salida.
Disección
fuente
Mathematica,
8679 bytesToma la entrada como dos listas separadas (coeficientes del numerador, coeficientes del denominador). Si la entrada puede tomarse directamente como una fracción de polinomios en lugar de como listas de coeficientes, esto puede acortarse significativamente.
Parece que
Do
puede funcionar con límites infinitos en v11. No puedo probar esto localmente, pero, si este es el caso, entonces esta solución se puede acortar a 75 bytes :fuente
n
partir de 1 en lugar de0
, esto da los mismos resultados que su solución; ambos fallan, sin embargo, en el penúltimo caso de prueba, que esta solución pasa al comenzarn
desde 0.Pyth , 23 bytes
Pruébalo en línea!
Cómo funciona
fuente
Pari / GP , 66 bytes
Pruébalo en línea!
fuente