Oblicz współczynniki mocy

24

Biorąc pod uwagę wielomian p(x)ze współczynnikami całkowymi i stałym składnikiem p(0) = 1 or -1oraz nieujemną liczbą całkowitą N, zwraca N-ty współczynnik szeregu potęgowego (czasami nazywany „szeregiem Taylora”) f(x) = 1/p(x)opracowany przy x0 = 0, tj. Współczynniku monomialu stopnia N.

Podane warunki gwarantują istnienie szeregu mocy, a jego współczynniki są liczbami całkowitymi.

Detale

Jak zawsze wielomian można zaakceptować w dowolnym dogodnym formacie, np. Listę współczynników można na przykład p(x) = x^3-2x+5przedstawić jako [1,0,-2,5].

Potęgi funkcji fopracowanej 0przez podano przez

a N-ty współczynnik (współczynnik x^N) jest określony przez

gdzie oznacza n-tą pochodnąf

Przykłady

  • Wielomian p(x) = 1-xdaje wynik w szeregu geometrycznym, f(x) = 1 + x + x^2 + ...więc wynik powinien być 1dla wszystkich N.

  • p(x) = (1-x)^2 = x^2 - 2x + 1daje pochodną szeregu geometrycznego f(x) = 1 + 2x + 3x^2 + 4x^3 + ..., więc wynikiem Njest N+1.

  • p(x) = 1 - x - x^2 skutkuje funkcją generowania sekwencji Fibonacciego f(x) = 1 + x + 2x^2 + 3x^3 + 5x^4 + 8x^5 + 13x^6 + ...

  • p(x) = 1 - x^2skutkuje funkcją generującą 1,0,1,0,...tjf(x) = 1 + x^2 + x^4 + x^6 + ...

  • p(x) = (1 - x)^3 = 1 -3x + 3x^2 - x^3skutkuje funkcją generowania liczb trójkątnych, f(x) = 1 + 3x + 6x^6 + 10x^3 + 15x^4 + 21x^5 + ...co oznacza, że N-ty współczynnik jest współczynnikiem dwumianowym(N+2, N)

  • p(x) = (x - 3)^2 + (x - 2)^3 = 1 + 6x - 5x^2 + x^3 prowadzi do f(x) = 1 - 6x + 41x^2 - 277x^3 + 1873x4 - 12664x^5 + 85626x^6 - 57849x^7 + ...

wada
źródło
Czy dopuszczalne byłoby przyjęcie wielomianu jako nieskończonej listy współczynników szeregów mocy, takich jak [1,-1,0,0,0,0,...]?
xnor
Tak, myślę, że jest to akceptowalny format.
flawr
Wybrano ładne przykłady!
Greg Martin
Cieszę się, że to doceniasz, dziękuję =)
flawr

Odpowiedzi:

9

Mathematica, 24 23 bajty

Zaoszczędzono 1 bajt dzięki Gregowi Martinowi

