Berechnen Sie die Potenzreihenkoeffizienten

24

Bei einem Polynom p(x)mit ganzzahligen Koeffizienten und einem konstanten Term von p(0) = 1 or -1und einer nichtnegativen ganzen Zahl Nwird der N-te Koeffizient der Potenzseris (manchmal als "Taylor-Reihe" bezeichnet) von f(x) = 1/p(x)entwickelt x0 = 0, dh der Koeffizient des Gradmonoms, zurückgegeben N.

Die gegebenen Bedingungen stellen sicher, dass die Potenzreihen existieren und die Koeffizienten ganze Zahlen sind.

Einzelheiten

Wie immer kann das Polynom in jedem geeigneten Format akzeptiert werden, z. B. kann eine Liste von Koeffizienten p(x) = x^3-2x+5dargestellt werden als [1,0,-2,5].

Die Potenzreihen einer bei fentwickelten Funktion 0sind gegeben durch

und der N-te Koeffizient (der Koeffizient von x^N) ist gegeben durch

wo bezeichnet die n-te Ableitung vonf

Beispiele

  • Das Polynom p(x) = 1-xergibt die geometrische Reihe, f(x) = 1 + x + x^2 + ...daher sollte die Ausgabe 1für alle gelten N.

  • p(x) = (1-x)^2 = x^2 - 2x + 1ergibt die Ableitung der geometrischen Reihe f(x) = 1 + 2x + 3x^2 + 4x^3 + ..., die Ausgabe für Nist also N+1.

  • p(x) = 1 - x - x^2 ergibt die Erzeugungsfunktion der Fibonacci-Sequenz f(x) = 1 + x + 2x^2 + 3x^3 + 5x^4 + 8x^5 + 13x^6 + ...

  • p(x) = 1 - x^2ergibt sich die erzeugende Funktion von 1,0,1,0,...dhf(x) = 1 + x^2 + x^4 + x^6 + ...

  • p(x) = (1 - x)^3 = 1 -3x + 3x^2 - x^3ergibt die Erzeugungsfunktion der Dreieckszahlen f(x) = 1 + 3x + 6x^6 + 10x^3 + 15x^4 + 21x^5 + ..., dh der N-te Koeffizient ist der Binomialkoeffizient(N+2, N)

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

Fehler
quelle
Wäre es akzeptabel, ein Polynom als eine unendliche Liste von Potenzreihenkoeffizienten zu betrachten, wie z [1,-1,0,0,0,0,...].
Xnor
Ja, ich denke, dass dies ein akzeptables Format ist.
Fehler
Schöne Beispiele ausgewählt!
Greg Martin
Ich bin froh, dass Sie es zu schätzen wissen, danke =)
Fehler

Antworten:

9

Mathematica, 24 23 Bytes

Dank Greg Martin 1 Byte gespeichert

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

Reine Funktion mit zwei Argumenten #und #2. Nimmt an, dass das Polynom #2erfüllt ist PolynomialQ[#2,x]. Natürlich gibt es dafür ein eingebautes:

SeriesCoefficient[1/#2,{x,0,#}]&
Genisis
quelle
1
Gut gemacht, die eingebauten zu schlagen! Ich denke, Sie können ein Byte speichern, indem Sie annehmen, dass dies #die ganze Zahl Nund #2das Polynom ist.
Greg Martin
6

Matlab, 81 79 75 Bytes

Im Gegensatz zu den beiden vorherigen Antworten werden hier keine symbolischen Berechnungen verwendet. Die Idee ist, dass Sie die Koeffizienten iterativ berechnen können:

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)

Probieren Sie es online!

Erläuterung

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
Fehler
quelle
4

GeoGebra , 28 Bytes

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

Die Eingabe erfolgt aus den Tabellenkalkulationszellen A1 und B1 eines Polynoms bzw. einer Ganzzahl, und jede Zeile wird separat in die Eingabeleiste eingegeben. Die Ausgabe erfolgt über die Zuordnung zur Variablen a.

Hier ist ein GIF, das die Ausführung zeigt:

Taylor-Koeffizienten

Die Verwendung von Builtins ist mit 48 Bytes viel länger:

First[Coefficients[TaylorPolynomial[1/A1,0,B1]]]
TheBikingViking
quelle
4

Haskell, 44 Bytes

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

Eine direkte Berechnung ohne algebraische Einbauten. Nimmt die Eingabe als unendliche Liste von Potenzreihenkoeffizienten wie p = [1,-2,3,0,0,0,0...](dh p = [1,-2,3] ++ repeat 0) für 1-2*x+x^2. Nenne es gerne p%3, was gibt -4.0.

Die Idee ist, wenn p ein Polynom ist und q = 1 / p ist es invers, dann können wir die Gleichheit p · q = 1 termweise ausdrücken . Der Koeffizient von x n in p · q ergibt sich aus der Faltung der Koeffizienten in p und q :

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

Damit p · q = 1 gilt, muss das Obige für alle n> 0 gleich Null sein . Denn hier können wir q n rekursiv durch q 0 , ..., q n-1 und die Koeffizienten von p ausdrücken .

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

Dies ist genau das, was im Ausdruck sum[p!!i*p%(n-i)|i<-[1..n]]/head pmit head pdem führenden Koeffizienten p 0 berechnet wird . Der Anfangskoeffizient q 0 = 1 / p 0 wird in demselben Ausdruck arithmetisch behandelt, der 0^nals Indikator für verwendet wird n==0.

xnor
quelle
3

J, 12 Bytes

1 :'(1%u)t.'

Verwendet das Adverb, t.das ein Polynom pin Form eines Verbs in der LHS und einer nichtnegativen Ganzzahl kin der RHS annimmt und den kth- Koeffizienten der Taylor-Reihe von pat berechnet x = 0. Um die Potenzreihe zu erhalten, pwird vor der Anwendung der Kehrwert von genommen.

Probieren Sie es online!

Meilen
quelle
2

Ahorn, 58 26 Bytes

Dies ist eine unbenannte Funktion, die ein Polynom in xund eine Ganzzahl akzeptiert N.

EDIT: Mir ist gerade aufgefallen, dass es ein eingebautes gibt:

(p,N)->coeftayl(1/p,x=0,N)
Fehler
quelle
1

MATL , 19 Bytes

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

Übersetzung der großartigen Matlab-Antwort von @ flawr .

Probieren Sie es online!

Wie es funktioniert

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
quelle
1

JavaScript (ES6), 57 Byte

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

Port von @ xnors Haskell-Antwort. Ursprünglich habe ich eine iterative Version ausprobiert, es stellte sich jedoch heraus, dass sie 98 Byte groß ist. Für große N ist sie jedoch viel schneller, da ich mir die rekursiven Aufrufe effektiv merken kann:

(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+1Es sind Begriffe erforderlich, die im Array gespeichert werden r. Anfänglich sind es Nullen, die es ermöglichen, das gesamte Array rauf einmal zu reduzieren , da die Nullen das Ergebnis nicht beeinflussen. Der zuletzt berechnete Koeffizient ist das Endergebnis.

Neil
quelle
1

PARI / GP, 31 27 Bytes

f->n->Pol(Ser(1/f,,n+1))\x^n
Alephalpha
quelle