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 golf golfowy , więc wygrywa najkrótszy kod (w bajtach)!
Odpowiedzi:
MATL ,
1312 bajtówWypró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.źródło
X>t_w&:GyZQ~)
, ale wciąż 13 bajtówŁuska ,
109 bajtów-1 bajt dzięki Zgarb
Wypróbuj online!
Wyjaśnienie
źródło
ṁṡ
zamiast,oṡ►a
jeśli później deduplikujesz.Haskell , 54 bajty
Wypróbuj online!
Brutalna siła i podział syntetyczny.
Niegolfowany z UniHaskell i
-XUnicodeSyntax
Alternatywne rozwiązanie, 44 bajty
Podziękowania dla nich.
Życzymy powodzenia w wypróbowywaniu go online , ponieważ sprawdza on każdą liczbę w
Int
zakresie.źródło
i
nad[minBound..]
i upuść całąt
rzecz. Połączeniaf
z wyraźnymiInt
listami, npf [1::Int,5,6]
. Oczywiście nie kończy się to w rozsądnym czasie.Bounded
typy zatrzymują sięmaxBound
npprint [minBound::Bool ..]
.Python 2 + numpy,
959391103939182 bajtów-2 bajty dzięki ovs
dzięki Luis Mendo za górne / dolne granice korzeni
-10 bajtów dzięki Mr. Xcoder
Wypróbuj online!
źródło
numpy.polyval
oszczędza sporo bajtówWolfram Language (Mathematica) ,
5047422527 bajtówWypróbuj online!
Aktualizacja: korzystając z faktu Luisa Mendo, grał w golfa o kolejne 3 bajty
Stając się niechlujniejszy z ograniczeniami, możemy zmniejszyć te 5 dodatkowych bajtów na @Nie sugeruje drzewa:
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.Jak wskazał @alephalpha, nie powiedzie się to w przypadku, gdy zero jest pierwiastkiem, więc aby naprawić, możemy użyć
Optional
symbolu:
To analizuje dobrze Mathematica 11.0.1, ale kończy się niepowodzeniem i wymaga dodatkowego zestawu nawiasów
b_:0
w 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!
źródło
#.#
zamiastTr@Abs@#
: to gorsze ograniczenie, ale mniej bajtów.Wolfram Language (Mathematica) ,
332631 bajtówNaprawiono błąd zauważony przez Kelly Lowder w komentarzach.
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.
Wypróbuj online!
Teraz, jeśli nie istnieje rozwiązanie liczb całkowitych, funkcja powraca
x
.Poprzednio:
Wypróbuj online!
źródło
Union
to naprawić.Solve
: listy zmiennych można pominąć.R ,
6159 bajtówSpecjalne podziękowania dla @mathmandan za wskazanie mojego (niewłaściwego) podejścia można zapisać i zagrać w golfa!
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:
Wypróbuj online!
-p:p
generuje szereg symetryczny (z ostrzeżeniem) tylko za pomocą pierwszego elementup
,a_0
. Zgodnie z racjonalnym twierdzeniem o korzeniu wszystkie racjonalne pierwiastkiP
muszą mieć postać, wp/q
którejp
dzieli sięa_0
iq
dzielia_n
(plus lub minus). Stąd, przy użyciu tylkoa_0
jest wystarczająca do|a_0|>0
, jak dla każdegoq
,|p/q|<=a_0
. Jednak gdya_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^k
który można uwzględnić, i zakładając, żek
jest maksymalny, widzimy, żeNastępnie stosujemy Racjonalne Twierdzenie o Korzeniu
Q(x)
, i jaka_k
gwarantuje to niezerowość przez maksimumk
,a_k
zapewnia uporządkowane ograniczenie pierwiastków całkowitychQ
, a pierwiastkiP
są pierwiastkamiQ
wraz z zerą, więc będziemy mieli całą liczbę całkowitą korzenieP
poprzez zastosowanie tej metody.Jest to równoważne znalezieniu pierwszego niezerowego współczynnika wielomianu
t=p[!!p][1]
i użyciu go zamiast naiwnegop[1]
jako granic. Co więcej, ponieważ zakres-t:t
zawsze zawiera zero, zastosowanieP
do tego zakresu nadal dałoby nam zero jako pierwiastek, jeśli w rzeczywistości tak jest.bez golfa:
źródło
max
wartości bezwzględnych zamiastsum
; nie zmieniłoby to liczby bajtów, ale powinno poprawić wydajność.) W każdym razie tak, szkoda, że krótsza wersja nie działaa_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ć, aby0
również generować , co prawdopodobnie kosztowałoby kilka bajtów)max
byłby bardziej wydajny, ale do twojego drugiego punktu, ponieważ nie muszę się martwić o wynik,0
ponieważ jest generowany przez zakres-t:t
(gdziet
jest pierwszy niezerowy współczynnik), oszczędza 2 bajty!Galaretka , 8 bajtów
Wypróbuj online! lub jako zestaw testowy!
W jaki sposób?
Na podstawie odpowiedzi Luisa . Alternatywą .
źródło
Ær+.Ḟ
?[1,2,3]
.[10,-42,8]
, prawda?Oktawa ,
5949 bajtówWypróbuj online!
Jest to port z moim R odpowiedź . Jedyną różnicą jest to, że muszę jawnie użyć
sign(t)
iend
wygenerować zakres oraz że musipolyval
on obliczyć wielomian.Pobiera dane wejściowe jako wektor rzędu współczynników w malejącej kolejności.
źródło
Pari / GP , 31 bajtów
Uwzględnia wielomian i wybiera czynniki, których pochodnymi są 1.
Wypróbuj online!
źródło
C (gcc) ,
127126123 bajtówl+~j++
w golfal-++j
.Wypróbuj online!
Wyjaśnienie
C (gcc) , 517 bajtów
Wypróbuj online!
źródło
l+~j++
możnal-++j
Java 8,
141140 bajtówZainspirowany 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.
źródło
Oktawa z pakietem symbolicznym, 63 bajty
Wypróbuj online!
źródło
05AB1E , 8 bajtów
Wypróbuj online!
źródło
JavaScript (ES6), 97 bajtów
Przyjmuje współczynniki w malejącej kolejności mocy, a wyniki w kolejności malejącej.
źródło
Czysty ,
11091 bajtówWypróbuj online!
źródło
Python 2 , 89 bajtów
Wypróbuj online!
źródło