Полиномиальное длинное деление

10

Реализуйте полиномиальное длинное деление, алгоритм, который делит два полинома и получает частное и остаток:

(12x ^ 3 - 5x ^ 2 + 3x - 1) / (x ^ 2 - 5) = 12x - 5 R 63x - 26

В ваших программах вы будете представлять полиномы в виде массива с постоянным членом на хвосте. например, x ^ 5 - 3x ^ 4 + 2x ^ 2 - x + 1 станет [1, -3, 0, 2, -1, 1].

Функция длинного деления, которую вы собираетесь написать, вернет два значения: частное и остаток. Вам не нужно обрабатывать неточности и арифметические ошибки. Не используйте математическую библиотеку для своей работы, однако вы можете сделать так, чтобы ваша функция могла работать с символическими значениями. Самый короткий код выигрывает.

ПРИМЕР: div([12, -5, 3, -1], [1, 0, -5]) == ([12, -5], [63, -26])

code-golf math abstract-algebra polynomials Мин-Tang
источник
rosettacode.org/wiki/Polynomial_synthetic_division#Python
ghosts_in_the_code

Ответы:

3

J, 94

f=:>@(0&{)
d=:0{[%~0{[:f]
D=:4 :'x((1}.([:f])-((#@]{.[)f)*d);([:>1{]),d)^:(>:((#f y)-(#x)))y'

например.

(1 0 _5) D (12 _5 3 _1;'')
63 _26 | 12  _5

Объяснение некоторых фрагментов, учитывая, что a: (12 -5 3 -1) и b: (1 0 -5)

длина:

#a
4

сделать a и b одинаковый порядок, добавив нули к b:

(#a) {. b
1 0 -5 0

разделить высшие силы (первые элементы) a, b:

(0{a) % (0{b)
12

умножьте b на это и вычтите это из a:

a - 12*b
12 0 _60

повторить n раз b = f (a, b):

a f^:n b
Eelvex
источник
Две вещи. 1) Вы выигрываете персонажей, принимая дивиденды / делители в необычном порядке? 2) необходим ли трейлинг `; '' 'в дивиденде? выглядит как то, что вы должны сделать изнутри фактической программы.
JB
@JB: 1) Нет, на самом деле это может быть короче для «обычного» порядка; это просто способ, которым я начал думать об этом. 2) Это часть массива, поэтому я полагаю, что он должен быть частью ввода.
Eelvex
Я не могу понять, что дополнительный пустой массив имеет отношение к вводу.
JB
3

Python 2, 260 258 257 255 байт

exec'''def d(p,q):
 R=range;D=len(p);F=len(q)-1;d=q[0];q=[q[i]/-d@R(1,F+1)];r=[0@R(D)];a=[[0@R(F)]@R(D)]
@R(D):
  p[i]/=d;r[i]=sum(a[i])+p[i]
  for j in R(F):
   if i<D-F:a[i+j+1][F-j-1]=r[i]*q[j]
 return r[:D-F],[d*i@r[D-F:]]'''.replace('@',' for i in ')

Это выполняет:

def d(p,q):
 R=range;D=len(p);F=len(q)-1;d=q[0];q=[q[i]/-d for i in R(1,F+1)];r=[0 for i in R(D)];a=[[0 for i in R(F)] for i in R(D)]
 for i in R(D):
  p[i]/=d;r[i]=sum(a[i])+p[i]
  for j in R(F):
   if i<D-F:a[i+j+1][F-j-1]=r[i]*q[j]
 return r[:D-F],[d*i for i in r[D-F:]]

Используйте так:

>>>d([12., -5., 3., -1.],[1.,0.,-5.])
([12.0, -5.0], [63.0, -26.0])
Джастин
источник
1
Вау, впервые я увидел, что exec / replace действительно используется для сохранения символов.
xnor
@xnor Я сделал это в другой раз, но для более чем одной замены.
Джастин
2

Хаскелл, 126

Для начала:

l s _ 0=s
l(x:s)(y:t)n=x/y:l(zipWith(-)s$map(*(x/y))t++repeat 0)(y:t)(n-1)
d s t=splitAt n$l s t n where n=length s-length t+1

Образец использования:

*Main> d [12, -5, 3, -1] [1, 0, -5]
([12.0,-5.0],[63.0,-26.0])
JB
источник
1

Javascript с лямбдами, 108

f=(a,b)=>{for(n=b.length;a.length>=n;a.shift())for(b.push(k=a[q=0]/b[0]);q<n;++q)a[q]-=k*b[q];b.splice(0,n)}

Первый аргумент заменяется напоминанием, а второй - результатом.

Пример использования в Firefox:

f(x=[12,-5,3,-1], y=[1,0,-5]), console.log(x, y)
// Array [ 63, -26 ] Array [ 12, -5 ]

Извините за ошибку. Уже исправлено.

Qwertiy
источник