Division longue polynomiale

10

Implémentez la division longue polynomiale, un algorithme qui divise deux polynômes et obtient le quotient et le reste:

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

Dans vos programmes, vous représenterez les polynômes sous forme de tableau, avec le terme constant sur la queue. par exemple, x ^ 5 - 3x ^ 4 + 2x ^ 2 - x + 1 deviendra [1, -3, 0, 2, -1, 1].

La fonction de division longue que vous allez écrire renverra deux valeurs: le quotient et le reste. Vous n'avez pas besoin de gérer les imprécisions numériques et les erreurs arithmétiques. N'utilisez pas la bibliothèque mathématique pour faire votre travail, cependant, vous pouvez rendre votre fonction capable de gérer des valeurs symboliques. Le code le plus court gagne.

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

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

Réponses:

3

J, 94

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

par exemple.

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

Explication de quelques extraits, étant donné que a: (12 -5 3 -1) et b: (1 0 -5)

longueur d'un:

#a
4

faire un et b même ordre en ajoutant des zéros à b:

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

diviser les puissances supérieures (premiers éléments) de a, b:

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

multipliez b par cela et soustrayez-le de a:

a - 12*b
12 0 _60

répéter n fois b = f (a, b):

a f^:n b
Eelvex
la source
Deux choses. 1) gagnez-vous des personnages en prenant des dividendes / diviseurs dans l'ordre inhabituel? 2) est-ce que la fuite `` '' dans le dividende est nécessaire? ressemble à quelque chose que vous devriez faire à l'intérieur du programme réel.
JB
@JB: 1) Non, en fait, cela pourrait être plus court pour l'ordre "habituel"; c'est juste la façon dont j'ai commencé à y penser. 2) Cela fait partie du tableau, donc je suppose que cela devrait faire partie de l'entrée.
Eelvex
Je n'arrive pas à comprendre ce qu'un tableau vide supplémentaire a à voir avec l'entrée.
JB
3

Python 2, 260 258 257 255 octets

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

Cela exécute:

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

Utilisez comme ça:

>>>d([12., -5., 3., -1.],[1.,0.,-5.])
([12.0, -5.0], [63.0, -26.0])
Justin
la source
1
Wow, la première fois que j'ai vu un exécutable / remplacer utilisé pour enregistrer des caractères.
xnor
@xnor Je l'ai fait une autre fois, mais pour plus d'un remplacement.
Justin
2

Haskell, 126

Pour un début:

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

Exemple d'utilisation:

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

Javascript avec 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)}

Il remplace le premier argument par rappel et le second par résultat.

Exemple d'utilisation dans Firefox:

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

Désolé pour le bug. Déjà réparé.

Qwertiy
la source