Diberi dua daftar bilangan bulat kosong , kiriman Anda harus menghitung dan mengembalikan konvolusi diskrit keduanya. Menariknya, jika Anda mempertimbangkan elemen daftar sebagai koefisien polinomial, lilitan kedua daftar mewakili koefisien produk dari dua polinomial.

Definisi

Diberikan daftar A=[a(0),a(1),a(2),...,a(n)]dan B=[b(0),b(1),b(2),...,b(m)](pengaturan a(k)=0 for k<0 and k>ndan b(k)=0 for k<0 and k>m) maka lilitan keduanya didefinisikan sebagai A*B=[c(0),c(1),...,c(m+n)]manac(k) = sum [ a(x)*b(y) for all integers x y such that x+y=k]

Aturan

• Input dan output format apa pun yang nyaman untuk bahasa Anda diizinkan.
• Built-in untuk konvolusi, membuat matriks konvolusi, korelasi dan multiplikasi polinomial tidak diperbolehkan.

Contohnya

[1,1]*[1] = [1,1]
[1,1]*[1,1] = [1,2,1]
[1,1]*[1,2,1] = [1,3,3,1]
[1,1]*[1,3,3,1] = [1,4,6,4,1]
[1,1]*[1,4,6,4,1] = [1,5,10,10,5,1]

[1,-1]*[1,1,1,1,1] = [1,0,0,0,0,-1]
[80085,1337]*[-24319,406] = [-1947587115,7,542822]

J, 10 8 byte

[:+//.*/

Pemakaian:

ppc =: [:+//.*/    NB. polynomial product coefficients 
80085 1337 ppc _24319 406
_1947587115 7 542822

Deskripsi: Program ini mengambil dua daftar, membuat tabel perkalian, lalu menambahkan angka pada diagonal positif.

MATL , 19 byte

PiYdt"TF2&YStpsw]xx

Cobalah online!

Penjelasan

Ini membangun matriks blok-diagonal dengan dua input, membalikkan yang pertama. Misalnya, dengan input [1 4 3 5], [1 3 2]matriksnya adalah

[ 5 3 4 1 0 0 0
  0 0 0 0 1 3 2 ]

Setiap entri konvolusi diperoleh dengan menggeser baris pertama satu posisi ke kanan, menghitung produk dari setiap kolom, dan menjumlahkan semua hasil.

Pada prinsipnya, pergeseran harus dilakukan padding dengan nol dari kiri. Secara ekuivalen, penggeseran lingkaran dapat digunakan, karena matriks berisi nol pada entri yang sesuai.

Sebagai contoh, hasil pertama diperoleh dari matriks bergeser

[ 0 5 3 4 1 0 0
  0 0 0 0 1 3 2 ]

dan karenanya 1*1 == 1. Yang kedua diperoleh dari

[ 0 0 5 3 4 1 0
  0 0 0 0 1 3 2 ]

dan dengan demikian 4*1+1*3 == 7, dll. Ini harus dilakukan m+n-1kali, di mana mdan nmerupakan panjang input. Kode menggunakan loop dengan m+niterasi (yang menyimpan beberapa byte) dan membuang hasil terakhir.

P          % Take first input (numeric vactor) implicitly and reverse it
i          % Take second input (numeric vactor) 
Yd         % Build diagonal matrix with the two vectors
t          % Duplicate
"          % For each column of the matrix
  TF2&YS   %   Circularly shift first row 1 step to the right
  t        %   Duplicate
  p        %   Product of each column
  s        %   Sum all those products
  w        %   Swap top two elements in stack. The shifted matrix is left on top
]          % End for
xx         % Delete matrix and last result. Implicitly display

Haskell, 55 49 byte

(a:b)#c=zipWith(+)(0:b#c)$map(a*)c++[]#b
_#c=0<$c

Menentukan operator #.

Matlab / Oktaf, 41 byte

@(p,q)poly([roots(p);roots(q)])*p(1)*q(1)

Ini mendefinisikan fungsi anonim. Untuk menyebutnya, tetapkan ke variabel atau gunakan ans.

Coba di sini .

Penjelasan

Ini mengeksploitasi fakta itu

• Akar (mungkin diulang) menandai polinomial hingga koefisien terdepan.
• Produk dari dua polinomial memiliki akar keduanya.

Kode menghitung akar dari dua polinomial (fungsi roots) dan menggabungkannya menjadi array kolom. Dari sana ia memperoleh koefisien polinomial produk dengan 1fungsi ( terkemuka poly). Akhirnya hasilnya dikalikan dengan koefisien terkemuka dari dua polinomial.

Oktaf , 48 byte

@(p,q)ifft(fft([p q*0]).*fft([q p*0]))(1:end-1)

Coba di sini .

Penjelasan

Konvolusi diskrit berhubungan dengan multiplikasi transformasi Fourier (waktu diskrit). Jadi salah satu cara untuk melipatgandakan polinomial adalah mengubahnya, mengalikan urutan yang ditransformasikan, dan mentransformasikannya kembali.

Jika transformasi Fourier diskrit (DFT) digunakan sebagai pengganti transformasi Fourier, hasilnya adalah konvolusi melingkar dari urutan asli dari koefisien polinomial. Kode mengikuti rute ini. Untuk membuat lilitan melingkar sama dengan lilitan standar, urutannya berlapis-nol dan hasilnya dipangkas.

05AB1E , 18 17 byte

Kode

0Ev²¹g<Å0«y*NFÁ}+

