Obróć korzenie

11

Biorąc pod uwagę niezerowy wielomian ze współczynnikami całkowitymi i pierwiastkami, które znajdują się na wyimaginowanej i rzeczywistej linii, tak że jeśli ajest to pierwiastek, to tak też jest -a, zwróć inny wielomian z pierwiastkami obróconymi o 90 stopni.

Detale

Wielomian można podać w dowolnym rozsądnym formacie, np. Jako listę współczynników. Warunek symetrii, który ajest pierwiastkiem wtedy i tylko wtedy, -agdy pierwiastek zbyt wymusza obrócony wielomian, aby miał również rzeczywiste współczynniki liczb całkowitych.

Przykłady

Poniżej wielomianów podano jako listę współczynników monomialów w malejącym stopniu. (tzn. stała jest ostatnia) Wielomian x^2-1ma pierwiastki {1,-1}. Obracanie ich poprzez 90°pomnożenie przez i(jednostkę urojoną), więc wielomian wyjściowy powinien mieć pierwiastki {i,-i}, czyli x^2 + 1.

Input / Output
[1 0 10 0 -127 0 -460 0 576]  [1 0 -10 0 -127 0 460 0 576]
[1 0 -4 0] [1 0 4 0]
[1] [1]
wada
źródło
Czy mogę przyjąć stopień wielomianu, a także wielomianu
Rohan Jhunjhunwala
Tak, myślę, że jest to do przyjęcia.
flawr
Wszystkie twoje przykłady wykorzystują monomiczne wielomiany. Czy możemy założyć, że wielomian wejściowy będzie moniczny? Czy wielomian wyjściowy musi być moniczny?
Dennis
Nie, może mieć również inne wiodące współczynniki niż 1, a wynik jest również zdefiniowany do całkowitej wielokrotności.
flawr
Wygląda na to, że format nie musi być listą współczynników. Jak daleko idą rozsądne formaty? Czy mój Format być wyrażeniem łańcuchowym w nieokreślonej x, tak, że moja uległość puszki string-wymienić xz (i*x)? Czy mój format może sformułować funkcję oceniającą wielomian, aby moje przesłanie skomponowało go z funkcją x -> i*x?
xnor

Odpowiedzi:

12

Mathematica, 10 bajtów

Czysta funkcja, która przyjmuje funkcję x i zastępuje w ix.

#/.x->I*x&

Alternatywnie z tylko 7 bajtami, ale nie do końca pewny, czy się liczy. Funkcja czysta, która przyjmuje funkcję czystą i zwraca funkcję x.

#[I*x]&
Ian Miller
źródło
5
I nawet nie potrzebujesz żadnych wbudowanych funkcji!
Neil
Jestem prawie pewien, że czysty wielomian funkcji jest „rozsądnym formatem” (tak jak tutaj był ). Używa go #jako zmiennej i ma &na końcu.
JungHwan Min
Głosowałbym za tym dwa razy, gdybym mógł
Greg Martin
Moją jedyną obawą dotyczącą drugiej odpowiedzi było niedopasowanie między wejściem (funkcja czysta) a wyjściem (funkcja x).
Ian Miller
6

Galaretka , 5 bajtów

Jı*Ċ×

Wypróbuj online!

Jak to działa

Mnoży pierwszy element przez 1, trzeci element przez -1itd.

Jı*Ċ×  argument: z
J      [1,2,...,len(z)]
 ı     i (the imaginary unit)
  *    to the power of (each element)
   Ċ   imaginary part
    ×  multiply by input (vectorize)

Dowód algorytmu

Niech wielomian będzie f(x).

Ponieważ mamy gwarancję, że jeśli xjest pierwiastkiem -x, to fmusi być , więc musi być parzyste, co oznacza, że ​​jego współczynnik dla mocy nieparzystych musi być 0.

Teraz obracanie korzeni 90°jest zasadniczo f(ix).

Rozwinięcie, a następnie porównanie współczynników potwierdza algorytm.

