SICP 全笔记

Exercise 2.94. Using div-terms, implement the procedure remainder-terms and use this to define gcd-terms as above. Now write a procedure gcd-poly that computes the polynomial GCD of two polys. (The procedure should signal an error if the two polys are not in the same variable.) Install in the system a generic operation greatest-common-divisor that reduces to gcd-poly for polynomials and to ordinary gcd for ordinary numbers. As a test, try

(define p1 (make-polynomial 'x '((4 1) (3 -1) (2 -2) (1 2))))
(define p2 (make-polynomial 'x '((3 1) (1 -1))))
(greatest-common-divisor p1 p2)

and check your result by hand.

在 练习 2.91 中，我们已经写好了 div 来计算两个多项式的除法。div 的结果是一个 list，第一项是商，第二项是余数。

借用 div-terms 我们可以实现多项式的 gcd：

首先是用 div-poly 来实现 gcd-poly：

  (define (div-poly p1 p2)
    (if (same-variable? (variable p1) (variable p2))
        (let ((result  (div-terms (term-list p1)
                                  (term-list p2))))
          (list
           (make-poly (variable p1) (car result))
           (make-poly (variable p1) (cadr result))))
        (error "Polys not in same var -- DIV-POLY"
               (list p1 p2))))

  (define (gcd-poly p1 p2)
    (if (same-variable? (variable p1) (variable p2))
        (let ((g (gcd-terms (term-list p1)
                            (term-list p2))))
          (make-poly (variable p1) g))
        (error "Polys not in same var -- GCD-POLY"
               (list p1 p2))))

上面的实现中 gcd-poly 使用了 gcd-terms，定义如下：

  (define (remainder-terms L1 L2)
    (let ((result (div-terms L1 L2)))
      (cadr result)))

  (define (gcd-terms a b)
    (if (empty-termlist? b)
        a
        (gcd-terms b (remainder-terms a b))))

最后是定义 greatest-common-divisor：

  (put 'greatest-common-divisor '(polynomial polynomial)
       (lambda (p1 p2)
         (tag (gcd-poly p1 p2))))

同时我们定义一个泛型的 greatest-common-divisor 以及处理 scheme-number 类型的 greatest-common-divisor：

;; install greatest-common-divisor for scheme-number
(put 'greatest-common-divisor '(scheme-number scheme-number)
     (lambda (a b)
       (gcd a b)))

; generic greatest-common-divisor
(define (greatest-common-divisor a b)
  (apply-generic 'greatest-common-divisor a b))
; end 4.

(install-polynomial-package)

;;; tests begin
(load "../testframe.scm")

(let ((p1 (make-polynomial 'x '((4 1) (3 -1) (2 -2) (1 2))))
      (p2 (make-polynomial 'x '((3 1) (1 -1)))))
  (asserttrue (or (equal? (greatest-common-divisor p1 p2)
                          (make-polynomial 'x '((2 1) (1 -1))))
                  (equal? (greatest-common-divisor p1 p2)
                          (make-polynomial 'x '((2 -1) (1 1)))))))

(assert= (greatest-common-divisor 3 12) 3)

最后是测试：

(load "../testframe.scm")

(let ((p1 (make-polynomial 'x '((4 1) (3 -1) (2 -2) (1 2))))
      (p2 (make-polynomial 'x '((3 1) (1 -1)))))
  (asserttrue (or (equal? (greatest-common-divisor p1 p2)
                          (make-polynomial 'x '((2 1) (1 -1))))
                  (equal? (greatest-common-divisor p1 p2)
                          (make-polynomial 'x '((2 -1) (1 1)))))))

(assert= (greatest-common-divisor 3 12) 3)

值得注意的是，最后求出多项式的 greatest-common-divisor，可能与预期的结果互为相反数，这在多项式中当然是允许的，所以我们的测试中不得不使用 or 来判断最终的结果。