Bei zwei Polynomen f,g
willkürlichen Grades über den ganzen Zahlen sollte Ihr Programm / Ihre Funktion das erste Polynom im zweiten Polynom auswerten. f(g(x))
(auch bekannt als die Zusammensetzung (fog)(x)
der beiden Polynome)
Einzelheiten
Builtins sind erlaubt. Sie können jede sinnvolle Formatierung als Eingabe / Ausgabe annehmen, aber das Eingabe- und Ausgabeformat sollte übereinstimmen. ZB Formatierung als String
x^2+3x+5
oder als Koeffizientenliste:
[1,3,5] or alternatively [5,3,1]
Weiterhin kann angenommen werden, dass die Eingabepolynome vollständig expandiert sind, und es wird auch erwartet, dass die Ausgaben vollständig expandiert sind.
Beispiele
A(x) = x^2 + 3x + 5, B(y) = y+1
A(B(y)) = (y+1)^2 + 3(y+1) + 5 = y^2 + 5y + 9
A(x) = x^6 + x^2 + 1, B(y) = y^2 - y
A(B(y))= y^12 - 6y^11 + 15y^10 - 20y^9 + 15y^8 - 6y^7 + y^6 + y^4 - 2 y^3 + y^2 + 1
A(x) = 24x^3 - 144x^2 + 288x - 192, B(y) = y + 2
A(B(y)) = 24y^3
A(x) = 3x^4 - 36x^3 + 138x^2 - 180x + 27, B(y) = 2y + 3
A(B(y)) = 48y^4 - 96y^2
(.)
eine Antwort in Haskell. Sie meinen wahrscheinlich eine Darstellung der Koeffizientenliste.Antworten:
Haskell,
8672 BytesDefiniert eine Funktion
o
,o g f
die die Komposition f ∘ g berechnet. Polynome werden durch eine nicht leere Liste von Koeffizienten dargestellt, die mit dem konstanten Term beginnen.Demo
Wie es funktioniert
Keine polynombezogenen Buildins oder Bibliotheken. Beachten Sie die ähnlichen Rezidive
f (x) = a + f₁ (x) x ⇒ f (x) g (x) = ag (x) + f₁ (x) g (x) x,
f (x) = a + f₁ (x) x ⇒ f (g (x)) = a + f & sub1; (g (x)) g (x),
für die Polynommultiplikation bzw. -zusammensetzung. Sie nehmen beide die Form an
f (x) = a + f & sub1; (x) x ⇒ W (f) (x) = C (a) (x) + U (W (f & sub1;)) (x).
Der Operator
!
löst eine Wiederholung dieser Form für W mit U und C unter Verwendung derzipWith(+).(++[0,0..])
Polynomaddition (vorausgesetzt, das zweite Argument ist länger - für unsere Zwecke wird es immer länger sein). Dann,(0:)
multipliziert ein Polynomargument mit x (indem ein Nullkoeffizient vorangestellt wird);(<$>g).(*)
multipliziert ein skalares Argument mit dem Polynomg
;(0:)!((<$>g).(*))
multipliziert ein Polynomargument mit dem Polynomg
;pure
hebt ein skalares Argument auf ein konstantes Polynom (Singleton-Liste);(0:)!((<$>g).(*))!pure
setzt mit dem Polynom ein Polynomargument zusammeng
.quelle
Mathematica, 17 Bytes
Anwendungsbeispiel:
quelle
TI-Basic 68k, 12 Bytes
Die Verwendung ist unkompliziert, zB für das erste Beispiel:
Welches kehrt zurück
quelle
→
, in TI-BASIC 1 Byte zu haben?Python 2, 138
156 162BytesEs wird erwartet, dass die Eingaben Ganzzahllisten mit den kleinsten Potenzen zuerst sind.
Ungolfed:
Bei dieser Berechnung werden die Polynomkoeffizienten als Ziffern (die negativ sein können) einer Zahl auf einer sehr großen Basis betrachtet. Nachdem Polynome in diesem Format vorliegen, ist die Multiplikation oder Addition eine einzelne Ganzzahloperation. Solange die Basis ausreichend groß ist, werden keine Überträge in benachbarte Ziffern übertragen.
-18 von Verbesserung gebunden an,
B
wie von @xnor vorgeschlagen.quelle
B
, würde10**len(`a+b`)
ausreichen , um?Python + SymPy,
59-35ByteDanke an @asmeurer für das Golfen mit 24 Bytes!
Testlauf
quelle
compose()
Funktion.from module import*;function
gültig war. Unabhängig davon ist dies eine neuere Richtlinie, die Import- und Hilfsfunktionen mit nicht benannten Lambdas ermöglicht.Salbei, 24 Bytes
Ab Sage 6.9 (die Version, die unter http://sagecell.sagemath.org ausgeführt wird ) führen Funktionsaufrufe ohne explizite Argumentzuweisung (
f(2) rather than f(x=2)
) dazu, dass eine nervige und nicht hilfreiche Nachricht an STDERR ausgegeben wird. Da STDERR im Codegolf standardmäßig ignoriert werden kann, ist dies weiterhin gültig.Dies ist Dennis 'SymPy-Antwort sehr ähnlich, da Sage a) auf Python basiert und b) Maxima verwendet , ein Computeralgebrasystem, das SymPy in vielerlei Hinsicht sehr ähnlich ist. Allerdings ist Sage mit SymPy viel leistungsfähiger als Python und daher eine Sprache, die eine eigene Antwort verdient.
Überprüfen Sie alle Testfälle online
quelle
PARI / GP , 19 Bytes
was können Sie tun
bekommen
quelle
MATLAB mit Symbolic Toolbox, 28 Byte
Dies ist eine anonyme Funktion. Um es aufzurufen, weisen Sie es einer Variablen zu oder verwenden Sie
ans
. Eingaben sind Zeichenfolgen mit dem Format (Leerzeichen sind optional)Beispiellauf:
quelle
Python 2,
239232223 BytesEine "richtige" Implementierung, die keine Basen missbraucht. Niedrigster signifikanter Koeffizient zuerst.
a
ist Polynomaddition,m
ist Polynommultiplikation undo
ist Zusammensetzung.quelle
m([c],e(m,[[1]]+[g]*k))
nicht dasselbe wiee(m,[[c]]+[g]*k)
?a=lambda*l:map(lambda x,y:(x or 0)+(y or 0),*l)
( or 0)
in dieser Version nicht benötigen .JavaScript (ES6),
150103 ByteAkzeptiert und gibt Polynome als Array a = [a 0 , a 1 , a 2 , ...] zurück, das a 0 + a 1 * x + a 2 * x 2 ... darstellt.
Bearbeiten: 47 Bytes durch Umschalten von rekursiver zu iterativer Polynommultiplikation gespart, wodurch ich zwei
map
Aufrufe zusammenführen konnte.Erklärung: r ist das Ergebnis, das bei Null beginnt, dargestellt durch ein leeres Array, und p ist g h , das bei Eins beginnt. p wird von jedem multipliziert f h wiederum , und das Ergebnis der aufgelaufenen r . Gleichzeitig wird p mit g multipliziert .
quelle
Pyth,
5134 BytesTestsuite .
quelle
Ruby 2.4 + Polynom , 41 + 12 = 53 Bytes
Verwendet Flagge
-rpolynomial
. Die Eingabe besteht aus zweiPolynomial
Objekten.Wenn mich jemand in Vanille Ruby (keine polynomiale externe Bibliothek) überlistet, bin ich sehr beeindruckt.
quelle