Polinomial persepsi

22

Diberi dua polinomial f,gderajat sembarang atas bilangan bulat, program / fungsi Anda harus mengevaluasi polinomial pertama di polinomial kedua. f(g(x))(alias komposisi (fog)(x) dua polinomial)

Detail

Dibangun secara bawaan. Anda dapat menganggap pemformatan yang masuk akal sebagai input / output, tetapi format input dan output harus cocok. Misalnya memformat sebagai string

x^2+3x+5

atau sebagai daftar koefisien:

[1,3,5] or alternatively [5,3,1]

Selanjutnya polinomial input dapat diasumsikan diperluas penuh, dan outputnya juga diharapkan diperluas sepenuhnya.

Contohnya

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
cacat
sumber
bagaimana dengan builtin?
Maltysen
1
@Maltysen "Detail: Builtin diizinkan. (...)" : D
flawr
2
Saya pikir "format apa pun yang masuk akal" mungkin agak bisa diregangkan. Jika fungsi yang mengevaluasi polinom diperbolehkan, maka fungsi komposisi (.)adalah jawaban di Haskell. Anda mungkin bermaksud beberapa representasi dari daftar koefisien.
xnor
1
Judul! Saya baru saja mendapatkannya :-D
Luis Mendo
2
@LuisMendo Pemikir cepat = P
flawr

Jawaban:

10

Haskell, 86 72 byte

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

Menentukan fungsi osedemikian rupa sehingga o g fmenghitung komposisi f ∘ g. Polinomial diwakili oleh daftar koefisien kosong mulai dari suku konstan.

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]

Bagaimana itu bekerja

Tidak ada builtin atau perpustakaan terkait polinomial. Amati perulangan yang serupa

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₁ (g (x)) g (x),

untuk perkalian dan komposisi polinomial, masing-masing. Mereka berdua mengambil formulir

f (x) = a + f₁ (x) x ⇒ W (f) (x) = C (a) (x) + U (W (f₁)) (x).

Operator !memecahkan pengulangan formulir ini untuk W diberikan U dan C, menggunakanzipWith(+).(++[0,0..]) untuk penambahan polinomial (dengan asumsi argumen kedua lebih panjang-untuk tujuan kita, selalu akan menjadi). Kemudian,

(0:)mengalikan argumen polinomial dengan x (dengan mendahului koefisien nol);
(<$>g).(*)mengalikan argumen skalar dengan polinomial g;
(0:)!((<$>g).(*))mengalikan argumen polinomial dengan polinomial g;
puremengangkat argumen skalar ke polinomial konstan (daftar tunggal);
(0:)!((<$>g).(*))!puremenyusun argumen polinomial dengan polinomial g.

Anders Kaseorg
sumber
9

Mathematica, 17 byte

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

Contoh penggunaan:

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

              2       4
Out[17]= -96 x  + 48 x
feersum
sumber
7

TI-Basic 68k, 12 byte

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

Penggunaannya mudah, misalnya untuk contoh pertama:

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

Yang kembali

y^2+5y+9
cacat
sumber
Sepertinya curang bagi saya untuk meminta input dalam variabel yang berbeda. Apakah itu penting untuk jawaban ini?
feersum
Merasa bebas untuk melakukannya, saya secara eksplisit mengizinkan format input nyaman yang masuk akal.
flawr
Mengenai pengeditan komentar Anda: ya itu penting.
flawr
Saya tidak terlalu terbiasa dengan aturan di situs ini. Apakah benar menjadi 1 byte di TI-BASIC?
penanggung jawab
@asmeurer Memang: TI-Basic dinilai oleh pengkodean yang digunakan pada kalkulator yang sesuai. Jika Anda tertarik dengan detailnya, Anda dapat membacanya di sini di meta . Daftar token dapat ditemukan di sini di ti-basic-dev .
flawr
6

Python 2, 138 156 162 byte

Masukan diharapkan daftar bilangan bulat dengan kekuatan terkecil terlebih dahulu.

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

Tidak Disatukan:

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

Dalam perhitungan ini, koefisien polinomial dipandang sebagai digit (yang mungkin negatif) dari angka dalam basis yang sangat besar. Setelah polinomial berada dalam format ini, penggandaan atau penambahan adalah operasi integer tunggal. Selama basisnya cukup besar, tidak akan ada carry yang tumpah ke angka tetangga.

-18 dari meningkatkan terikat Bseperti yang disarankan oleh @xnor.

feersum
sumber
Metode yang bagus. Sebab B, apakah 10**len(`a+b`)cukup?
xnor
@ xnor Mungkin ... sulit bagi saya untuk mengatakannya.
feersum
+1 Ini adalah solusi yang sangat kreatif, dan penggunaan bigint yang bagus !!!
flawr
@ xnor Sekarang saya telah berhasil meyakinkan diri saya bahwa panjang koefisien hte adalah linear dalam panjang input :)
feersum
5

