Dado um polinômio p(x)
com coeficientes integrais e um termo constante de p(0) = 1 or -1
, e um número inteiro não negativo N
, retorne o N
-ésimo coeficiente do seris de potência (às vezes chamado de "série Taylor") de f(x) = 1/p(x)
desenvolvido em x0 = 0
, isto é, o coeficiente do monômio de grau N
.
As condições dadas garantem que a série de potências exista e que seus coeficientes sejam inteiros.
Detalhes
Como sempre, o polinômio pode ser aceito em qualquer formato conveniente, por exemplo, uma lista de coeficientes, por exemplo, p(x) = x^3-2x+5
pode ser representada como [1,0,-2,5]
.
As séries de potência de uma função f
desenvolvida em 0
são dadas por
e o N
-ésimo coeficiente (o coeficiente de x^N
) é dado por
onde denota a n
-ésima derivada def
Exemplos
O polinômio
p(x) = 1-x
resulta na série geométrica,f(x) = 1 + x + x^2 + ...
portanto a saída deve ser1
para todosN
.p(x) = (1-x)^2 = x^2 - 2x + 1
resulta na derivada da série geométricaf(x) = 1 + 2x + 3x^2 + 4x^3 + ...
, então a saída paraN
éN+1
.p(x) = 1 - x - x^2
resulta na função geradora da sequência de Fibonaccif(x) = 1 + x + 2x^2 + 3x^3 + 5x^4 + 8x^5 + 13x^6 + ...
p(x) = 1 - x^2
resulta na função geradora de1,0,1,0,...
ief(x) = 1 + x^2 + x^4 + x^6 + ...
p(x) = (1 - x)^3 = 1 -3x + 3x^2 - x^3
resulta na função geradora dos números triangularesf(x) = 1 + 3x + 6x^6 + 10x^3 + 15x^4 + 21x^5 + ...
que significa que oN
-ésimo coeficiente é o coeficiente binomial(N+2, N)
p(x) = (x - 3)^2 + (x - 2)^3 = 1 + 6x - 5x^2 + x^3
resulta emf(x) = 1 - 6x + 41x^2 - 277x^3 + 1873x4 - 12664x^5 + 85626x^6 - 57849x^7 + ...
fonte
[1,-1,0,0,0,0,...]
?Respostas:
Mathematica,
2423 bytesGuardado 1 byte graças a Greg Martin
Função pura com dois argumentos
#
e#2
. Assume que o polinômio é#2
satisfatórioPolynomialQ[#2,x]
. Claro que há um built-in para isso:fonte
#
é o número inteiroN
e#2
é o polinômio.Matlab,
81 7975 bytesAo contrário das duas respostas anteriores, isso não faz uso de cálculos simbólicos. A ideia é que você possa calcular iterativamente os coeficientes:
Experimente online!
Explicação
fonte
GeoGebra , 28 bytes
A entrada é obtida das células da planilha A1 e B1 de um polinômio e um número inteiro, respectivamente, e cada linha é inserida separadamente na barra de entrada. A saída é via atribuição à variável
a
.Aqui está um gif mostrando a execução:
O uso de built-in é muito mais longo, com 48 bytes:
fonte
Haskell, 44 bytes
Uma computação direta sem built-ins algébricos. Recebe entrada como uma lista infinita de coeficientes de séries de potência, como
p = [1,-2,3,0,0,0,0...]
(iep = [1,-2,3] ++ repeat 0
) para1-2*x+x^2
. Chame assimp%3
, o que dá-4.0
.A idéia é que se p é um polinômio e q = 1 / p é inverso, então podemos expressar a igualdade p · q = 1 termo a termo. O coeficiente de x n em p · q é dado pela convolução dos coeficientes em p e q :
p 0 · q n + p 1 · q n-1 + ... + p n · q 0
Para que p · q = 1 seja mantido, o acima deve ser igual a zero para todos os n> 0 . Por aqui, podemos expressar q n recursivamente em termos de q 0 , ..., q n-1 e os coeficientes de p .
q n = - 1 / p 0 · (p 1 · q n-1 + ... + p n · q 0 )
É exatamente isso que é calculado na expressão
sum[p!!i*p%(n-i)|i<-[1..n]]/head p
, comhead p
o coeficiente inicial p 0 . O coeficiente inicial q 0 = 1 / p 0 é tratado aritmeticamente na mesma expressão usando0^n
como um indicador paran==0
.fonte
J, 12 bytes
Usa o advérbio
t.
que recebe um polinômiop
na forma de um verbo no LHS e um número inteiro não negativok
no RHS e calcula o coeficientek
th da série Taylor dep
emx = 0
. Para obter a série de potências,p
é recíproco antes de aplicá-la.Experimente online!
fonte
Bordo,
5826 bytesEsta é uma função sem nome que aceita um polinômio in
x
e um número inteiroN
.EDIT: Acabei de notar que existe um builtin:
fonte
MATL , 19 bytes
Tradução da ótima resposta do @ flawr no Matlab .
Experimente online!
Como funciona
fonte
JavaScript (ES6), 57 bytes
Porto da resposta Haskell do @ xnor. Inicialmente, tentei uma versão iterativa, mas era de 98 bytes, mas será muito mais rápido para N grande, pois estou efetivamente memorizando as chamadas recursivas:
n+1
são necessários termos salvos na matrizr
. Inicialmente, são zeros que permitem reduzir toda a matriz der
uma só vez, pois os zeros não afetam o resultado. O último coeficiente calculado é o resultado final.fonte
PARI / GP,
3127 bytesfonte