Найти интегральные корни многочлена

19

Вызов

Задача состоит в том, чтобы написать программу, которая принимает коэффициенты любого полиномиального уравнения n-степени в качестве входных данных и возвращает интегральные значения x, для которых выполняется уравнение. Коэффициенты будут предоставлены в качестве входных данных в порядке убывания или увеличения мощности. Вы можете считать все коэффициенты целыми числами .

Вход и выход

Входными данными будут коэффициенты уравнения в порядке убывания или увеличения мощности. Степень уравнения, т. Е. Максимальная мощность x, всегда на 1 меньше, чем общее количество элементов на входе.

Например:

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

Ваши выходные данные должны быть только различными целочисленными значениями x, которые удовлетворяют данному уравнению. Все входные коэффициенты являются целыми числами, и входной многочлен не будет нулевым многочленом . Если для данного уравнения нет решения, то результат не определен.

Если уравнение имеет повторяющиеся корни, отобразите этот конкретный корень только один раз. Вы можете вывести значения в любом порядке. Также предположим, что ввод будет содержать как минимум 2 числа.

Примеры

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

Обратите внимание, что уравнение во втором примере также имеет корень 0,2, но он не отображается, поскольку 0,2 не является целым числом.

счет

Это , поэтому выигрывает самый короткий код (в байтах)!

Маниш Кунду
источник
7
Примечание: Перед голосованием к концу, пожалуйста , считают , что этот вопрос не является дубликатом этого одного . Я могу вспомнить хотя бы один подход к этой проблеме, который не будет тривиально изменяемым для другой задачи (хотя я не говорю, что; это остается вам; P).
Эрик Outgolfer
Можем ли мы предположить, что нам нужно только возвращать корни внутри целочисленных границ нашего языка? Или алгоритм должен работать, даже если диапазон целочисленных типов языков был увеличен, но поведение осталось прежним.
августа
1
Можем ли мы также использовать собственный полиномиальный тип, если ваш язык поддерживает их?
flawr
1
Программы, которые работают вечно, если нет решений, принятых?
Джек М
1
Это для простоты.
Маниш Кунду

Ответы:

6

MATL , 13 12 байт

|stE:-GyZQ~)

Попробуйте онлайн!

При этом используется тот факт, что для целочисленных коэффициентов абсолютное значение любого корня строго меньше суммы абсолютных значений коэффициентов.

объяснение

Рассмотрим ввод [1 5 6]в качестве примера.

|    % 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]
Луис Мендо
источник
3
В качестве альтернативы теореме Роше для обоснования использованной вами оценки также будет достаточно теоремы о рациональных корнях. По теореме Рационального Корня все целочисленные корни ограничены по абсолютной величине максимумом абсолютных значений коэффициентов, более жесткой границей, чем сумма. Или даже еще сильнее, по абсолютной величине «последнего» ненулевого коэффициента, то есть коэффициента наименьшей степени x, который имеет ненулевой коэффициент. (Вероятно, это не поможет сохранить байты, просто альтернативное доказательство, поскольку RRT, вероятно, более знаком, чем Рош, большинству людей.) :)
mathmandan
1
@mathmandan этот подход на три байта длиннее: попробуйте здесь , хотя я уверен, что пропустил один или два трюка
Джузеппе
@Giuseppe Благодаря обоим. Возможно X>t_w&:GyZQ~), но все же 13 байт
Луис Мендо
1
... но я нашел более короткую альтернативу для диапазона
Луис Мендо
5

Шелуха , 10 9 байт

-1 байт благодаря Zgarb

