Znajdź integralne pierwiastki wielomianu

19

Wyzwanie

Wyzwaniem jest zapisanie programu, uwzględniający współczynniki dowolnego n stopni równania wielomianowego na wejściu i zwraca integralne wartości x, dla której jest prawdziwe równanie. Współczynniki zostaną podane jako dane wejściowe w kolejności malejącej lub zwiększającej moc. Możesz założyć, że wszystkie współczynniki są liczbami całkowitymi .

Wejście i wyjście

Dane wejściowe będą stanowić współczynniki równania w malejącym lub rosnącym porządku mocy. Stopień równania, tj. Maksymalna moc x, jest zawsze o 1 mniejszy niż całkowita liczba elementów na wejściu.

Na przykład:

[1,2,3,4,5] -> represents x^4 + 2x^3 + 3x^2 + 4x + 5 = 0 (degree = 4, as there are 5 elements)
[4,0,0,3] -> represents 4x^3 + 3 = 0 (degree = 3, as there are 3+1 = 4 elements)

Wynik powinien być tylko wyraźnymi wartościami całkowitymi x, które spełniają podane równanie. Wszystkie współczynniki wejściowe są liczbami całkowitymi, a wielomian wejściowy nie będzie wielomianem zerowym . Jeśli nie ma rozwiązania dla danego równania, wynik jest niezdefiniowany.

Jeśli równanie ma powtarzające się pierwiastki, wyświetl ten konkretny pierwiastek tylko raz. Możesz wyprowadzać wartości w dowolnej kolejności. Załóżmy również, że dane wejściowe będą zawierać co najmniej 2 liczby.

Przykłady

[1,5,6] -> (-3,-2)
[10,-42,8] -> (4)
[1,-2,0] -> (0,2)
[1, 1, -39, -121, -10, 168] -> (-4, -3, -2, 1, 7)
[1, 0, -13, 0, 36] -> (-3, -2, 2, 3)
[1,-5] -> (5)
[1,2,3] -> -

Zauważ, że równanie w drugim przykładzie ma również pierwiastek 0.2, ale nie jest wyświetlane, ponieważ 0.2 nie jest liczbą całkowitą.

Punktacja

To jest , więc wygrywa najkrótszy kod (w bajtach)!

Manish Kundu
źródło
7
Uwaga: Przed przystąpieniem do głosowania, aby zamknąć, należy uznać, że to pytanie jest nie duplikat tej jednej . Mogę wymyślić co najmniej jedno podejście do tego problemu, które nie będzie w sposób trywialny modyfikowalne dla drugiego wyzwania (chociaż nie mówię co; to pozostawia tobie; P).
Erik the Outgolfer
Czy możemy założyć, że musimy przywrócić korzenie tylko w granicach liczb całkowitych naszego języka? A może algorytm zadziała, nawet jeśli zakres typów liczb całkowitych języków zostanie zwiększony, ale zachowanie pozostanie takie samo.
Οurous
1
Czy możemy również użyć rodzimego typu wielomianowego, jeśli Twój język je obsługuje?
flawr
1
Czy programy działające bez końca nie są akceptowane?
Jack M
1
To ma uprościć sprawę.
Manish Kundu

Odpowiedzi:

6

MATL , 13 12 bajtów

|stE:-GyZQ~)

Wypróbuj online!

Wykorzystuje to fakt, że dla współczynników całkowitych wartość bezwzględna dowolnego pierwiastka jest ściśle mniejsza niż suma wartości bezwzględnych współczynników.

Wyjaśnienie

Rozważ dane wejściowe [1 5 6]jako przykład.

|    % Implicit input. Absolute value
     % STACK: [1 5 6]
s    % Sum
     % STACK: 12
t    % Duplicate
     % STACK: 12, 12
E    % Multiply by 2
     % STACK: 12, 24
:    % Range
     % STACK: 12, [1 2 ... 23 24]
-    % Subtract, elemet-wise
     % STACK: [11 10 ... -11 -12]
G    % Push input again
     % STACK: [11 10 ... -11 -12], [1 5 6]
y    % Duplicate from below
     % STACK: [11 10 ... -11 -12], [1 5 6], [11 10 ... -11 -12]
ZQ   % Polyval: values of polynomial at specified inputs
     % STACK: [11 10 ... -11 -12], [182 156 ... 72 90]
