第二章习题 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)。