uSȯf¬`Bṁṡ

Попробуйте онлайн!

объяснение

       ṁṡ   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
источник
Вы можете сделать ṁṡвместо, oṡ►aесли вы дедуплицируете позже.
Згарб
@ Zgarb Очень мило! Спасибо
H.PWiz
5

Haskell , 54 байта

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

Попробуйте онлайн!

Грубая сила и синтетическое разделение.

Разрушенный с UniHaskell и-XUnicodeSyntax

import UniHaskell

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

Альтернативный раствор, 44 байта

Благодарю Ними.

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

Удачи в онлайн-тестировании , так как он проверяет все числа в Intдиапазоне.

totallyhuman
источник
Вы можете перемещаться iнад [minBound..]и уронить всю tвещь. Звоните fс явными Intсписками, например f [1::Int,5,6]. Конечно, это не заканчивается в разумные сроки.
Ними
@nimi Почему это когда-нибудь остановится? Не будет ли это бесконечно зацикливаться?
полностью человек
Нет, Boundedтипы останавливаются на maxBound, например print [minBound::Bool ..].
Ними
4

Python 2 + numpy, 95 93 91 103 93 91 82 байта

-2 байта благодаря ovs
спасибо Луису Мендо за верхнюю / нижнюю границы корней
-10 байтов благодаря Mr. Xcoder

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

Попробуйте онлайн!

прут
источник
@ LuisMendo да.
Род
3
Похоже, что наш текущий консенсус заключается в том, что программы должны всегда завершаться, если в запросе не указано иное.
Згарб
@ Zgarb там, исправлено!
Род
Использование numpy.polyvalэкономит немало байтов
Mr. Xcoder
4

Wolfram Language (Mathematica) , 50 47 42 25 27 байт

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

Попробуйте онлайн!

Обновление: с использованием факта Луиса Мендо, отыгравшего еще 3 байта

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

Получая небрежность с границами, мы можем уменьшить это еще на 5 байт на @ Не предложение дерева:

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

После публикации этого сообщения OP прокомментировал разрешение «нативных полиномов», так что вот 25-байтовое решение, которое принимает полином как входные данные. Это работает, потому что по умолчанию Mathematica делит полиномы на целые числа, и любые рациональные корни отображаются в такой форме, m*x+bчто не соответствует шаблону.

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

Как указал @alephalpha, это не удастся для случая, когда ноль является корнем, поэтому для исправления мы можем использовать Optionalсимвол:

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

Это прекрасно разбирает Mathematica 11.0.1, но не работает и требует дополнительного набора скобок b_:0в версии 11.2. Это занимает до 27 байтов, плюс еще два после версии 11.0.1. Похоже, что "исправить" был введен здесь

Попробуйте онлайн!

Келли Лоудер
источник
1
Я думаю, что вы можете использовать #.#вместо Tr@Abs@#: это хуже, но меньше байтов.
Не дерево
1
OP сказал в комментарии, что вы можете использовать родной полиномиальный тип вашего языка, если таковой существует. Я не знаю Mathematica хорошо, но я думаю, что есть один ... Это спасет байты?
Не показывалось мое настоящее имя
1
@alephalpha, исправлено.
Келли Лоудер
3

Wolfram Language (Mathematica) , 33 26 31 байт

Исправлена ​​ошибка, отмеченная Келли Лоудер в комментариях.

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

Попробуйте онлайн!

Предыдущие неверные решения:

Я только что заметил, что для целочисленного решения вывод не определен вместо пустого списка; что позволяет удалить несколько байтов.

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

Попробуйте онлайн!

Теперь, если целочисленного решения не существует, функция возвращает x.

Ранее:

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

Попробуйте онлайн!

celtschk
источник
Это терпит неудачу, как в настоящее время заявлено с 1,2,1, поскольку это повторяет корень, и OP сказал, что они должны быть отличны. Вы должны Unionэто исправить.
Келли Лоудер
@KellyLowder: Ах, я пропустил это. Но тогда это также отсутствовало в данных тестах.
celtschk
@KellyLowder: я сейчас исправил это. Если из-за этого вы проголосовали против, не могли бы вы отменить это?
celtschk
@cellschk, да сделано.
Келли Лоудер
29 байт , используя недокументированную особенностьSolve : список переменных может быть опущен.
Роман
3

R , 61 59 байт

Отдельное спасибо @mathmandan за то, что он указал на мой (неправильный) подход, можно сохранить и сыграть в гольф!

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

Попробуйте онлайн!

Принимает ввод как список коэффициентов в порядке возрастания , т.е. c(-1,0,1)представляет -1+0x+1x^2.

Используя рациональную корневую теорему, следующий подход почти работает, для 47 байтов:

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

Попробуйте онлайн!

-p:pгенерирует симметричный диапазон (с предупреждением) , используя только первый элемент p, a_0. По теореме о рациональном корне все рациональные корни Pдолжны иметь форму, в p/qкоторой pделится a_0и qделится a_n(плюс или минус). Следовательно, использование только a_0достаточно для|a_0|>0 , как и для любого q, |p/q|<=a_0. Однако когда a_0==0, как и тогда любое целое число делится 0, и, таким образом, это не удается.

Тем не менее, Матмандан указывает, что на самом деле, в этом случае, это означает, что есть постоянный фактор, x^kкоторый может быть учтен, и, предполагая kмаксимальный, мы видим, что

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

Затем мы применяем теорему Рационального Корня к Q(x), и, как a_kгарантируется, будет ненулевым по максимальностиk , a_kобеспечивает аккуратную оценку для целочисленных корней Q, а корни Pявляются корнями Qнаряду с нулем, поэтому мы будем иметь все целые корни Pпутем применения этого метода.

Это эквивалентно нахождению первого ненулевого коэффициента многочлена, t=p[!!p][1] и использованию его вместо наивного p[1]в качестве границ. Более того, поскольку диапазон -t:tвсегда содержит ноль, применение Pэтого диапазона все равно даст нам ноль в качестве корня, если это действительно так.

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
источник
(Я думаю, что вы могли бы использовать maxабсолютные значения вместо sum; это не изменило бы количество байтов, но это должно улучшить производительность.) В любом случае, да, жаль, что более короткая версия не работает a_0==0. Есть ли какой-то короткий путь в R для поиска первого (с возрастанием мощностей) ненулевого коэффициента и его использования вместо этого? Это будет соответствовать факторизации как можно большего числа x (сначала, конечно, вы должны будете также не забывать выводить данные 0, что, вероятно, будет стоить несколько байтов.)
mathmandan
@mathmandan maxбыл бы более эффективным, но ко второму пункту, поскольку мне не нужно беспокоиться о выводе, 0поскольку он генерируется диапазоном -t:t(где tпервый ненулевой коэффициент), он экономит 2 байта!
Джузеппе
О, очень мило! (И красивое объяснение тоже.)
Матемандан
2

Желе , 8 байт

ASŒRḅ@Ðḟ

Попробуйте онлайн!или как тестовый набор!

Как?

ASŒRḅ @ Ðḟ || Полная программа (монадическая ссылка).

AS || Суммируйте абсолютные значения.
  ŒR || И создайте симметричный включающий диапазон из его отрицательного значения.
       Ðḟ || И откажитесь от тех, которые дают истинную ценность ...
     ḅ @ || При подключении их к полиному (используется базовое преобразование).

Исходя из ответа Луиса . Альтернатива .

Мистер Xcoder
источник
Есть ли что-то, что я упускаю из-за принятия (разрешенного) обратного порядка и выполнения Ær+.Ḟ?
Джонатан Аллан
Я немного сбит с толку, так как в ответе Python на numpy это тоже не так, и я думаю, что пропустил какой-то крайний случай.
Джонатан Аллан
@JonathanAllan Как я и ожидал, у тебя ничего не получится [1,2,3].
г-н Xcoder
«Если для данного уравнения нет решения, то выход не определен»
Джонатан Аллан
@JonathanAllan Но это действительно не в состоянии в течение [10,-42,8], не так ли?
г-н Xcoder
2

Октава , 59 49 байт

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

Попробуйте онлайн!

Это порт моего R ответа . Единственное отличие состоит в том, что я должен явно использовать sign(t)и endгенерировать диапазон, и что он должен polyvalвычислять полином.

Принимает ввод как вектор строки коэффициентов в порядке убывания.

Giuseppe
источник
2

C (gcc) , 127 126 123 байта

  • Сохранено один байт благодаря Кевину Круйссену ; играть в гольф l+~j++в l-++j.
  • Благодаря Celercat за сохранение трех байтов.
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;}

Попробуйте онлайн!


объяснение

C (gcc) , 517 байтов

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

Попробуйте онлайн!

Джонатан Фрех
источник
l+~j++можно сыграть в гольфl-++j
Кевин Круйссен
@KevinCruijssen Большое спасибо.
Джонатан Фрех
@ceilingcat Спасибо.
Джонатан Фрех
1

Java 8, 141 140 байт

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

Вдохновлен ответом @Rod 's Python 2 (его версия на 82 байта) .

Веселый вызов! Я, конечно, многому научился, исследуя полиномы и видя, как это сделали некоторые другие здесь.

Объяснение:

Попробуйте онлайн.

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`
Кевин Круйссен
источник
0

JavaScript (ES6), 97 байт

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

Принимает коэффициенты в порядке убывания мощности и выводит результаты в порядке убывания.

Нил
источник