Bei einem Polynom p(x)
mit ganzzahligen Koeffizienten und einem konstanten Term von p(0) = 1 or -1
und einer nichtnegativen ganzen Zahl N
wird 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+5
dargestellt werden als [1,0,-2,5]
.
Die Potenzreihen einer bei f
entwickelten Funktion 0
sind 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-x
ergibt die geometrische Reihe,f(x) = 1 + x + x^2 + ...
daher sollte die Ausgabe1
für alle geltenN
.p(x) = (1-x)^2 = x^2 - 2x + 1
ergibt die Ableitung der geometrischen Reihef(x) = 1 + 2x + 3x^2 + 4x^3 + ...
, die Ausgabe fürN
ist alsoN+1
.p(x) = 1 - x - x^2
ergibt die Erzeugungsfunktion der Fibonacci-Sequenzf(x) = 1 + x + 2x^2 + 3x^3 + 5x^4 + 8x^5 + 13x^6 + ...
p(x) = 1 - x^2
ergibt sich die erzeugende Funktion von1,0,1,0,...
dhf(x) = 1 + x^2 + x^4 + x^6 + ...
p(x) = (1 - x)^3 = 1 -3x + 3x^2 - x^3
ergibt die Erzeugungsfunktion der Dreieckszahlenf(x) = 1 + 3x + 6x^6 + 10x^3 + 15x^4 + 21x^5 + ...
, dh derN
-te Koeffizient ist der Binomialkoeffizient(N+2, N)
p(x) = (x - 3)^2 + (x - 2)^3 = 1 + 6x - 5x^2 + x^3
Ergebnisse inf(x) = 1 - 6x + 41x^2 - 277x^3 + 1873x4 - 12664x^5 + 85626x^6 - 57849x^7 + ...
quelle
[1,-1,0,0,0,0,...]
.Antworten:
Mathematica,
2423 BytesDank Greg Martin 1 Byte gespeichert
Reine Funktion mit zwei Argumenten
#
und#2
. Nimmt an, dass das Polynom#2
erfüllt istPolynomialQ[#2,x]
. Natürlich gibt es dafür ein eingebautes:quelle
#
die ganze ZahlN
und#2
das Polynom ist.Matlab,
81 7975 BytesIm Gegensatz zu den beiden vorherigen Antworten werden hier keine symbolischen Berechnungen verwendet. Die Idee ist, dass Sie die Koeffizienten iterativ berechnen können:
Probieren Sie es online!
Erläuterung
quelle
GeoGebra , 28 Bytes
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:
Die Verwendung von Builtins ist mit 48 Bytes viel länger:
quelle
Haskell, 44 Bytes
Eine direkte Berechnung ohne algebraische Einbauten. Nimmt die Eingabe als unendliche Liste von Potenzreihenkoeffizienten wie
p = [1,-2,3,0,0,0,0...]
(dhp = [1,-2,3] ++ repeat 0
) für1-2*x+x^2
. Nenne es gernep%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 p
mithead p
dem führenden Koeffizienten p 0 berechnet wird . Der Anfangskoeffizient q 0 = 1 / p 0 wird in demselben Ausdruck arithmetisch behandelt, der0^n
als Indikator für verwendet wirdn==0
.quelle
J, 12 Bytes
Verwendet das Adverb,
t.
das ein Polynomp
in Form eines Verbs in der LHS und einer nichtnegativen Ganzzahlk
in der RHS annimmt und denk
th- Koeffizienten der Taylor-Reihe vonp
at berechnetx = 0
. Um die Potenzreihe zu erhalten,p
wird vor der Anwendung der Kehrwert von genommen.Probieren Sie es online!
quelle
Ahorn,
5826 BytesDies ist eine unbenannte Funktion, die ein Polynom in
x
und eine Ganzzahl akzeptiertN
.EDIT: Mir ist gerade aufgefallen, dass es ein eingebautes gibt:
quelle
MATL , 19 Bytes
Übersetzung der großartigen Matlab-Antwort von @ flawr .
Probieren Sie es online!
Wie es funktioniert
quelle
JavaScript (ES6), 57 Byte
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:
n+1
Es sind Begriffe erforderlich, die im Array gespeichert werdenr
. Anfänglich sind es Nullen, die es ermöglichen, das gesamte Arrayr
auf einmal zu reduzieren , da die Nullen das Ergebnis nicht beeinflussen. Der zuletzt berechnete Koeffizient ist das Endergebnis.quelle
PARI / GP,
3127 Bytesquelle