Leaky Nun
źródło
Więc nie musimy dotykać 2,4, 6, 8 itd.?
Rohan Jhunjhunwala
2
To i tak jest zero.
flawr
Twoja sztuczka ı*Ċjest bardzo fajna, powinieneś to wyjaśnić :)
Leo
@Leo Jest to jednak zasadniczo prosta implementacja ...
Leaky Nun
Logika tutaj nie jest całkiem słuszna, ponieważ zamiast tego możesz mieć wszystkie współczynniki dla parzystych mocy równe 0.
Ørjan Johansen
5

JavaScript (ES6), 25 bajtów

a=>a.map((e,i)=>i%4?-e:e)

Oryginalny wielomian ma rozwiązania w postaci, w x = ±aktórej leży na linii rzeczywistej lub urojonej. Z wyjątkiem kiedy a = 0(w takim przypadkux to czynnik wielomianu) oznacza to, że x² - a²jest on czynnikiem wielomianu (co oznacza, że ​​alternatywne warunki są zawsze równe zero). Teraz, gdy obracamy korzenie, współczynnik zmienia się na x² + a². Ponieważ wszystkie czynniki zmieniają się w tym samym czasie, trzeci element wielomianu, który jest sumą wszystkich -a²terminów, znak zmian, piąty, który jest sumą iloczynów par -a²terminów, zachowuje ten sam znak itp. , naprzemiennie co drugi termin.

Neil
źródło
4

Oktawa , 27 bajtów

@(x)round(poly(roots(x)*j))

Wypróbuj online!

Odnosi się to bezpośrednio do definicji: oblicz pierwiastki, pomnóż przez j, przekonwertuj z korzeni na wielomian. Ostateczne zaokrąglenie jest konieczne z powodu błędów liczb zmiennoprzecinkowych.

Luis Mendo
źródło
1

SILOS , 71 66 bajtów

readIO
b=i
lbla
readIO
d=c
d&2
i=i*(1-d)
printInt i
b-1
c+1
if b a

Wypróbuj online!

Nie mam pojęcia, co magia @Leaky Nun zrobiła tutaj, aby zaoszczędzić 5 bajtów.

Zajęło mi sekundę, żeby się domyślić, ale drugi kawałek C będzie się zmieniał tak, jak chcemy. Dlatego @Leaky Nun wykorzystała to, aby zaoszczędzić potrzebne nam bity.

Rohan Jhunjhunwala
źródło
66 bajtów
Leaky Nun
0

TI-Basic, 20 bajtów

seq(real(i^X/i)Ans(X),X,1,dim(Ans

Jeśli jest przechowywany prgmA, uruchom z:

{1, 0, 3, 0, 1}:prgmA

seq(musiałem być jedynym * poleceniem, które nie obsługuje liczb zespolonych. :)

*: Przesada

pizzapanty184
źródło
0

Casio-Basic, 8 bajtów

n|x=𝑖x

Funkcja nienazwana, wykorzystująca podejście Matematyki Iana Millera. Należy użyć fikcyjnego 𝑖 z klawiatury Math2 (liczy się jako 2 bajty, kod char 769), a wielomian należy wprowadzić jako równaniex .

7 bajtów dla kodu, 1 bajt do określenia njako parametr.

Objaśnienie : wyraża równanie n, a następnie po prostu zastępuje wszystkie wystąpienia xz 𝑖x.

NumberManiac
źródło
0

Stax , 5 bajtów

Æ[]▐↨

Uruchom i debuguj online!

Port galaretki odpowiedź.

Używa reprezentacji ASCII do wyjaśnienia:

mih|1*
m         Map each element with rest of program, print mapped results on individual lines
 i        Current 0-based loop index
  h       Floor(i/2)
   |1     (-1)^(i/2)
     *    Multiply with current element

Jeśli mogą istnieć zera wiodące, należy je najpierw przyciąć i można to zrobić kosztem innego bajtu.

Weijun Zhou
źródło