태그 보관물: abstract-algebra

abstract-algebra

다항식 긴 나눗셈 -3, 0,

두 개의 다항식을 나누고 몫과 나머지를 얻는 알고리즘 인 다항식 긴 나눗셈을 구현합니다.

(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]이됩니다.

작성할 long 나누기 함수는 몫과 나머지 두 값을 반환합니다. 수치 적 부정확성과 산술 오류를 처리 할 필요는 없습니다. 수학 라이브러리를 사용하여 작업을 수행하지 마십시오. 그러나 함수가 기호 값을 처리 할 수있게 만들 수 있습니다. 가장 짧은 코드가 승리합니다.

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

답변

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 : (100-5)를 제외하고 일부 스 니펫에 대한 설명

길이 :

#a
4

b에 0을 추가하여 a와 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

답변

파이썬 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])

답변

하스켈, 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])

답변

람다가 포함 된 자바 스크립트, 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 ]

버그 죄송합니다. 이미 수정되었습니다.

답변