Temukan Akar Integral Polinomial A

19

Tantangan

Tantangannya adalah untuk menulis sebuah program yang mengambil koefisien dari setiap persamaan polinomial n-derajat sebagai input dan mengembalikan nilai integral x yang menjadi dasar persamaan tersebut. Koefisien akan diberikan sebagai input dalam urutan penurunan atau peningkatan daya. Anda dapat menganggap semua koefisien sebagai bilangan bulat .

Masukan dan keluaran

Input akan menjadi koefisien persamaan dalam mengurangi atau meningkatkan urutan daya. Tingkat persamaan, yaitu, daya maksimum x, selalu 1 kurang dari jumlah total elemen dalam input.

Sebagai contoh: 

[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)

Output Anda harus hanya nilai integral x yang memenuhi persamaan yang diberikan. Semua koefisien input adalah bilangan bulat dan polinomial input tidak akan menjadi nol polinomial . Jika tidak ada solusi untuk persamaan yang diberikan, maka outputnya tidak ditentukan.

Jika sebuah persamaan memiliki akar berulang, tampilkan akar tertentu hanya sekali. Anda dapat menampilkan nilai dalam urutan apa pun. Juga, asumsikan bahwa input akan mengandung setidaknya 2 angka.

Contohnya

[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] -> -

Perhatikan bahwa persamaan dalam contoh kedua juga memiliki root 0,2, tetapi tidak ditampilkan karena 0,2 bukan bilangan bulat.

Mencetak gol

Ini adalah kode-golf , jadi kode terpendek (dalam byte) menang!

code-golf number integer polynomials equation Manish Kundu
sumber
7
Catatan: Sebelum pemungutan suara untuk ditutup, harap pertimbangkan bahwa pertanyaan ini bukan merupakan duplikat dari pertanyaan ini . Saya dapat memikirkan setidaknya satu pendekatan untuk masalah ini yang tidak dapat dimodifikasi secara sepele untuk tantangan lainnya (walaupun saya tidak mengatakan apa; itu diserahkan kepada Anda; P).
Erik the Outgolfer
Bisakah kita menganggap kita hanya perlu mengembalikan akar di dalam batas bilangan bulat bahasa kita? Atau seandainya algoritme berfungsi bahkan jika rentang jenis bilangan bahasa ditingkatkan, tetapi perilaku tetap sama.
Surous
1
Bisakah kita juga menggunakan tipe polinom asli jika bahasa Anda mendukungnya?
flawr
1
Apakah program yang berjalan selamanya jika tidak ada solusi yang diterima?
Jack M
1
Itu untuk menjaga hal-hal sederhana.
Manish Kundu

Jawaban:

6

MATL , 13 12 byte

|stE:-GyZQ~)

Cobalah online!

Ini menggunakan fakta bahwa, untuk koefisien bilangan bulat, nilai absolut dari akar apa pun benar-benar kurang dari jumlah nilai absolut dari koefisien.

Penjelasan

Pertimbangkan input [1 5 6]sebagai contoh.

|    % 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
sumber
3
Sebagai alternatif dari Teorema Rouche, Teorema Rasional Akar juga cukup untuk membenarkan ikatan yang Anda gunakan. Dengan Teorema Akar Rasional, semua akar bilangan bulat dibatasi dalam nilai absolut dengan maksimum nilai absolut dari koefisien, ikatan yang lebih ketat dari jumlah. Atau bahkan lebih ketat, dengan nilai absolut dari koefisien bukan nol "terakhir" - yaitu koefisien kekuatan x terkecil yang memiliki koefisien bukan nol. (Mungkin tidak membantu menyelamatkan byte, hanya bukti alternatif karena RRT mungkin lebih akrab daripada Rouche bagi kebanyakan orang.) :)
mathmandan
1
@mathmandan pendekatan itu tiga byte lebih lama: Cobalah di sini , meskipun saya yakin saya telah melewatkan satu atau dua trik
Giuseppe
@Giuseppe Terima kasih untuk keduanya. Mungkin X>t_w&:GyZQ~), tapi masih 13 byte
Luis Mendo
1
... tapi saya menemukan alternatif yang lebih pendek untuk jangkauan
Luis Mendo
5

