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>n
i 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]
[1,1]*[] = []
i nie może być możliwe[]*[] = ?
. Konwolucja nie jest dobrze zdefiniowana na pustych listach. Myślę, że powinieneś zagwarantować, że listy wejściowe są niepuste.Odpowiedzi:
J,
108 bajtówStosowanie:
Opis: Program pobiera dwie listy, tworzy tabliczkę mnożenia, a następnie dodaje liczby na dodatnich przekątnych.
źródło
MATL , 19 bajtów
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 jestKaż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
i tak jest
1*1 == 1
. Drugi uzyskano zi tak jest
4*1+1*3 == 7
itd. Należy to zrobićm+n-1
razy, gdziem
i jakien
są długości wejściowe. Kod używa pętli zm+n
iteracjami (która oszczędza niektóre bajty) i odrzuca ostatni wynik.źródło
Haskell,
5549 bajtówDefiniuje operatora
#
.źródło
[0,0..]
może(0<$b)
dać dokładnie potrzebną długość, pozwalając na opróżnienie podstawy_#b=0<$b
.Matlab / Octave, 41 bajtów
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
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.źródło
Oktawa , 48 bajtów
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.
źródło
05AB1E ,
1817 bajtówKod
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:Teraz umieszczamy drugą tablicę jak drabinę i mnożymy ją przez:
W wyniku czego:
Następnie dodajemy je, w wyniku czego:
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.Najpierw pchamy,
0
a następnieE
wyceniamy 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ą¹g
i zmniejszamy ją o 1 (za pomocą<
). Przekształcamy to w listę zer z zerami (długość 1. tablicy - 1) , używającÅ0
i dołączając to do naszej listy. Nasz stos wygląda teraz tak dla pierwszego elementu na liście danych wejściowych:Mnożymy tę tablicę przez bieżący element, za pomocą
y*
. Następnie wciskamyN
, 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:Który jest następnie domyślnie drukowany. Wykorzystuje kodowanie CP-1252 . Wypróbuj online! .
źródło
Galaretka , 9 bajtów
Wypróbuj online! lub zweryfikuj wszystkie przypadki testowe .
Jak to działa
źródło
Łuska , 5 bajtów
Wypróbuj online!
Uwaga: Podając listę zero-wielomianową / pustą, musisz określić jej typ (tj.
[]:LN
)!Wyjaśnienie
źródło
Matlab, 33 bajty
Wypróbuj online!
Tworzy macierz wszystkich iloczynów elementarnych danych wejściowych, a następnie sumuje wzdłuż przekątnych. Na
,1
końcu zmusza matlab do sumowania wzdłuż poprawnego kierunku, gdy jeden z wektorów wejściowych ma długość 1.W Octave
spdiags
nie 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.źródło
Rubinowy, 83 bajty
Niemal bezpośrednio wyciągnąłem odpowiedź, którą zrobiłem wcześniej, dotyczącą rozwijania korzeni w wielomian .
źródło
Python, 90 bajtów
źródło
JavaScript (ES6), 64 bajty
Zwraca pustą tablicę, jeśli dane wejściowe są puste. Na podstawie mojej odpowiedzi na wielomiany .
źródło
Julia,
6255 bajtówWypróbuj online!
źródło
Clojure, 104 bajty
Połączenie w celu
sorted-map
zagwarantowania, że wartości są zwracane we właściwej kolejności. Chciałbym, żeby było jeszcze kilka przypadków testowych.źródło