D[1/#2,{x,#}]/#!/.x->0&

Czysta funkcja z dwoma argumentami #i #2. Zakłada, że ​​wielomian #2spełnia PolynomialQ[#2,x]. Oczywiście jest do tego wbudowana:

SeriesCoefficient[1/#2,{x,0,#}]&
ngenisis
źródło
1
Brawo, pokonując wbudowane! Myślę, że możesz zapisać bajt, zakładając, że #jest on liczbą całkowitą Ni #2jest wielomianem.
Greg Martin
6

Matlab, 81 79 75 bajtów

W przeciwieństwie do dwóch poprzednich odpowiedzi nie korzysta z obliczeń symbolicznych. Chodzi o to, że można iteracyjnie obliczyć współczynniki:

function C=f(p,N);s=p(end);for k=1:N;q=conv(p,s);s=[-q(end-k),s];end;C=s(1)

Wypróbuj online!

Wyjaśnienie

function C=f(p,N);
s=p(end);            % get the first (constant coefficient)
for k=1:N;           
    q=conv(p,s);     % multiply the known coefficients with the polynomial
    s=[-q(end-k),s]; % determine the new coefficient to make the the product get "closer" 
end;
C=s(1)           % output the N-th coefficient
wada
źródło
4

GeoGebra , 28 bajtów

Derivative[1/A1,B1]/B1!
f(0)

Dane wejściowe są pobierane z komórek arkusza kalkulacyjnego A1 i B1 odpowiednio wielomianu i liczby całkowitej, a każda linia jest wprowadzana osobno w pasku wprowadzania. Wyjście odbywa się poprzez przypisanie do zmiennej a.

Oto gif przedstawiający wykonanie:

Współczynniki Taylora

Korzystanie z wbudowanych jest znacznie dłuższe i wynosi 48 bajtów:

First[Coefficients[TaylorPolynomial[1/A1,0,B1]]]
TheBikingViking
źródło
4

Haskell, 44 bajty

p%n=(0^n-sum[p!!i*p%(n-i)|i<-[1..n]])/head p

Bezpośrednie obliczenia bez wbudowanych algorytmów algebraicznych. Pobiera dane wejściowe jako nieskończoną listę współczynników szeregu mocy, takich jak p = [1,-2,3,0,0,0,0...](tj. p = [1,-2,3] ++ repeat 0) Dla 1-2*x+x^2. Nazwij to jak p%3, co daje -4.0.

Chodzi o to, że jeśli p jest wielomianem, a q = 1 / p jest odwrotne, to możemy wyrazić równość p · q = 1 termin po terminie. Współczynnik x n w p · Q jest przez splot tych współczynników p i q :

p 0 · q n + p 1 · q n-1 + ... + p n · q 0

Aby p · q = 1 utrzymało się, powyższe musi być równe zero dla wszystkich n> 0 . W tym przypadku możemy wyrazić q n rekurencyjnie w kategoriach q 0 , ..., q n-1 i współczynników p .

q n = - 1 / p 0 · (p 1 · q n-1 + ... + p n · q 0 )

To jest dokładnie to, co obliczono w wyrażeniu sum[p!!i*p%(n-i)|i<-[1..n]]/head p, z head pwiodącym współczynnikiem p 0 . Początkowy współczynnik q 0 = 1 / p 0 jest traktowany arytmetycznie w tym samym wyrażeniu przy użyciu 0^njako wskaźnika dla n==0.

xnor
źródło
3

J, 12 bajtów

1 :'(1%u)t.'

Wykorzystuje przysłówek, t.który przyjmuje wielomian pw postaci czasownika na LHS i nieujemną liczbę całkowitą kna RHS, i oblicza współczynnik kth z serii Taylora pna x = 0. Aby uzyskać serię mocy, należy zastosować odwrotność pprzed zastosowaniem.

Wypróbuj online!

mile
źródło
2

Klon, 58 26 bajtów

Jest to funkcja bez nazwy, która akceptuje wielomian w xi liczbę całkowitą N.

EDYCJA: Właśnie zauważyłem, że jest wbudowany:

(p,N)->coeftayl(1/p,x=0,N)
wada
źródło
1

MATL , 19 bajtów

0)i:"1GY+@_)_8Mh]1)

Tłumaczenie świetnej odpowiedzi Matlaba na @ flawr .

Wypróbuj online!

Jak to działa

0)      % Implicitly input vector of polynomial coefficients and get last entry
i       % Input N
:"      % For k in [1 2 ... N]
  1G    %   Push vector of polynomial coefficients
  Y+    %   Convolution, full size
  @     %   Push k
  _     %   Negate
  )     %   Index. This produces the end-k coefficient
  _     %   Negate
  8M    %   Push first input of the latest convolution
  h     %   Concatenate horizontally
]       % End
1)      % Get first entry. Implicitly display
Luis Mendo
źródło
1

JavaScript (ES6), 57 bajtów

(a,n)=>a.reduce((s,p,i)=>!i|i>n?s:s-p*f(a,n-i),!n)/a[0]

Port odpowiedzi Haskell @ xnora. Początkowo próbowałem wersji iteracyjnej, ale okazało się, że ma 98 bajtów, jednak dla dużych liczb N będzie znacznie szybsza, ponieważ skutecznie zapamiętywam rekurencyjne wywołania:

(a,n)=>[...Array(n+1)].fill(0).map((_,i,r)=>r[i]=r.reduce((s,p,j)=>s-p*(a[i-j]||0),!i)/a[0]).pop()

n+1warunki są wymagane, które są zapisywane w tablicy r. Początkowo są to zera, co pozwala na zmniejszenie całej tablicy rjednocześnie, ponieważ zera nie wpłyną na wynik. Ostatni obliczony współczynnik to wynik końcowy.

Neil
źródło
1

PARI / GP, 31 27 bajtów

f->n->Pol(Ser(1/f,,n+1))\x^n
alephalpha
źródło