Sekam , 10 9 byte

-1 byte terima kasih kepada Zgarb

uSȯf¬`Bṁṡ

Cobalah online!

Penjelasan

       ṁṡ   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.Piz
sumber
Anda bisa melakukannya ṁṡdaripada oṡ►amenduplikat nanti.
Zgarb
@Zgarb Sangat bagus! Terima kasih
H.PWiz
5

Haskell , 54 byte

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

Cobalah online!

Divisi kasar dan sintetis.

Tidak tergabung dengan UniHaskell dan-XUnicodeSyntax

import UniHaskell

roots    ∷ Num a ⇒ [a] → [a]
roots xs = [r | r ← -bound … bound, foldl1 ((+) ∘ (r ×)) xs ≡ 0]
             where bound = sum $ abs § xs

Solusi alternatif, 44 byte

Penghargaan untuk nimi.

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

Selamat mencoba dengan online , karena ini memeriksa setiap nomor dalam Intrentang.

benar-benar manusiawi
sumber
Anda dapat iterate iatas [minBound..]dan drop seluruh thal. Panggil fdengan Intdaftar eksplisit , mis f [1::Int,5,6]. Tentu saja ini tidak selesai dalam waktu yang wajar.
nimi
@nimi Mengapa itu berhenti? Bukankah itu akan berulang?
Sepenuhnya manusiawi
Tidak, Boundedtipe berhenti di maxBound, mis print [minBound::Bool ..].
nimi
4

Python 2 + numpy, 95 93 91 103 93 91 82 byte

-2 byte terima kasih kepada Ov
terima kasih Luis Mendo untuk batas atas / bawah dari akar
-10 byte terima kasih kepada Tn. Xcoder

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

Cobalah online!

tongkat
sumber
91 byte
ovs
@LuisMendo ya.
Rod
3
Konsensus kami saat ini tampaknya bahwa program harus selalu berakhir, kecuali tantangannya menyatakan sebaliknya.
Zgarb
@ Zgarb di sana, diperbaiki!
Rod
Menggunakan numpy.polyvalmenghemat beberapa byte
Tn. Xcoder
4

Bahasa Wolfram (Mathematica) , 50 47 42 25 27 byte

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

Cobalah online!

Pembaruan: menggunakan fakta Luis Mendo, bermain golf 3 byte lagi

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

Menjadi lebih sembrono dengan batasan, kita dapat mengurangi 5 byte ini lebih per @tidak saran pohon:

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

Setelah memposting ini, OP berkomentar memungkinkan "polinomial asli", jadi inilah solusi 25 byte yang menerima polinomial sebagai input. Ini berfungsi karena secara default Mathematica faktor polinomial atas bilangan bulat, dan setiap akar rasional muncul dalam bentuk seperti m*x+byang gagal cocok dengan pola.

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

Seperti @alephalpha tunjukkan ini akan gagal untuk kasus di mana nol adalah root, jadi untuk memperbaikinya kita bisa menggunakan Optionalsimbol:

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

Ini mem-parsing baik-baik saja Mathematica 11.0.1 tetapi gagal dan membutuhkan set kurung tambahan sekitar b_:0dalam versi 11.2. Ini membutuhkan waktu hingga 27 byte, ditambah dua lagi setelah versi 11.0.1. Sepertinya "perbaikan" dimasukkan ke sini

Cobalah secara Online!

Kelly Lowder
sumber
1
Saya pikir Anda bisa menggunakan #.#bukan Tr@Abs@#: itu adalah batas yang lebih buruk tetapi lebih sedikit byte.
Bukan pohon
1
OP mengatakan dalam komentar bahwa Anda dapat menggunakan jenis polinomial asli bahasa Anda jika ada. Saya tidak tahu Mathematica dengan baik, tetapi saya membayangkan ada satu ... Apakah itu menghemat byte?
Tidak, jangan tampilkan nama asli saya
1
Gagal ketika 0 adalah root.
alephalpha
1
@alephalpha, diperbaiki.
Kelly Lowder
24 byte dengan pola Default dan komposisi kanan operator
Roman
3

Bahasa Wolfram (Mathematica) , 33 26 31 byte

Memperbaiki kesalahan yang dicatat oleh Kelly Lowder di komentar.

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

Cobalah online!

Solusi yang salah sebelumnya:

Saya hanya memperhatikan bahwa tanpa solusi integer, output tidak terdefinisi daripada daftar kosong; yang memungkinkan untuk menghapus beberapa byte.

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

Cobalah online!

Sekarang jika tidak ada solusi integer, fungsi kembali x.

Sebelumnya:

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

Cobalah online!

celtschk
sumber
Ini gagal seperti yang dinyatakan saat ini dengan 1,2,1 karena mengulangi root dan OP mengatakan mereka harus berbeda. Anda harus Unionmemperbaikinya.
Kelly Lowder
@KellyLowder: Ah, saya melewatkan itu. Tapi kemudian, itu juga hilang dalam kasus uji yang diberikan.
celtschk
@KellyLowder: Sekarang saya sudah memperbaikinya. Jika Anda downvoted karena ini, dapatkah Anda mengembalikannya?
celtschk
@selschk, ya sudah selesai.
Kelly Lowder
29 byte dengan menggunakan fitur tidak berdokumen dari Solve: daftar variabel dapat dihilangkan.
Roman
3

R , 61 59 byte

Terima kasih khusus kepada @mathmandan karena menunjukkan pendekatan saya (yang salah) dapat diselamatkan, dan bermain golf !

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

Cobalah online!

Mengambil input sebagai daftar koefisien dalam urutan meningkat , yaitu, c(-1,0,1)mewakili -1+0x+1x^2.

Menggunakan teorema root rasional, pendekatan berikut ini hampir berhasil, untuk 47 byte:

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

Cobalah online!

-p:pmenghasilkan berbagai simetris (dengan peringatan) hanya menggunakan elemen pertama dari p, a_0. Dengan Teorema Akar Rasional , semua akar rasional Pharus dari bentuk di p/qmana pmembagi a_0dan qmembagi a_n(plus atau minus). Oleh karena itu, dengan hanya menggunakan a_0cukup untuk |a_0|>0, seperti untuk q, |p/q|<=a_0. Namun, ketika a_0==0, saat itu pun bilangan bulat terbagi 0, dan dengan demikian ini gagal.

Namun, mathmandan menunjukkan bahwa sebenarnya, dalam hal ini, ini berarti bahwa ada faktor konstan x^kyang dapat diperhitungkan, dan, dengan asumsi kmaksimal, kita melihat bahwa

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

Kami kemudian menerapkan Teorema Rasional Akar untuk Q(x), dan seperti a_kyang dijamin bukan nol dengan maksimalnya k, a_kmemberikan ikatan rapi untuk akar bilangan bulat Q, dan akar Padalah akar Qbersama dengan nol, jadi kami akan memiliki semua bilangan bulat akar Pdengan menerapkan metode ini.

Ini sama dengan menemukan koefisien bukan nol pertama dari polinomial, t=p[!!p][1]dan menggunakannya sebagai pengganti naif p[1]sebagai batas. Selain itu, karena rentang -t:tselalu berisi nol, menerapkan Pke rentang ini akan tetap memberi kita nol sebagai root, jika memang itu.

ungolfed:

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
sumber
(Saya pikir Anda bisa menggunakan maxnilai absolut alih-alih sum; ini tidak akan mengubah jumlah byte, tetapi seharusnya meningkatkan kinerja.) Bagaimanapun, ya, kasihan versi yang lebih pendek tidak bekerja dengan baik a_0==0. Apakah ada cara singkat dalam R untuk mencari koefisien bukan nol pertama (dengan kekuatan naik), dan menggunakannya sebagai gantinya? Ini akan sesuai dengan anjak sebanyak mungkin x pertama (tentu saja, maka Anda harus ingat untuk output 0juga, yang mungkin akan menelan biaya beberapa byte.)
mathmandan
@mathmandan maxakan lebih efisien, tetapi untuk poin kedua Anda, karena saya tidak perlu khawatir tentang keluaran 0karena dihasilkan oleh kisaran -t:t(di mana tadalah koefisien bukan nol pertama), menghemat 2 byte!
Giuseppe
Oh bagus sekali! (Dan penjelasan yang indah juga.)
mathmandan
2

Jelly , 8 byte

ASŒRḅ@Ðḟ

Cobalah online! atau sebagai test-suite!

Bagaimana?

ASŒRḅ @ Ðḟ || Program lengkap (tautan monadik).

AS || Jumlahkan nilai absolut.
  ŒR || Dan buat rentang inklusif simetris dari nilai negatifnya.
       Ðḟ || Dan buang yang menghasilkan nilai kebenaran ...
     ḅ @ || Saat menghubungkan mereka ke polinomial (menggunakan konversi basis).

Didasarkan atas jawaban Luis . Alternatif .

Tuan Xcoder
sumber
Apakah ada sesuatu yang saya lewatkan tentang mengambil urutan terbalik dan melakukan Ær+.Ḟ?
Jonathan Allan
Saya sedikit bingung karena jawaban Python dengan numpy juga tidak, dan saya pikir saya telah melewatkan beberapa kasus tepi.
Jonathan Allan
@ JonathanAllan Seperti yang saya harapkan, milik Anda gagal [1,2,3].
Tuan Xcoder
"Jika tidak ada solusi untuk persamaan yang diberikan, maka hasilnya tidak ditentukan"
Jonathan Allan
@JonathanAllan Tapi itu tidak gagal untuk [10,-42,8], kan?
Tn. Xcoder
2

Oktaf , 59 49 byte

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

Cobalah online!

Ini adalah port jawaban R saya . Satu-satunya perbedaan adalah bahwa saya harus secara eksplisit menggunakan sign(t)dan endmenghasilkan kisaran, dan polyvalharus menghitung polinomial.

Mengambil input sebagai vektor baris koefisien dalam urutan menurun.

Giuseppe
sumber
2

Pari / GP , 31 byte

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

Faktor polinomial, dan pilih faktor-faktor yang turunannya adalah 1.

Cobalah online!

alephalpha
sumber
2

C (gcc) , 127 126 123 byte

  • Disimpan satu byte berkat Kevin Cruijssen ; bermain golf l+~j++untuk l-++j.
  • Terima kasih kepada ceilingcat untuk menghemat tiga byte.
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;}

Cobalah online!

Penjelasan

C (gcc) , 517 byte

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

Cobalah online!

Jonathan Frech
sumber
l+~j++dapat l-++j
bermain golf
@KevinCruijssen Terima kasih banyak.
Jonathan Frech
@ceilingcat Terima kasih.
Jonathan Frech
1

Java 8, 141 140 byte

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;}

Terinspirasi oleh @Rod 's Python 2 answer (versi 82 ​​byte-nya) .

Tantangan yang menyenangkan! Saya tentu belajar banyak dari itu ketika menyelidiki tentang polinomial dan melihat bagaimana beberapa orang lain di sini melakukannya.

Penjelasan:

Cobalah 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
sumber
0

Oktaf dengan Paket Simbolik, 63 byte

@(p)(s=double(solve(poly2sym(p)==0)))(s==(t=real(s))&~mod(t,1))

Cobalah online!

Luis Mendo
sumber
0

JavaScript (ES6), 97 byte

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

Mengambil koefisien dalam mengurangi urutan daya dan output menghasilkan urutan menurun.

Neil
sumber
0

Bersih , 110 91 byte

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

Cobalah online!

Suram
sumber
0

Python 2 , 89 byte

def f(a):s=sum(map(abs,a));return[n for n in range(-s,s)if reduce(lambda v,c:v*n+c,a)==0]

Cobalah online!

Chas Brown
sumber