Biorąc pod uwagę dwie niepuste listy liczb całkowitych, twoje zgłoszenie powinno obliczyć i zwrócić dyskretny splot tych dwóch. Co ciekawe, jeśli weźmiesz pod uwagę elementy listy jako współczynniki wielomianów, splot dwóch list reprezentuje współczynniki iloczynu dwóch wielomianów.

Definicja

Biorąc pod uwagę listy A=[a(0),a(1),a(2),...,a(n)]i B=[b(0),b(1),b(2),...,b(m)](ustawienie a(k)=0 for k<0 and k>ni b(k)=0 for k<0 and k>m), splot dwóch jest zdefiniowany jako A*B=[c(0),c(1),...,c(m+n)]gdziec(k) = sum [ a(x)*b(y) for all integers x y such that x+y=k]

Zasady

• Dozwolone jest dowolne wygodne formatowanie danych wejściowych i wyjściowych dla twojego języka.
• Wbudowane splot, tworzenie macierzy splotów, korelacja i mnożenie wielomianowe są niedozwolone.

Przykłady

[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 bajtów

[:+//.*/

Stosowanie:

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

Opis: Program pobiera dwie listy, tworzy tabliczkę mnożenia, a następnie dodaje liczby na dodatnich przekątnych.

MATL , 19 bajtów

PiYdt"TF2&YStpsw]xx

Wypróbuj online!

Wyjaśnienie

To buduje macierz blokowo-diagonalną z dwoma wejściami, odwracając pierwszy. Na przykład, z wejściami [1 4 3 5], [1 3 2]matryca jest

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

Każde wejście splotu uzyskuje się poprzez przesunięcie pierwszego rzędu o jedną pozycję w prawo, obliczenie iloczynu każdej kolumny i zsumowanie wszystkich wyników.

Zasadniczo przesuwanie powinno odbywać się wypełnianiem zerami od lewej strony. Odpowiednio można zastosować przesunięcie kołowe , ponieważ macierz zawiera zera przy odpowiednich wpisach.

Na przykład pierwszy wynik jest uzyskiwany z przesuniętej matrycy

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

i tak jest 1*1 == 1. Drugi uzyskano z

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

i tak jest 4*1+1*3 == 7itd. Należy to zrobić m+n-1razy, gdzie mi jakie nsą długości wejściowe. Kod używa pętli z m+niteracjami (która oszczędza niektóre bajty) i odrzuca ostatni wynik.

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 bajtów

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

Definiuje operatora #.

Matlab / Octave, 41 bajtów

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

Definiuje to anonimową funkcję. Aby go wywołać, przypisz go do zmiennej lub użyj ans.

Wypróbuj tutaj .

Wyjaśnienie

Wykorzystuje to fakty, które

• (Prawdopodobnie powtórzone) pierwiastki charakteryzują wielomian aż do jego wiodącego współczynnika.
• Iloczyn dwóch wielomianów ma swoje korzenie.

Kod oblicza pierwiastki dwóch wielomianów (funkcji roots) i łączy je w tablicę kolumn. Z tego uzyskuje się współczynniki wielomianu produktu z wiodącą 1(funkcją poly). Na koniec wynik mnoży się przez wiodące współczynniki dwóch wielomianów.

Oktawa , 48 bajtów

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

Wypróbuj tutaj .

Wyjaśnienie

Dyskretny splot odpowiada zwielokrotnieniu (dyskretnego czasu) przekształceń Fouriera. Tak więc jednym ze sposobów pomnożenia wielomianów byłoby ich przekształcenie, pomnożenie transformowanych sekwencji i przekształcenie z powrotem.

Jeśli zastosowana zostanie dyskretna transformata Fouriera (DFT) zamiast transformaty Fouriera, wynikiem będzie kołowy splot oryginalnych sekwencji współczynników wielomianowych. Kod podąża tą drogą. Aby splot kołowy był równy splotowi standardowemu, sekwencje są zerowane i wynik jest przycinany.

05AB1E , 18 17 bajtów

Kod

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

Wyjaśnienie

Teoria leżąca u podstaw:

Aby znaleźć splot, weźmy przykład [1, 2, 3], [3, 4, 5]. Ustawiamy wartości pierwszej tablicy do góry nogami i pionowo, w następujący sposób:

3
2
1

Teraz umieszczamy drugą tablicę jak drabinę i mnożymy ją przez:

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

W wyniku czego:

        9   12   15
    6   8   10
3   4   5

Następnie dodajemy je, w wyniku czego:

        9   12   15
    6   8   10
3   4   5       

3   10  22  22   15

Tak więc splot jest [3, 10, 22, 22, 15].

Sam kod:

Zrobimy to krok po kroku, używając [1, 2, 3], [3, 4, 5]jako przypadku testowego.

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

Najpierw pchamy, 0a następnie Ewyceniamy pierwszą tablicę wejściową. Mapujemy każdy element za pomocą v.

Tak więc dla każdego elementu wciskamy drugą tablicę za pomocą, ²a następnie długość pierwszej tablicy za pomocą ¹gi zmniejszamy ją o 1 (za pomocą <). Przekształcamy to w listę zer z zerami (długość 1. tablicy - 1) , używając Å0i dołączając to do naszej listy. Nasz stos wygląda teraz tak dla pierwszego elementu na liście danych wejściowych:

[3, 4, 5, 0, 0]

Mnożymy tę tablicę przez bieżący element, za pomocą y*. Następnie wciskamy N, co wskazuje indeks bieżącego elementu (indeksowany od zera) i obracamy tablicę, która wiele razy w prawo za pomocą FÁ}. Na koniec dodajemy to do naszej wartości początkowej ( 0). Tak więc zasadniczo wykonuje się następujące czynności:

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

[3, 10, 22, 22, 15]

Który jest następnie domyślnie drukowany. Wykorzystuje kodowanie CP-1252 . Wypróbuj online! .

Galaretka , 9 bajtów

0;+
×'Ṛç/

Wypróbuj online! lub zweryfikuj wszystkie przypadki testowe .

Jak to działa

×'Ṛç/  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.

Łuska , 5 bajtów

mΣ∂Ṫ*

Wypróbuj online!

Uwaga: Podając listę zero-wielomianową / pustą, musisz określić jej typ (tj. []:LN)!

Wyjaśnienie

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 bajty

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

Wypróbuj online!

Tworzy macierz wszystkich iloczynów elementarnych danych wejściowych, a następnie sumuje wzdłuż przekątnych. Na ,1końcu zmusza matlab do sumowania wzdłuż poprawnego kierunku, gdy jeden z wektorów wejściowych ma długość 1.

W Octave spdiagsnie działa dla wektorów, co powoduje błąd, gdy jedno z danych wejściowych ma długość 1. Do wyraźnego rozszerzenia produktu opartego na elementach wymagany jest Matlab 2016b lub nowszy.

Rubinowy, 83 bajty

Niemal bezpośrednio wyciągnąłem odpowiedź, którą zrobiłem wcześniej, dotyczącą rozwijania korzeni w wielomian .

->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 bajtów

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 bajty

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

Zwraca pustą tablicę, jeśli dane wejściowe są puste. Na podstawie mojej odpowiedzi na wielomiany .

Julia, 62 55 bajtów

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

Wypróbuj online!

Clojure, 104 bajty

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

Połączenie w celu sorted-mapzagwarantowania, że ​​wartości są zwracane we właściwej kolejności. Chciałbym, żeby było jeszcze kilka przypadków testowych.