~    % Logical negation: turns nonzero into zero
     % STACK: [11 10 ... -11 -12], [0 0 ... 0] (contains 1 for roots)
)    % Index: uses second input as a mask for the first. Implicit display
     % STACK: [-3 -2]
Luis Mendo
źródło
3
Alternatywą dla twierdzenia Rouchego byłoby także uzasadnienie twierdzenia o wymiernych korzeniach, aby uzasadnić zastosowane ograniczenie. Zgodnie z twierdzeniem Rational Roots wszystkie pierwiastki całkowite są ograniczone w wartości bezwzględnej przez maksimum wartości bezwzględnych współczynników, ściślejsze niż suma. Lub jeszcze ściślej, o wartość bezwzględną „ostatniego” niezerowego współczynnika - tj. Współczynnika najmniejszej potęgi x, która ma niezerowy współczynnik. (Prawdopodobnie nie pomaga zaoszczędzić żadnych bajtów, tylko alternatywny dowód, ponieważ RRT jest prawdopodobnie bardziej znany niż Rouche dla większości ludzi.) :)
matmandan
1
@mathmandan takie podejście jest o trzy bajty dłuższe: spróbuj tutaj , chociaż jestem pewien, że przegapiłem lewę lub dwie
Giuseppe
@Giuseppe Podziękowania dla obu. Może X>t_w&:GyZQ~), ale wciąż 13 bajtów
Luis Mendo
1
... ale znalazłem krótszą alternatywę dla zakresu
Luis Mendo
5

Łuska , 10 9 bajtów

-1 bajt dzięki Zgarb

uSȯf¬`Bṁṡ

Wypróbuj online!

Wyjaśnienie

       ṁṡ   Concatenate together the symmetric ranges of each coefficient
            (It is guaranteed that the integer roots lie in the range [-n..n],
                        where n is the coefficient with the largest magnitude)
 Sȯf        Find all the values in that range which
    ¬       are zero
     `B     when plugged through the polynomial
            (Base conversion acts as polynomial evaluation)
u           De-duplicate the roots
H.PWiz
źródło
Możesz to zrobić ṁṡzamiast, oṡ►ajeśli później deduplikujesz.
Zgarb
@Zgarb Very nice! Dzięki
H.PWiz
5

Haskell , 54 bajty

f l|t<-sum$abs<$>l=[i|i<-[-t..t],foldl1((+).(i*))l==0]

Wypróbuj online!

Brutalna siła i podział syntetyczny.

Niegolfowany z UniHaskell i-XUnicodeSyntax

import UniHaskell

roots     Num a  [a]  [a]
roots xs = [r | r  -bound  bound, foldl1 ((+)  (r ×)) xs  0]
             where bound = sum $ abs § xs

Alternatywne rozwiązanie, 44 bajty

Podziękowania dla nich.

f l=[i|i<-[minBound..],foldl1((+).(i*))l==0]

Życzymy powodzenia w wypróbowywaniu go online , ponieważ sprawdza on każdą liczbę w Intzakresie.

całkowicie ludzki
źródło
Można iteracyjne inad [minBound..]i upuść całą trzecz. Połączenia fz wyraźnymi Intlistami, np f [1::Int,5,6]. Oczywiście nie kończy się to w rozsądnym czasie.
nimi
@nimi Dlaczego to miałoby się kiedykolwiek skończyć? Czy nie zapętliby się w nieskończoność?
całkowicieludzki
Nie, Boundedtypy zatrzymują się maxBoundnp print [minBound::Bool ..].
nimi
4

Python 2 + numpy, 95 93 91 103 93 91 82 bajtów

-2 bajty dzięki ovs
dzięki Luis Mendo za górne / dolne granice korzeni
-10 bajtów dzięki Mr. Xcoder

from numpy import*
def f(r):s=sum(fabs(r));q=arange(-s,s);print q[polyval(r,q)==0]

Wypróbuj online!

Pręt
źródło
@LuisMendo tak.
Rod
3
Nasz obecny konsensus wydaje się być taki, że programy muszą zawsze kończyć się, chyba że wyzwanie stanowi inaczej.
Zgarb
@Zgarb tam, naprawiono!
Rod
Użycie numpy.polyvaloszczędza sporo bajtów
Mr. Xcoder
4

Wolfram Language (Mathematica) , 50 47 42 25 27 bajtów

