다항식 패키지는 대수를 태그 데이터의 연산으로 바꾼다.
희소 항 목록은 차수와 계수를 명시적으로 보존합니다. 범용 add와 multiply 메서드는 같은 차수를 합치고 0 계수를 제거하며 다항식 변수를 유지하고 맞지 않는 변수는 거부합니다.
범용 산술 시스템은 항 목록의 세부 표현을 클라이언트 코드에 퍼뜨리지 않고 다항식 구조를 어떻게 다룰까요?
- 희소 다항식을 변수와 내림차순 항으로 표현하기
- 두 항 목록을 더하며 같은 차수 합치기
- 곱셈 중 한 항을 다른 다항식 전체에 분배하기
- 표현 경계에서 0 계수 항 제거하기
- 타입 태그 메서드로 다항식 덧셈과 곱셈 디스패치하기
- 변수가 다른 다항식의 연산 거부하기
첫 프로그램은 각 항을 차수와 계수로 표현하고 높은 차수부터 낮은 차수 순서로 저장합니다. add-terms는 앞에서 정렬 집합에 사용한 것과 같은 병합을 수행합니다. 더 큰 차수는 그대로 옮기고 같은 차수는 계수를 합치며 adjoin-term은 결과가 0인 항을 생략합니다. 다항식 패키지가 이 표현을 소유하고 태그가 붙은 add 메서드 하나를 노출하므로 x² + 2x + 1과 x² − 1의 합은 명시적인 0 상수항 없이 2x² + 2x가 됩니다. y 다항식은 서로 다른 미지수를 조용히 섞지 않고 different-variables를 반환합니다.
두 번째 프로그램은 한 항을 다른 다항식의 모든 항에 곱하고, 차수는 더하고 계수는 곱한 뒤, 부분 곱을 add-terms로 병합합니다. (x + 1)(x − 1)에서는 가운데 두 항이 상쇄되어 x² − 1만 남습니다. 별도 평가기는 패키지 선택자만 사용해 x = 3에서 8을 보고합니다. 이 수업은 희소 단일 변수 정수 계수 다항식만 모형화하며 조밀 표현과 다변수 정규화, 다항식 gcd, 유리 함수, 완전한 컴퓨터 대수 시스템은 구현하지 않습니다.
(begin
(define (attach-tag type contents) (cons type contents))
(define (type-tag object) (car object))
(define (contents object) (cdr object))
(define (make-term order coefficient)
(list order coefficient))
(define (order term) (car term))
(define (coefficient term) (cadr term))
(define (adjoin-term term terms)
(if (= (coefficient term) 0)
terms
(cons term terms)))
(define (add-terms left right)
(cond ((null? left) right)
((null? right) left)
(else
(let ((left-term (car left))
(right-term (car right)))
(cond ((> (order left-term) (order right-term))
(adjoin-term
left-term
(add-terms (cdr left) right)))
((< (order left-term) (order right-term))
(adjoin-term
right-term
(add-terms left (cdr right))))
(else
(adjoin-term
(make-term
(order left-term)
(+ (coefficient left-term)
(coefficient right-term)))
(add-terms (cdr left) (cdr right)))))))))
(define (make-polynomial variable terms)
(attach-tag 'polynomial (cons variable terms)))
(define (variable polynomial-contents)
(car polynomial-contents))
(define (term-list polynomial-contents)
(cdr polynomial-contents))
(define (add-polynomial-contents left right)
(if (eq? (variable left) (variable right))
(make-polynomial
(variable left)
(add-terms (term-list left) (term-list right)))
'different-variables))
(define operation-table
(list
(cons (list 'add 'polynomial 'polynomial)
add-polynomial-contents)))
(define (lookup-entry key table)
(cond ((null? table) #f)
((equal? key (car (car table)))
(cdr (car table)))
(else (lookup-entry key (cdr table)))))
(define (apply-generic operation left right)
(let ((method
(lookup-entry
(list operation (type-tag left) (type-tag right))
operation-table)))
(if method
(method (contents left) (contents right))
'no-method)))
(define p
(make-polynomial
'x
(list (make-term 2 1)
(make-term 1 2)
(make-term 0 1))))
(define q
(make-polynomial
'x
(list (make-term 2 1)
(make-term 0 -1))))
(define y
(make-polynomial 'y (list (make-term 1 1))))
(list (apply-generic 'add p q)
(apply-generic 'add p y)))- 출력
- —
- 값
- —
- 진단
- —
덧셈 프로그램은 ((polynomial x (2 2) (1 2)) different-variables)를 반환합니다. 곱셈 프로그램은 ((polynomial x (2 1) (0 -1)) 8)을 반환합니다.
덧셈에서는 내림차순 차수 비교와 같은 차수 계수 합이 0 상수항을 제거하는 지점을 따라가세요. 곱셈에서는 각 차수 이동과 계수 곱, 재귀적인 부분 곱, 두 1차 항을 상쇄하는 add-terms 병합을 찾으세요. 변수 검사는 표현 연산이 시작되기 전에 일어납니다.
힌트를 보기 전에 프로그램을 바꿔 보세요.
x² + x + 1과 x − 1을 곱하고 희소 항 목록을 예상한 뒤 x = 2에서 값을 계산하세요.
힌트 하나 보기
왼쪽의 각 항마다 부분 곱을 하나 만들고 같은 차수를 병합하세요. 1차항과 상수항의 상쇄는 서로 다른 단계에서 일어납니다.