Polynomaufnahme

22

Bei zwei Polynomen f,gwillkü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
fehlerhaft
quelle
was ist mit builtins?
Maltysen
1
@Maltysen "Details: Builtins sind erlaubt. (...)" : D
flawr
2
Ich denke, dass "jedes vernünftige Format" ein bisschen dehnbar sein könnte. Wenn eine Funktion zulässig ist, die das Polynom auswertet, ist die Kompositionsfunktion (.)eine Antwort in Haskell. Sie meinen wahrscheinlich eine Darstellung der Koeffizientenliste.
XNOR
1
Der Titel! Ich habe es gerade bekommen :-D
Luis Mendo
2
@ LuisMendo Quick Thinker = P
Fehler

Antworten:

10

Haskell, 86 72 Bytes

u!c=foldr1((.u).zipWith(+).(++[0,0..])).map c
o g=(0:)!((<$>g).(*))!pure

Definiert eine Funktion o, o g fdie die Komposition f ∘ g berechnet. Polynome werden durch eine nicht leere Liste von Koeffizienten dargestellt, die mit dem konstanten Term beginnen.

Demo

*Main> o [1,1] [5,3,1]
[9,5,1]
*Main> o [0,-1,1] [1,0,1,0,0,0,1]
[1,0,1,-2,1,0,1,-6,15,-20,15,-6,1]
*Main> o [2,1] [-192,288,-144,24]
[0,0,0,24]
*Main> o [3,2] [27,-180,138,-36,3]
[0,0,-96,0,48]

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 der zipWith(+).(++[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 Polynom g;
(0:)!((<$>g).(*))multipliziert ein Polynomargument mit dem Polynom g;
purehebt ein skalares Argument auf ein konstantes Polynom (Singleton-Liste);
(0:)!((<$>g).(*))!puresetzt mit dem Polynom ein Polynomargument zusammen g.

Anders Kaseorg
quelle
9

Mathematica, 17 Bytes

Expand[#/.x->#2]&

Anwendungsbeispiel:

In[17]:= Expand[#/.x->#2]& [27 - 180x + 138x^2 - 36x^3 + 3x^4, 3 + 2x]

              2       4
Out[17]= -96 x  + 48 x
Feersum
quelle
7

TI-Basic 68k, 12 Bytes

a|x=b→f(a,b)

Die Verwendung ist unkompliziert, zB für das erste Beispiel:

f(x^2+3x+5,y+1)

Welches kehrt zurück

y^2+5y+9
fehlerhaft
quelle
Es scheint mir ein Betrug zu sein, wenn die Eingaben in verschiedenen Variablen erfolgen müssen. Ist das wichtig für diese Antwort?
Feersum
Fühlen Sie sich frei, dies zu tun, ich erlaube ausdrücklich jedes vernünftige bequeme Eingabeformat.
Fehler
In Bezug auf die Bearbeitung Ihres Kommentars: Ja, das ist wichtig.
Fehler
Ich bin mit den Regeln auf dieser Site nicht allzu vertraut. Ist es richtig , in TI-BASIC 1 Byte zu haben?
Asmeurer
@asmeurer In der Tat: TI-Basic wird anhand der Kodierung bewertet, die auf den entsprechenden Taschenrechnern verwendet wird. Wenn Sie an den Details interessiert sind, können Sie das hier auf Meta lesen . Eine Tabelle mit Tokens finden Sie hier auf ti-basic-dev .
Fehler
6

Python 2, 138 156 162 Bytes

Es wird erwartet, dass die Eingaben Ganzzahllisten mit den kleinsten Potenzen zuerst sind.

def c(a,b):
 g=lambda p,q:q>[]and q[0]+p*g(p,q[1:]);B=99**len(`a+b`);s=g(g(B,b),a);o=[]
 while s:o+=(s+B/2)%B-B/2,;s=(s-o[-1])/B
 return o

Ungolfed:

def c(a,b):
 B=sum(map(abs,a+b))**len(a+b)**2
 w=sum(B**i*x for i,x in enumerate(b))
 s=sum(w**i*x for i,x in enumerate(a))
 o=[]
 while s:o+=min(s%B,s%B-B,key=abs),; s=(s-o[-1])/B
 return o

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, Bwie von @xnor vorgeschlagen.

Feersum
quelle
Schöne Methode. Denn B, würde 10**len(`a+b`)ausreichen , um?
xnor
@xnor Vielleicht ... ist es schwer für mich zu sagen.
Feersum
+1 Dies ist eine wirklich kreative Lösung und eine nette Verwendung von Bigints !!!
Fehler
@xnor Jetzt habe ich mich davon überzeugen können, dass die Länge des Koeffizienten in der Eingabelänge linear ist :)
feersum
5

Python + SymPy, 59-35 Byte

from sympy import*
var('x')
compose

Danke an @asmeurer für das Golfen mit 24 Bytes!

Testlauf

>>> from sympy import*
>>> var('x')
x
>>> f = compose
>>> f(x**2 + 3*x + 5, x + 1)
x**2 + 5*x + 9
Dennis
quelle
1
SymPy hat eine compose()Funktion.
Asmeurer
1
Wo ist die Antwort? Es definiert keine Funktionen mehr oder macht irgendetwas ...
feersum
1
@feersum Das war noch nie so. Sie haben diesen Meta-Post gerade bearbeitet.
Mego
3
@feersum Sie haben einen akzeptierten Meta-Post bearbeitet, um die Richtlinie für Ihre eigene Agenda zu ändern. Das ist nicht ok.
Mego
3
@feersum Auch wenn Sie vielleicht dachten, dass Ihr Wortlaut nicht eindeutig ist, war er eindeutig nicht für den Rest der Community. Wir haben den Konsens akzeptiert, der from module import*;functiongültig war. Unabhängig davon ist dies eine neuere Richtlinie, die Import- und Hilfsfunktionen mit nicht benannten Lambdas ermöglicht.
Mego
3

Salbei, 24 Bytes

lambda A,B:A(B).expand()

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

Mego
quelle
2

PARI / GP , 19 Bytes

(a,b)->subst(a,x,b)

was können Sie tun

%(x^2+1,x^2+x-1)

bekommen

% 2 = x ^ 4 + 2 * x ^ 3 - x ^ 2 - 2 * x + 2

Charles
quelle
1

MATLAB mit Symbolic Toolbox, 28 Byte

@(f,g)collect(subs(f,'x',g))

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)

x^2 + 3*x + 5

Beispiellauf:

>> @(f,g)collect(subs(f,'x',g))
ans = 
    @(f,g)collect(subs(f,'x',g))
>> ans('3*x^4 - 36*x^3 + 138*x^2 - 180*x + 27','2*x + 3')
ans =
48*x^4 - 96*x^2
Luis Mendo
quelle
1

Python 2, 239 232 223 Bytes

r=range
e=reduce
a=lambda*l:map(lambda x,y:(x or 0)+(y or 0),*l)
m=lambda p,q:[sum((p+k*[0])[i]*(q+k*[0])[k-i]for i in r(k+1))for k in r(len(p+q)-1)]
o=lambda f,g:e(a,[e(m,[[c]]+[g]*k)for k,c in enumerate(f)])

Eine "richtige" Implementierung, die keine Basen missbraucht. Niedrigster signifikanter Koeffizient zuerst.

aist Polynomaddition, mist Polynommultiplikation und oist Zusammensetzung.

orlp
quelle
Ist das m([c],e(m,[[1]]+[g]*k))nicht dasselbe wie e(m,[[c]]+[g]*k)?
Neil
@Neil Guter Anruf, kann zwei in einem damit zerquetschen!
Orlp
a=lambda*l:map(lambda x,y:(x or 0)+(y or 0),*l)
Anders Kaseorg
@AndersKaseorg Richtig, ich habe es hinzugefügt, danke :)
Orlp
Es könnte möglich sein, Ihre Polynomaddition zu vereinfachen, da ich denke, dass eine Liste immer länger als die andere ist, sodass Sie die ( or 0)in dieser Version nicht benötigen .
Neil
1

JavaScript (ES6), 150 103 Byte

(f,g)=>f.map(n=>r=p.map((m,i)=>(g.map((n,j)=>p[j+=i]=m*n+(p[j]||0)),m*n+(r[i]||0)),p=[]),r=[],p=[1])&&r

Akzeptiert 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 mapAufrufe 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 .

(f,g)=>f.map(n=>            Loop through each term of f (n = f[h])
 r=p.map((m,i)=>(           Loop through each term of p (m = p[i])
  g.map((n,j)=>             Loop though each term of g (n = g[j])
   p[j+=i]=m*n+(p[j]||0)),  Accumulate p*g in p
  m*n+(r[i]||0)),           Meanwhile add p[i]*f[h] to r[i]
  p=[]),                    Reset p to 0 each loop to calculate p*g
 r=[],                      Initialise r to 0
 p=[1]                      Initialise p to 1
)&&r                        Return the result
Neil
quelle
1

Pyth, 51 34 Bytes

AQsM.t*LVG.usM.t.e+*]0k*LbHN0tG]1Z

Testsuite .

Undichte Nonne
quelle
2
wenn Python outgolfs pyth
downrep_nation
@ Downrep_nation nicht mehr :)
Leaky Nun
1

Ruby 2.4 + Polynom , 41 + 12 = 53 Bytes

Verwendet Flagge -rpolynomial. Die Eingabe besteht aus zwei PolynomialObjekten.

Wenn mich jemand in Vanille Ruby (keine polynomiale externe Bibliothek) überlistet, bin ich sehr beeindruckt.

->a,b{i=-1;a.coefs.map{|c|c*b**i+=1}.sum}
Wert Tinte
quelle