Penjelasan

Teori di balik:

Untuk menemukan konvolusi, mari kita ambil contoh [1, 2, 3], [3, 4, 5]. Kami memposisikan nilai-nilai dari array pertama terbalik dan vertikal, seperti ini:

3
2
1

Sekarang, kita menempatkan array kedua seperti tangga dan melipatgandakannya dengan:

3 ×       [3  4  5]
2 ×    [3  4  5]
1 × [3  4  5]

Menghasilkan:

        9   12   15
    6   8   10
3   4   5

Kemudian, kami menambahkannya, menghasilkan:

        9   12   15
    6   8   10
3   4   5       

3   10  22  22   15

Jadi, konvolusi itu [3, 10, 22, 22, 15].

Kode itu sendiri:

Kami akan melakukan langkah demi langkah menggunakan [1, 2, 3], [3, 4, 5]sebagai kasus uji.

0Ev²¹g<Å0«y*NFÁ}+

Kami pertama-tama mendorong 0dan kemudian kami Emenilai array input pertama. Kami memetakan setiap elemen menggunakan v.

Jadi, untuk setiap elemen, kita dorong array kedua dengan ²dan kemudian panjang array pertama menggunakan ¹gdan mengurangi ini dengan 1 (dengan <). Kami mengonversikan ini menjadi daftar nol dengan (panjang array 1 - 1) nol, menggunakan Å0dan menambahkan ini ke daftar kami. Tumpukan kami sekarang terlihat seperti ini untuk item pertama dalam daftar input:

[3, 4, 5, 0, 0]

Kami mengalikan array ini dengan item saat ini, selesai dengan y*. Setelah itu, kami mendorong N, yang menunjukkan indeks item saat ini (diindeks nol) dan memutar array yang berkali-kali ke kanan menggunakan FÁ}. Akhirnya, kami menambahkan ini ke nilai awal kami ( 0). Jadi, yang pada dasarnya dilakukan adalah sebagai berikut:

[0, 0, 9, 12, 15] +
[0, 6, 8, 10, 0] +
[3, 4, 5, 0, 0] =

[3, 10, 22, 22, 15]

Yang kemudian dicetak secara implisit. Menggunakan pengodean CP-1252 . Cobalah online! .

Jelly , 9 byte

0;+
×'Ṛç/

Cobalah online! atau verifikasi semua kasus uji .

Bagaimana itu bekerja

×'Ṛç/  Main link. Arguments: p, q (lists)

×'     Spawned multiplication; multiply each item of p with each item of q.
  Ṛ    Reverse the rows of the result.
   ç/  Reduce the rows by the helper link.


0;+    Helper link. Arguments: p, q (lists)

0;     Prepend a 0 to p.
  +    Perform vectorized addition of the result and q.

Sekam , 5 byte

mΣ∂Ṫ*

Cobalah online!

Catatan: Saat memasok daftar nol-polinomial / kosong, Anda perlu menentukan tipenya (mis. []:LN)!

Penjelasan

mΣ∂Ṫ*  -- implicit inputs xs ys, for example: [1,-1] [1,1]
   Ṫ*  -- compute the outer product xsᵀ·ys: [[1,1],[-1,-1]]
  ∂    -- diagonals: [[1],[1,-1],[-1]]
mΣ     -- map sum: [1,0,1]

Matlab, 33 byte

@(x,y)sum(spdiags(flip(x').*y),1)

Cobalah online!

Buat matriks semua produk elemen-bijaksana dari input, kemudian jumlahkan sepanjang diagonal. Pada ,1akhirnya memaksa matlab untuk menjumlahkan sepanjang arah yang benar ketika salah satu vektor input memiliki panjang 1.

Dalam Oktaf spdiagstidak bekerja untuk vektor, menghasilkan kesalahan ketika salah satu input memiliki panjang 1. Matlab 2016b atau lebih baru diperlukan untuk perluasan eksplisit produk elemen-bijaksana.

Ruby, 83 byte

Hampir secara langsung menarik keluar dari jawaban yang saya lakukan sebelumnya mengenai memperluas akar menjadi polinomial .

->a,b{q=a.map{|c|r=b.map{|e|e*c};b=[0]+b;r}
q.pop.zip(*q).map{|e|(e-[p]).reduce:+}}

Python, 90 byte

lambda p,q:[sum((p+k*[0])[i]*(q+k*[0])[k-i]for i in range(k+1))for k in range(len(p+q)-1)]

JavaScript (ES6), 64 byte

(a,b)=>a.map((n,i)=>b.map((m,j)=>r[j+=i]=m*n+(r[j]||0)),r=[])&&r

Mengembalikan array kosong jika salah satu input kosong. Berdasarkan jawaban saya terhadap Polinomialepsi .

Julia, 62 55 byte

~=endof
p%q=[sum(diag(p*rot180(q'),-k))for k=1-~q:~p-1]

Cobalah online!

Clojure, 104 byte

#(vals(apply merge-with +(sorted-map)(for[i(range(count %))j(range(count %2))]{(+ i j)(*(% i)(%2 j))})))

Penggabungan untuk sorted-mapmenjamin bahwa nilai dikembalikan dalam urutan yang benar. Saya berharap ada beberapa test case lagi.