sicp 笔记 (4)

第二章习题 2.52 – 2.72 的解答。

E-2.52: 跳过……

E-2.53: 直接运行一下结果就出来了。

E-2.54:

(define (my-equal? a b)
  (if (and (pair? a) (pair? b))
    (and (my-equal? (car a) (car b))
         (my-equal? (cdr a) (cdr b)))
    (eq? a b)))

; ----------------------------------------------

(my-equal? '(this is a list) '(this (is a) list))
(my-equal? '(this (is a) list) '(this (is a) list))

E-2.55: 展开式为“(car (quote (quote abracadabra)))”。

E-2.56:

(load "../examples/2.3.2-symbolic-differentiation.scm")

(define (make-exponentation base exponent)
  (cond ((=number? exponent 0) 1)
        ((=number? exponent 1) base)
        (else (list '** base exponent))))

(define (exponentation? x)
  (and (pair? x) (eq? (car x) '**)))

(define (base x) (cadr x))
(define (exponent x) (caddr x))

; -----------------------------------------------------------------------

(define (deriv e v)
  (cond ((number? e) 0)
        ((variable? e)
         (if (same-variable? e v) 1 0))
        ((sum? e)
         (make-sum (deriv (addend e) v)
                   (deriv (augend e) v)))
        ((product? e)
         (make-sum (make-product (multiplier e)
                                 (deriv (multipliend e) v))
                   (make-product (deriv (multiplier e) v))))
        ((exponentation? e)
         (let ((b (base e))
               (ex (exponent e)))
           (make-product (make-product ex (make-exponentation b (- ex 1)))
                         (deriv b v))))
        (else
          (error "unknown expression type --DERIV" e))))

; -----------------------------------------------------------------------

(deriv '(** x 3) 'x)

E-2.57: 根据题目的提示,改动的只有返回第二个加数和返回乘数的两个函数。

(define (variable? x) (symbol? x))

(define (same-variable? v1 v2)
  (and (variable? v1) (variable? v2) (eq? v1 v2)))

(define (=number? e n)
  (and (number? e) (= e n)))

(define (make-sum a1 a2)
  (cond ((=number? a1 0) a2)
        ((=number? a2 0) a1)
        ((and (number? a1) (number? a2)) (+ a1 a2))
        (else (list '+ a1 a2))))

(define (make-product m1 m2)
  (cond ((or (=number? m1 0) (=number? m2 0)) 0)
        ((=number? m1 1) m2)
        ((=number? m2 1) m1)
        ((and (number? m1) (number? m2)) (* m1 m2))
        (else (list '* m1 m2))))

(define (sum? x)
  (and (pair? x) (eq? (car x) '+)))

(define (addend s) (cadr s))

(define (augend s)
  (if (null? (cdddr s))
    (caddr s)
    (append (list '+) (cddr s))))

(define (product? x)
  (and (pair? x) (eq? (car x) '*)))

(define (multiplier p) (cadr p))

(define (multipliend p)
  (if (null? (cdddr p))
    (caddr p)
    (append (list '*) (cddr p))))

; ----------------------------------------------------------

(define (deriv e v)
  (cond ((number? e) 0)
        ((variable? e)
         (if (same-variable? e v) 1 0))
        ((sum? e)
         (make-sum (deriv (addend e) v)
                   (deriv (augend e) v)))
        ((product? e)
         (make-sum (make-product (multiplier e)
                                 (deriv (multipliend e) v))
                   (make-product (deriv (multiplier e) v)
                                 (multipliend e))))
        (else
          (error "unknown expression type --DERIV" e))))

; ----------------------------------------------------------

(deriv '(* x y (+ x 3)) 'x)

E-2.58: 第一个小题比较容易,就是换一下符号的位置;第二小题为了保证乘法的优先级,不管是加法还是乘法都是先算符号后面的部分,例如“3 + 5 * 2”,先算的是乘法,然后加法,其实和 E-2.57 类似。

(define (variable? x) (symbol? x))

(define (same-variable? v1 v2)
  (and (variable? v1) (variable? v2) (eq? v1 v2)))

(define (=number? e n)
  (and (number? e) (= e n)))

(define (make-sum a1 a2)
  (cond ((=number? a1 0) a2)
        ((=number? a2 0) a1)
        ((and (number? a1) (number? a2)) (+ a1 a2))
        (else (list a1 '+ a2))))

(define (make-product m1 m2)
  (cond ((or (=number? m1 0) (=number? m2 0)) 0)
        ((=number? m1 1) m2)
        ((=number? m2 1) m1)
        ((and (number? m1) (number? m2)) (* m1 m2))
        (else (list m1 '* m2))))

(define (sum? x)
  (and (pair? x) (eq? (cadr x) '+)))

(define (addend s) (car s))

(define (augend s) (caddr s))

(define (product? x)
  (and (pair? x) (eq? (cadr x) '*)))

(define (multiplier p) (car p))

(define (multipliend p) (caddr p))

; ----------------------------------------------------------

(define (deriv e v)
  (cond ((number? e) 0)
        ((variable? e)
         (if (same-variable? e v) 1 0))
        ((sum? e)
         (make-sum (deriv (addend e) v)
                   (deriv (augend e) v)))
        ((product? e)
         (make-sum (make-product (multiplier e)
                                 (deriv (multipliend e) v))
                   (make-product (deriv (multiplier e) v)
                                 (multipliend e))))
        (else
          (error "unknown expression type --DERIV" e))))

; ----------------------------------------------------------

(deriv '(x + (3 * (x + (y + 2)))) 'x)
(deriv '(x * (y * (x + 3))) 'x)
(define (variable? x) (symbol? x))

(define (same-variable? v1 v2)
  (and (variable? v1) (variable? v2) (eq? v1 v2)))

(define (=number? e n)
  (and (number? e) (= e n)))

(define (make-sum a1 a2)
  (cond ((=number? a1 0) a2)
        ((=number? a2 0) a1)
        ((and (number? a1) (number? a2)) (+ a1 a2))
        (else (list a1 '+ a2))))

(define (make-product m1 m2)
  (cond ((or (=number? m1 0) (=number? m2 0)) 0)
        ((=number? m1 1) m2)
        ((=number? m2 1) m1)
        ((and (number? m1) (number? m2)) (* m1 m2))
        (else (list m1 '* m2))))

(define (sum? x)
  (and (pair? x) (eq? (cadr x) '+)))

(define (addend s) (car s))

(define (augend s) (caddr s))

(define (augend s)
  (if (null? (cdddr s))
    (caddr s)
    (cddr s)))

(define (product? x)
  (and (pair? x) (eq? (cadr x) '*)))

(define (multiplier p) (car p))

(define (multipliend p)
  (if (null? (cdddr p))
    (caddr p)
    (cddr p)))

; ----------------------------------------------------------

(define (deriv e v)
  (cond ((number? e) 0)
        ((variable? e)
         (if (same-variable? e v) 1 0))
        ((sum? e)
         (make-sum (deriv (addend e) v)
                   (deriv (augend e) v)))
        ((product? e)
         (make-sum (make-product (multiplier e)
                                 (deriv (multipliend e) v))
                   (make-product (deriv (multiplier e) v)
                                 (multipliend e))))
        (else
          (error "unknown expression type --DERIV" e))))

; ----------------------------------------------------------

(deriv '(x + 3 * (x + y + 2)) 'x)

E-2.59: null? 对 cons 的判断有些问题,因此把题目中的 cons 改成 list 了。

(load "../examples/2.3.3-representing-sets.scm")

(define (diff-set s1 s2)
  (define (filter-s s)
    (if (null? s)
      (list)
      (let ((first (car s)) (rest (cdr s)))
        (if (element-of-set? first s2)
          (filter-s rest)
          (append (list first) (filter-s rest))))))

  (if (null? s2)
    s1
    (filter-s s1)))

(define (union-set s1 s2)
  (append (diff-set s1 s2) s2))

; -----------------------------------------------------------

(union-set (list 3 4 5 6 7 8) (list 4 5 3 7))

E-2.60: 我觉得还是会使用非重复的版本,首先是节约空间,不会有重复的元素。不过在效率上来说像确定某个元素是否属于某个集合(有副本找到的几率变大),添加元素,并集等操作都提高了(因为不需要检查唯一性),交集不好说,虽然查找元素速度有提高,但是要遍历的元素多了。

E-2.61: 写了递归和迭代两个版本。

(define (adjoin-set x set)

  (define (iter rest result)
    (if (null? rest)
      (append result (list x))
      (cond ((= x (car rest)) (append result rest))
            ((< x (car rest)) (append result (list x) rest))
            (else (iter (cdr rest) (append result (list (car rest))))))))

  (define (recur s)
    (if (null? s)
      (list x)
      (let ((first (car s)))
        (cond ((= x first) s)
              ((< x first) (append (list x) s))
              (else (append (list first) (recur (cdr s))))))))

  (iter set '()))

; ------------------------------------------------------------------------------

(adjoin-set 9 (list 1 3 5 7))

E-2.62:

(define (union-set s1 s2)
  (define (recur a b)
    (cond ((null? a) b)
          ((null? b) a)
          (else (let ((x1 (car a)) (x2 (car b)))
                  (cond ((= x1 x2) (append (list x1) (recur (cdr a) (cdr b))))
                        ((< x1 x2) (append (list x1) (recur (cdr a) b)))
                        (else (append (list x2) (recur a (cdr b)))))))))

  (recur s1 s2))

; ------------------------------------------------------------------------------

(union-set (list 1 3 5 7 9) (list 1 3 5 7))

E-2.63: (a) 两个都是中序遍历的程序,第一个是递归的,第二个是迭代,打印的结果都一样。(b) 两个的时间复杂度都是 O(logn)。

E-2.64: (a) 程序的工作过程是:每次先取列表的中间值,然后分别对中值两边的元素分别构造两棵子树。(b) 时间复杂度是 O(logn)。

E-2.65: union-set 和 intersection-set 的时间复杂度都是 O(n),list->tree 和 tree->list-* 的时间复杂度是 O(logn),因此总的时间复杂度是 O(n)。

(load "2.62.scm") ; union-set
(load "2.64.scm") ; list->tree

(define (union-set-balanced s1 s2)
  (list->tree (union-set (tree->list-1 s1) (tree->list-2 s2))))

(define (intersection-set-balanced s1 s2)
  (list->tree (intersection-set (tree->list-1 s1) (tree->list-2 s2))))

; ---------------------------------------------------------------------

(load "2.63.scm") ; l and r

(union-set-balanced l r)
(intersection-set-balanced l r)

E-2.66: 典型的二叉树查找。

(load "../examples/2.3.3-representing-sets.scm")

(define (key x) (entry x))

(define (lookup given-key set-of-records)
  (cond ((null? set-of-records) #f)
        ((= given-key (key set-of-records))
         (key set-of-records))
        ((< given-key (key set-of-records))
         (lookup given-key (left-branch set-of-records)))
        (else (lookup given-key (right-branch set-of-records)))))

; -------------------------------------------------

(define n1 (make-tree 1 '() '()))
(define n3 (make-tree 3 '() '()))
(define n5 (make-tree 5 '() '()))
(define n7 (make-tree 7 '() '()))
(define l (make-tree 2 n1 n3))
(define r (make-tree 6 n5 n7))
(define t (make-tree 4 l r))

(lookup 5 t)

E-2.67: (a d a b b c a)

E-2.68: 判断字符是否合法只需在根节点找一遍即可,因为根节点包含了所有节点。

(load "../examples/2.3.4-huffman-encoding-trees.scm")

(define (encode-symbol s tree)
  (define (valid? x branch)
    (memq x (symbols branch)))

  (define (encode-1 s current-branch)
    (if (leaf? current-branch)
      '()
      (if (valid? s (left-branch current-branch))
        (append (list 0) (encode-1 s (left-branch current-branch)))
        (append (list 1) (encode-1 s (right-branch current-branch))))))

  (if (valid? s tree)
    (encode-1 s tree)
    (error "bad character ->" s)))

; ---------------------------------------------------------------

(define (encode message tree)
  (if (null? message)
    '()
    (append (encode-symbol (car message) tree)
            (encode (cdr message) tree))))

(define sample-tree
  (make-code-tree (make-leaf 'A 4)
                  (make-code-tree
                    (make-leaf 'B 2)
                    (make-code-tree (make-leaf 'D 1)
                                    (make-leaf 'C 1)))))

(encode '(A D A B B C A) sample-tree)

E-2.69:

(load "../examples/2.3.4-huffman-encoding-trees.scm")

(define (successive-merge l)
  (if (null? l)
    '()
    (if (null? (cdr l))
      (car l)
      (successive-merge (adjoin-set (make-code-tree (car l) (cadr l))
                                    (cddr l))))))

; -------------------------------------------------------

(define (generate-huffman-tree pairs)
  (successive-merge (make-leaf-set pairs)))

(define sample-list '((a 4) (b 2) (c 1) (d 1)))

(generate-huffman-tree sample-list)

E-2.70: 一共用了 84bit,如果用定长编码每个符号需要 3 位,编码长度为 108bit。

E-2.71: 最短编码是 1 bit,最长的是 (n-1) bit。

E-2.72: 按照 2.71 的情况,如果都是最频繁的需要 O(n),都是最不频繁的需要 O(n^2)。如果频率均匀分布,那么树高接近 O(logn),这时复杂度为 O(nlogn)。

发表于 2013年4月29日
本文目前尚无任何评论.

发表评论

XHTML: 您可以使用这些标签: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>