Python + SymPy, 59 35 byte

from sympy import*
var('x')
compose

Terima kasih kepada @asmeurer karena bermain golf 24 byte!

Uji coba

>>> from sympy import*
>>> var('x')
x
>>> f = compose
>>> f(x**2 + 3*x + 5, x + 1)
x**2 + 5*x + 9
Dennis
sumber
1
SymPy memiliki compose()fungsi.
penanggung jawab
1
Di mana jawabannya? Itu tidak lagi mendefinisikan fungsi atau melakukan apa pun ...
feersum
1
@feersum Itu tidak pernah terjadi. Anda baru saja mengedit posting meta itu.
Mego
3
@feersum Anda telah mengedit pos meta yang diterima untuk mengubah kebijakan untuk agenda Anda sendiri. Itu tidak baik.
Mego
3
@feersum Meskipun Anda mungkin berpikir kata-kata Anda tidak jelas, itu jelas bukan untuk anggota komunitas lainnya. Kami menerima konsensus yang from module import*;functionmerupakan pengajuan yang valid. Apapun itu, ini adalah kebijakan yang lebih baru, yang memungkinkan impor dan fungsi pembantu dengan lambda yang tidak disebutkan namanya.
Mego
3

Sage, 24 byte

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

Pada Sage 6.9 (versi yang berjalan di http://sagecell.sagemath.org ), fungsi panggilan tanpa penugasan argumen eksplisit (f(2) rather than f(x=2) ) menyebabkan pesan yang mengganggu dan tidak membantu dicetak ke STDERR. Karena STDERR dapat diabaikan secara default dalam kode golf, ini masih berlaku.

Ini sangat mirip dengan jawaban SymPy Dennis karena Sage adalah a) dibangun di atas Python, dan b) menggunakan Maxima , sistem aljabar komputer yang sangat mirip dengan SymPy dalam banyak hal. Namun, Sage jauh lebih kuat daripada Python dengan SymPy, dan dengan demikian merupakan bahasa yang cukup berbeda sehingga pantas untuk jawabannya sendiri.

Verifikasi semua kasus uji online

Mego
sumber
2

PARI / GP , 19 byte

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

yang memungkinkan Anda melakukannya

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

mendapatkan

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

Charles
sumber
1

MATLAB dengan Symbolic Toolbox, 28 byte

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

Ini adalah fungsi anonim. Untuk menyebutnya, tetapkan ke variabel atau gunakan ans. Input adalah string dengan format (spasi opsional)

x^2 + 3*x + 5

Contoh dijalankan:

>> @(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
sumber
1

Python 2, 239 232 223 byte

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)])

Implementasi 'tepat' yang tidak menyalahgunakan basis. Koefisien signifikan terkecil terlebih dahulu.

aadalah penambahan polinomial, madalah perkalian polinomial, dan okomposisi.

orlp
sumber
Bukankah m([c],e(m,[[1]]+[g]*k))sama dengan e(m,[[c]]+[g]*k)?
Neil
@Neil Panggilan bagus, bisa remas dua dalam satu dengan itu!
orlp
a=lambda*l:map(lambda x,y:(x or 0)+(y or 0),*l)
Anders Kaseorg
@AndersKaseorg Benar, saya menambahkannya, terima kasih :)
orlp
Dimungkinkan untuk menyederhanakan penambahan polinomial Anda, karena saya pikir satu daftar akan selalu lebih panjang dari yang lain, jadi Anda tidak perlu ( or 0)dalam versi itu.
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

Menerima dan mengembalikan polinomial sebagai array a = [a 0 , a 1 , 2 , ...] yang mewakili 0 + a 1 * x + a 2 * x 2 ...

Sunting: Disimpan 47 byte dengan beralih dari multiplikasi polinomial berulang ke berulang, yang kemudian memungkinkan saya untuk menggabungkan dua mappanggilan.

Penjelasan: r adalah hasilnya, yang dimulai dari nol, diwakili oleh array kosong, dan p adalah g h , yang dimulai pada satu. p dikalikan dengan masing-masing f h pada gilirannya, dan hasilnya terakumulasi dalam r . p juga dikalikan dengan g pada saat yang sama.

(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
sumber
1

Pyth, 51 34 byte

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

Suite uji .

Biarawati Bocor
sumber
2
saat python mengungguli pyth
downrep_nation
@downrep_nation tidak lagi :)
Leaky Nun
1

Ruby 2.4 + polinomial , 41 + 12 = 53 byte

Menggunakan bendera -rpolynomial. Input adalah dua Polynomialobjek.

Jika seseorang mengalahkan saya di vanilla Ruby (tidak ada perpustakaan eksternal polinomial), saya akan sangat terkesan.

->a,b{i=-1;a.coefs.map{|c|c*b**i+=1}.sum}
Nilai Tinta
sumber