{}⋃Select[x/.Solve[#~FromDigits~x==0],IntegerQ]&

Wypróbuj online!

Aktualizacja: korzystając z faktu Luisa Mendo, grał w golfa o kolejne 3 bajty

Pick[r=Range[s=-Tr@Abs@#,-s],#~FromDigits~r,0]&

Stając się niechlujniejszy z ograniczeniami, możemy zmniejszyć te 5 dodatkowych bajtów na @Nie sugeruje drzewa:

Pick[r=Range[s=-#.#,-s],#~FromDigits~r,0]&

Po opublikowaniu tego, OP skomentował dopuszczenie „natywnych wielomianów”, więc oto 25 bajtowe rozwiązanie, które akceptuje wielomian jako dane wejściowe. Działa to, ponieważ domyślnie Mathematica rozkłada wielomiany na liczby całkowite, a wszelkie racjonalne pierwiastki pojawiają się w takiej formie, m*x+bże nie pasuje do wzorca.

Cases[Factor@#,b_+x:>-b]&

Jak wskazał @alephalpha, nie powiedzie się to w przypadku, gdy zero jest pierwiastkiem, więc aby naprawić, możemy użyć Optionalsymbolu:

Cases[Factor@#,b_:0+x:>-b]&

To analizuje dobrze Mathematica 11.0.1, ale kończy się niepowodzeniem i wymaga dodatkowego zestawu nawiasów b_:0w wersji 11.2. Zajmuje to do 27 bajtów plus dwa kolejne po wersji 11.0.1. Wygląda na to, że wprowadzono tutaj „poprawkę”

Wypróbuj online!

Kelly Lowder
źródło
1
Myślę, że możesz użyć #.#zamiast Tr@Abs@#: to gorsze ograniczenie, ale mniej bajtów.
Nie drzewo,
1
OP stwierdził w komentarzu, że możesz użyć rodzimego typu wielomianu swojego języka, jeśli taki istnieje. Nie znam dobrze Mathematiki, ale wyobrażam sobie, że istnieje ... Czy to by oszczędzało bajty?
Nie, nie pokazałem mojego prawdziwego imienia
1
@alephalpha, naprawiono.
Kelly Lowder
3

Wolfram Language (Mathematica) , 33 26 31 bajtów

Naprawiono błąd zauważony przez Kelly Lowder w komentarzach.

x/.{}⋃Solve[#==0,x,Integers]&

Wypróbuj online!

Poprzednie nieprawidłowe rozwiązania:

Właśnie zauważyłem, że w przypadku braku rozwiązania liczb całkowitych wyjście jest niezdefiniowane zamiast pustej listy; który pozwala usunąć kilka bajtów.

x/.Solve[#==0,x,Integers]&

Wypróbuj online!

Teraz, jeśli nie istnieje rozwiązanie liczb całkowitych, funkcja powraca x.

Poprzednio:

x/.Solve[#==0,x,Integers]/.x->{}&

Wypróbuj online!

celtschk
źródło
Nie udaje się to, jak obecnie stwierdzono w przypadku 1,2,1, ponieważ powtarza korzeń, a PO stwierdził, że muszą być wyraźne. Musisz Unionto naprawić.
Kelly Lowder
@ KellyLowder: Ach, tęskniłem za tym. Ale potem brakowało go również w danych przypadkach testowych.
celtschk
@KellyLowder: Naprawiłem to. Jeśli z tego powodu zostałeś odrzucony, czy możesz to cofnąć?
celtschk
@Cellschk, tak gotowe.
Kelly Lowder
29 bajtów przy użyciu nieudokumentowanej funkcji Solve: listy zmiennych można pominąć.
Rzym
3

R , 61 59 bajtów

Specjalne podziękowania dla @mathmandan za wskazanie mojego (niewłaściwego) podejścia można zapisać i zagrać w golfa!

function(p)(x=-(t=p[!!p][1]):t)[!outer(x,seq(p)-1,"^")%*%p]

Wypróbuj online!

Pobiera dane wejściowe jako listę współczynników w porządku rosnącym , tj . c(-1,0,1)Reprezentuje -1+0x+1x^2.

Korzystając z racjonalnego twierdzenia o korzeniu, następujące podejście działa bardzo prawie dla 47 bajtów:

function(p)(x=-p:p)[!outer(x,seq(p)-1,"^")%*%p]

Wypróbuj online!

-p:pgeneruje szereg symetryczny (z ostrzeżeniem) tylko za pomocą pierwszego elementu p, a_0. Zgodnie z racjonalnym twierdzeniem o korzeniu wszystkie racjonalne pierwiastki Pmuszą mieć postać, w p/qktórej pdzieli się a_0i qdzieli a_n(plus lub minus). Stąd, przy użyciu tylko a_0jest wystarczająca do |a_0|>0, jak dla każdego q, |p/q|<=a_0. Jednak gdy a_0==0, jak wtedy, jakakolwiek liczba całkowita dzieli się 0, a więc to się nie udaje.

Jednak matematyk wskazuje, że tak naprawdę w tym przypadku oznacza to, że istnieje stały czynnik, x^kktóry można uwzględnić, i zakładając, że kjest maksymalny, widzimy, że

P(x) = x^k(a_k + a_{k+1}x + ... a_n x^{n-k}) = x^k * Q(x)

Następnie stosujemy Racjonalne Twierdzenie o Korzeniu Q(x), i jak a_kgwarantuje to niezerowość przez maksimum k, a_kzapewnia uporządkowane ograniczenie pierwiastków całkowitych Q, a pierwiastki Psą pierwiastkami Qwraz z zerą, więc będziemy mieli całą liczbę całkowitą korzenie Ppoprzez zastosowanie tej metody.

Jest to równoważne znalezieniu pierwszego niezerowego współczynnika wielomianu t=p[!!p][1]i użyciu go zamiast naiwnego p[1]jako granic. Co więcej, ponieważ zakres -t:tzawsze zawiera zero, zastosowanie Pdo tego zakresu nadal dałoby nam zero jako pierwiastek, jeśli w rzeczywistości tak jest.

bez golfa:

function(polynom) {
 bound <- polynom[polynom != 0][1]             #first nonzero value of polynom
 range <- -bound:bound                         #generates [-bound, ..., bound]
 powers <- outer(range,seq_along(p) - 1, "^")  #matrix where each row is [n^0,n^1,n^2,...,n^deg(p)]
 polyVals <- powers %*% polynom                #value of the polynomial @ each point in range
 return(range[polyVals == 0])                  #filter for zeros and return
}

Giuseppe
źródło
(Myślę, że możesz użyć maxwartości bezwzględnych zamiast sum; nie zmieniłoby to liczby bajtów, ale powinno poprawić wydajność.) W każdym razie tak, szkoda, że ​​krótsza wersja nie działa a_0==0. Czy w R jest jakaś krótka droga do znalezienia pierwszego (z rosnącymi mocami) niezerowego współczynnika i zastosowania go zamiast tego? Odpowiadałoby to najpierw uwzględnieniu jak największej liczby x (oczywiście wtedy trzeba pamiętać, aby 0również generować , co prawdopodobnie kosztowałoby kilka bajtów)
mathmandan
@mathmandan maxbyłby bardziej wydajny, ale do twojego drugiego punktu, ponieważ nie muszę się martwić o wynik, 0ponieważ jest generowany przez zakres -t:t(gdzie tjest pierwszy niezerowy współczynnik), oszczędza 2 bajty!
Giuseppe
Och, bardzo miło! (A także piękne wyjaśnienie.)
matematyk
2

Galaretka , 8 bajtów

ASŒRḅ@Ðḟ

Wypróbuj online! lub jako zestaw testowy!

W jaki sposób?

ASŒRḅ @ Ðḟ || Pełny program (łącze monadyczne).

AS || Zsumuj wartości bezwzględne.
  ŒR || I utwórz symetryczny zakres włączający na podstawie jego wartości ujemnej.
       Ðḟ || I odrzuć te, które dają prawdziwą wartość ...
     ḅ @ || Podczas podłączania ich do wielomianu (wykorzystuje konwersję podstawową).

Na podstawie odpowiedzi Luisa . Alternatywą .

Pan Xcoder
źródło
Czy jest coś, czego mi brakuje w przyjmowaniu (dozwolonej) odwrotnej kolejności i robieniu Ær+.Ḟ?
Jonathan Allan
Jestem trochę zdezorientowany, ponieważ odpowiedź Pythona z numpy też tego nie robi i myślę, że przegapiłem jakiś przypadek.
Jonathan Allan
@JonathanAllan Tak jak się spodziewałem, twoje się nie udaje [1,2,3].
Pan Xcoder
„Jeśli nie ma rozwiązania dla danego równania, wynik jest niezdefiniowany”
Jonathan Allan
@JonathanAllan Ale to nie uda za [10,-42,8], prawda?
Pan Xcoder
2

Oktawa , 59 49 bajtów

@(p)(x=-(t=p(~~p)(end)):sign(t):t)(!polyval(p,x))

Wypróbuj online!

Jest to port z moim R odpowiedź . Jedyną różnicą jest to, że muszę jawnie użyć sign(t)i endwygenerować zakres oraz że musi polyvalon obliczyć wielomian.

Pobiera dane wejściowe jako wektor rzędu współczynników w malejącej kolejności.

Giuseppe
źródło
2

Pari / GP , 31 bajtów

p->[x-a|a<-factor(p)[,1],a'==1]

Uwzględnia wielomian i wybiera czynniki, których pochodnymi są 1.

Wypróbuj online!

alephalpha
źródło
2

C (gcc) , 127 126 123 bajtów

x,X,j,m,p;f(A,l)int*A;{for(m=j=0;j<l;m+=abs(A[j++]));for(x=~m;X=x++<m;p||printf("%d,",x))for(p=j=0;j<l;X*=x)p+=A[l-++j]*X;}

Wypróbuj online!


Wyjaśnienie

C (gcc) , 517 bajtów

x,X,j,m,p;                      // global integer variables
f(A,l)int*A;{                   // define function, takes in integer array pointer and length
 for(m=j=0;j<l;m+=abs(A[j++])); // loop through array, sum up absolute values
  for(x=~m;X=x++<m;             // loop through all values x in [-m, m], prime X
   p||printf("%d,",x))          // at loop's end, print x value if polynomial value is zero
    for(p=j=0;j<l;X*=x)         // loop through coefficients
     p+=A[l-++j]*X;}            // build polynomial

Wypróbuj online!

Jonathan Frech
źródło
l+~j++można l-++j
grać w
@KevinCruijssen Bardzo dziękuję.
Jonathan Frech
@ceilingcat Dziękuję.
Jonathan Frech,
1

Java 8, 141 140 bajtów

a->{int l=a.length,s=0,i,r,f,p;for(int n:a)s+=n<0?-n:n;for(r=~s;r++<s;System.out.print(p==0?r+",":""))for(p=i=0,f=1;i<l;f*=r)p+=a[l-++i]*f;}

Zainspirowany odpowiedzią @Rod na Python 2 (jego 82 bajtowa wersja) .

Zabawne wyzwanie! Na pewno wiele się nauczyłem, badając wielomiany i widząc, jak zrobili to inni tutaj.

Wyjaśnienie:

Wypróbuj online.

a->{                   // Method with integer-array parameter and no return-type
  int l=a.length,      //  The length of the input-array
      s=0,             //  Sum-integer, starting at 0
      i,               //  Index integer
      r,               //  Range-integer
      f,               //  Factor-integer
      p;               //  Polynomial-integer
  for(int n:a)         //  Loop over the input-array
    s+=n<0?-n:n;       //   And sum their absolute values
  for(r=~s;r++<s;      //  Loop `r` from `-s` up to `s` (inclusive) (where `s` is the sum)
      System.out.print(p==0?r+",":""))
                       //    After every iteration: print the current `r` if `p` is 0
    for(p=i=0,         //   Reset `p` to 0
        f=1;           //   and `f` to 1
        i<l;           //   Loop over the input-array again, this time with index (`i`)
        f*=r)          //     After every iteration: multiply `f` with the current `r`
      p+=              //    Sum the Polynomial-integer `p` with:
         a[l-++i]      //     The value of the input at index `l-i-1`,
                 *f;}  //     multiplied with the current factor `f`
Kevin Cruijssen
źródło
0

JavaScript (ES6), 97 bajtów

a=>[...Array((n=Math.max(...a.map(Math.abs)))-~n)].map(_=>n--).filter(i=>!a.reduce((x,y)=>x*i+y))

Przyjmuje współczynniki w malejącej kolejności mocy, a wyniki w kolejności malejącej.

Neil
źródło
0

Czysty , 110 91 bajtów

import StdEnv
?p#s=sum p
=[i\\i<-[~s..s]|i<>0&&sum[e*i^t\\t<-reverse(indexList p)&e<-p]==0]

Wypróbuj online!

Obrzydliwe
źródło