Wielomian charakterystyczny macierzy kwadratowej A jest zdefiniowane jako wielomian p A (x) = det ( I X ), gdzie I jest macierzą jednostkową , a det się determinant . Zauważ, że ta definicja zawsze daje nam monomiczny wielomian, dzięki czemu rozwiązanie jest unikalne.
Twoim zadaniem w tym wyzwaniu jest obliczenie współczynników charakterystycznego wielomianu dla macierzy o wartości całkowitej, do tego możesz użyć wbudowanych, ale jest to odradzane.
Zasady
- wejście to macierz liczb całkowitych NxN (N ≥ 1) w dowolnym dogodnym formacie
- twój program / funkcja wyświetli / zwróci współczynniki w kolejności rosnącej lub malejącej (proszę określić, które)
- współczynniki są normowane w taki sposób, że współczynnik x N wynosi 1 (patrz przypadki testowe)
- nie musisz obsługiwać nieprawidłowych danych wejściowych
Przypadki testowe
Współczynniki podano w porządku malejącym (tj. X N , x N-1 , ..., x 2 , x, 1):
[0] -> [1 0]
[1] -> [1 -1]
[1 1; 0 1] -> [1 -2 1]
[80 80; 57 71] -> [1 -151 1120]
[1 2 0; 2 -3 5; 0 1 1] -> [1 1 -14 12]
[4 2 1 3; 4 -3 9 0; -1 1 0 3; 20 -4 5 20] -> [1 -21 -83 559 -1987]
[0 5 0 12 -3 -6; 6 3 7 16 4 2; 4 0 5 1 13 -2; 12 10 12 -2 1 -6; 16 13 12 -4 7 10; 6 17 0 3 3 -1] -> [1 -12 -484 3249 -7065 -836601 -44200]
[1 0 0 1 0 0 0; 1 1 0 0 1 0 1; 1 1 0 1 1 0 0; 1 1 0 1 1 0 0; 1 1 0 1 1 1 1; 1 1 1 0 1 1 1; 0 1 0 0 0 0 1] -> [1 -6 10 -6 3 -2 0 0]
[ 1.00000000e+00 -1.51000000e+02 1.12000000e+03]
na przykład generować dane wyjściowe ?Odpowiedzi:
SageMath , 3 bajty
5 bajtów zapisanych dzięki @Mego
Wypróbuj online!
Pobiera
Matrix
jako dane wejściowe.fcp
oznacza f actorization o c haracteristic p olynomial,który jest krótszy niż normalne wbudowane
charpoly
.źródło
Oktawa ,
164 bajtów@ BruteForce właśnie powiedział mi, że jedna z funkcji, z których korzystałem w poprzednim rozwiązaniu, może faktycznie wykonać całą pracę:
Wypróbuj online!
16 bajtów: To rozwiązanie oblicza wartości własne macierzy wejściowej, a następnie buduje wielomian z podanych pierwiastków.
Ale oczywiście jest też nudno
(potrzebuje
symbolic
matrycy typów w Octave, ale działa ze zwykłymi macierzami w MATLAB.)Wypróbuj online!
źródło
Pari / GP , 8 bajtów
Wypróbuj online!
Pari / GP , 14 bajtów
Wypróbuj online!
źródło
x
macierz o odpowiednim wymiarze? Ładny!R , 53 bajty
Wypróbuj online!
Zwraca współczynniki w porządku rosnącym; tj
a_0, a_1, a_2, ..., a_n
.Oblicza wielomian, znajdując wartości własne macierzy.
R + pracma , 16 bajtów
pracma
jest biblioteką „PRACtical MAth” dla języka R i ma całkiem sporo przydatnych funkcji.źródło
Mathematica, 22 bajty
-7 bajtów od alephalpha
-3 bajtów od Misha Lavrov
Wypróbuj online!
i oczywiście...
Mathematica, 29 bajtów
Wypróbuj online!
obie odpowiedzi generują wielomian
źródło
Haskell ,
243 223222 bajtówWypróbuj online!
Dzięki @ ØrjanJohansen za pomoc w golfa!
Wyjaśnienie
Wykorzystuje on algorytm Faddeev – LeVerrier do obliczenia współczynników. Oto nie golfowa wersja z bardziej szczegółowymi nazwami:
Uwaga: wziąłem to prosto z tego rozwiązania
źródło
c=z pure[1..]a
.f a|let c=z pure[0..]a;g(u,d)k|m<-[z(+)a b|(a,b)<-a#u&[[s[d|x==y]|y<-c]|x<-c]]=(m,-s[a#m!!n!!n|n<-c]`div`(k+1))=snd<$>scanl g(0<$c<$c,1)c
, że coś podobnego powinno działać również na drugim.Python 2 + numpy , 23 bajty
Wypróbuj online!
źródło
MATL , 4 bajty
Wypróbuj online!
To tylko port odpowiedzi flawr na Octave , więc zwraca współczynniki w malejącej kolejności, tj.
[a_n, ..., a_1, a_0]
źródło
CJam (48 bajtów)
Zestaw testów online
Sekcja
Jest to dość podobne do mojej odpowiedzi na Determinant macierzy liczb całkowitych . Ma pewne poprawki, ponieważ znaki są różne i ponieważ chcemy zachować wszystkie współczynniki, a nie tylko ostatni.
źródło