Se escrevermos uma sequência de números como coeficientes de uma série de potências, essa série de potências será chamada de função geradora (comum) (ou Gf) dessa sequência. Ou seja, se, para alguma função F(x)
e série de números inteiros a(n)
, temos:
a(0) + a(1)x + a(2)x^2 + a(3)x^3 + a(4)x^4 + ... = F(x)
Então F(x)
é a função geradora de a
. Por exemplo, a série geométrica nos diz que:
1 + x + x^2 + x^3 + x^4 + ... = 1/(1-x)
Portanto, a função geradora de 1, 1, 1, ...
é 1/(1-x)
. Se diferenciarmos ambos os lados da equação acima e multiplicarmos x
, obtemos a seguinte igualdade:
x + 2x^2 + 3x^3 + 4x^4 + ... = x/(1-x)^2
Portanto, a função geradora de 1, 2, 3, ...
é x/(1-x)^2
. A geração de funções é uma ferramenta muito poderosa e você pode fazer muitas coisas úteis com elas. Uma breve introdução pode ser encontrada aqui , mas para uma explicação realmente completa, há o incrível livro que gera a funcionalidade.
Nesse desafio, você terá uma função racional (o quociente de dois polinômios com coeficientes inteiros) como entrada como duas matrizes de coeficientes inteiros, primeiro o numerador e o denominador. Por exemplo, a função f(x) = x / (1 - x - x^2)
será codificada como [0, 1], [1, -1, -1]
na entrada.
Dada essa entrada, seu programa deve imprimir infinitamente os coeficientes da série de potências que são iguais à função geradora, um por linha, começando no coeficiente de x
, então x^2
, etc.
Exemplos:
[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, ...
fonte
Respostas:
Haskell , 63 bytes
Experimente online!
Define um operador
%
retornando uma lista lenta infinita de coeficientes. A lista é indexada a zero, portanto, o coeficiente constante é incluído.fonte
Mathematica, 64
8390bytesObrigado a @ngenisis e @Jenny_mathy!
Tome entrada como duas listas.
Precisa
Alt+.
finalizar a execução para ver o resultado. O front-end pode falhar devido à saída rápida.Versão de 83 bytes (@Jenny_mathy):
fonte
64
bytes:Do[Echo@Limit[D[#/#2/i!&@@Fold[x#+#2&]/@#,{x,i}],x->0],{i,∞}]&
. Isso pressupõe que a entrada seja uma lista de duas listas e os coeficientes estejam em ordem decrescente. A única built-in que conheço para fazer o quev
faz éInternal`FromCoefficientList
i
dentro da lambda. (Por outro lado, não tenho muita certeza se a capacidade de executar repetidamente é relevante quando o objetivo é imprimir uma lista infinita ... houve um meta consenso sobre isso?)Iterator {i,∞} does not have appropriate bounds
.CJam (22 bytes)
Demonstração online . Observe que, como muitas das respostas existentes, isso inclui o coeficiente 0 na saída.
Dissecação
fonte
Mathematica,
8679 bytesRecebe entrada como duas listas separadas (coeficientes do numerador, coeficientes do denominador). Se a entrada puder ser tomada diretamente como uma fração de polinômios, e não como listas de coeficientes, isso poderá ser reduzido significativamente.
Parece que
Do
pode funcionar com limites infinitos na v11. Não posso testar isso localmente, mas, se for esse o caso, essa solução pode ser reduzida para 75 bytes :fonte
n
partir de 1 em vez de0
, isso fornece os mesmos resultados que sua solução; ambos falham, no entanto, no penúltimo caso de teste, que esta solução passa ao iniciar an
partir de 0.Pitão , 23 bytes
Experimente online!
Como funciona
fonte
Pari / GP , 66 bytes
Experimente online!
fonte