Wyzwanie
Biorąc wielomianu p
o współczynnikach rzeczywistych porządku 1
i stopnia n
, znaleźć inny wielomian q
stopnia co najwyżej n
taki, że (p∘q)(X) = p(q(X)) ≡ X mod X^(n+1)
, innymi słowy takie, że p(q(X)) = X + h(X)
gdzie h
jest dowolnym wielomianem ord(h) ≥ n+1
. Wielomian q
jest jednoznacznie określony przez p
.
Dla wielomian p(X) = a(n)*X^n + a(n+1)*X^(n+1) + ... + a(m)*X^m
gdzie n <= m
i a(n) ≠ 0
, a(m) ≠ 0
mówimy, n
jest zamówienie od p
i m
jest wyższe od p
.
Uproszczenie : Możesz założyć, że p
ma współczynniki całkowite, i a(1)=1
(tak p(X) = X + [some integral polynomial of order 2]
). W tym przypadku q
ma również współczynniki całkowite.
Celem tego uproszczenia jest uniknięcie problemów z liczbami zmiennoprzecinkowymi. Istnieje jednak niecałkowity przykład do celów ilustracyjnych.
Przykłady
- Zastanów się nad serią Taylora,
exp(x)-1 = x + x^2/2 + x^3/6 + x^4/24 + ...
aln(x+1) = x - x^2/2 + x^3/3 - x^4/4 + ...
potem oczywiścieln(exp(x)-1+1)= x
. Jeśli po prostu rozważyć wielomiany stopnia 4 Taylor z tych dwóch funkcji możemy uzyskać z notacją od dołu (patrz testami)p = [-1/4,1/3,-1/2,1,0]
iq = [1/24, 1/6, 1/2, 1,0]
i(p∘q)(X) ≡ X mod X^5
Rozważ wielomian
p(X) = X + X^2 + X^3 + X^4
. Aq(X) = X - X^2 + X^3 - X^4
więc dostaniemy(p∘q)(X) = p(q(X)) = X - 2X^5 + 3X^6 - 10X^7 +...+ X^16 ≡ X mod X^5
Przypadki testowe
W tym przypadku wielomian wejściowy i wyjściowy są zapisywane jako listy współczynników (ze współczynnikiem monomialu najwyższego stopnia najpierw, a stałym składnikiem jako ostatnim):
p = [4,3,2,0]; q=[0.3125,-.375,0.5,0]
Zintegrowane przypadki testowe:
p = [1,0]; q = [1,0]
p = [9,8,7,6,5,4,3,2,1,0]; q = [4862,-1430,429,-132,42,-14,5,-2,1,0]
p = [-1,3,-3,1,0]; q = [91,15,3,1,0]
źródło