Divisi Panjang Polinomial

10

Menerapkan pembagian panjang polinomial, suatu algoritma yang membagi dua polinomial dan mendapatkan hasil bagi dan sisanya:

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

Dalam program Anda, Anda akan merepresentasikan polinomial sebagai array, dengan suku konstanta di ekornya. misalnya, x ^ 5 - 3x ^ 4 + 2x ^ 2 - x + 1 akan menjadi [1, -3, 0, 2, -1, 1].

Fungsi pembagian panjang yang akan Anda tulis akan mengembalikan dua nilai: hasil bagi dan sisanya. Anda tidak perlu menangani ketidaktepatan numerik dan kesalahan aritmatika. Jangan gunakan perpustakaan matematika untuk melakukan pekerjaan Anda, namun, Anda dapat membuat fungsi Anda mampu menangani nilai simbolik. Kode terpendek menang.

CONTOH: div([12, -5, 3, -1], [1, 0, -5]) == ([12, -5], [63, -26])

code-golf math abstract-algebra polynomials Ming-Tang
sumber
rosettacode.org/wiki/Polynomial_synthetic_division#Python
ghosts_in_the_code

Jawaban:

3

J, 94

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

misalnya.

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

Penjelasan beberapa cuplikan, mengingat bahwa: (12 -5 3 -1) dan b: (1 0 -5)

panjang:

#a
4

buat a dan b urutan yang sama dengan menambahkan nol ke b:

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

membagi kekuatan yang lebih tinggi (elemen pertama) dari a, b:

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

kalikan b dengan itu dan kurangi dari:

a - 12*b
12 0 _60

ulangi n kali b = f (a, b):

a f^:n b
Eelvex
sumber
Dua hal. 1) apakah Anda memenangkan karakter dengan mengambil dividen / pembagi dalam urutan yang tidak biasa? 2) apakah membuntuti `; '' 'dalam dividen diperlukan? Sepertinya sesuatu yang harus Anda lakukan dari dalam program yang sebenarnya.
JB
@ JP: 1) Tidak, sebenarnya bisa lebih pendek untuk pesanan "biasa"; itu hanya cara saya mulai memikirkannya. 2) Ini bagian dari array jadi saya kira itu harus menjadi bagian dari input.
Eelvex
Saya tidak bisa memahami apa yang harus dilakukan oleh array kosong tambahan dengan input.
JB
3

Python 2, 260 258 257 255 byte

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

Ini dijalankan:

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

Gunakan seperti ini:

>>>d([12., -5., 3., -1.],[1.,0.,-5.])
([12.0, -5.0], [63.0, -26.0])
Justin
sumber
1
Wow, pertama kali saya melihat eksekutif / ganti sebenarnya digunakan untuk menyimpan karakter.
xnor
@ xnor Saya sudah melakukannya sekali lagi, tetapi untuk lebih dari satu penggantian.
Justin
2

Haskell, 126

Sebagai permulaan:

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

Penggunaan sampel:

*Main> d [12, -5, 3, -1] [1, 0, -5]
([12.0,-5.0],[63.0,-26.0])
JB
sumber
1

Javascript dengan lambdas, 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)}

Ini menggantikan argumen pertama dengan pengingat dan yang kedua dengan hasil.

Contoh penggunaan di Firefox:

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

Maaf untuk bugnya. Sudah diperbaiki.

Qwertiy
sumber