sicp 2.3小结习题尝试解答

 习题2.2没有全部做，我读书的速度远远超过做习题的进度，没办法，时间有限，晚上的时间基本用来看书了，习题也都是在工作间隙做的，慢慢来了，前两章读完再总结下。回到2.3节，这一节在前几节介绍数值型符号数据的基础上引入了符号数据，将任意符号作为数据的能力非常有趣，并给出了一个符号求导的例子，实在是太漂亮了。

习题2.53，直接看结果：

> (list 'a 'b 'c)

(a b c)

> (list (list 'george))

((george))

> (cdr '((x1 x2) (y1 y2)))

((y1 y2))

> (cadr '((x1 x2) (y1 y2)))

(y1 y2)

> (pair? (car '(a short list)))

#f

> (memq? 'red '((red shoes) (blue socks)))

> (memq? 'red '(red shoes blue socks))

(red shoes blue socks)

习题2.54，equal?过程的定义，递归定义，很容易

(define (equal? a b)

  (cond ((and (not (pair? a)) (not (pair? b)) (eq? a b)) #t)

        ((and (pair? a) (pair? b))

         (and (equal? (car a) (car b)) (equal? (cdr a) (cdr b))))

        (else

          (display "a and b are not equal"))))

注意，在drscheme实现中,eq?可以用于比较数值，比如(eq? 1 1)也是返回真

习题2.55，表达式(car ''abracadabra)其实就是

(car (quote (quote abracadabra)))，也就是(car '(quote abracadabra))，显然将返回quote

习题2.56，求幂表达式的导数，学着书中的代码写，也很容易了，先写出constructor和selector：

(define (make-exponentiation base e)

  (cond ((= e 0) 1)

        ((= e 1) base)

          (list '** base e))))

(define (base x) (cadr x))

(define (exponent x) (caddr x))

(define (exponentiation? x)

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

用**表示幂运算，因此(make-exponentiation x 3)表示的就是x的3次方。

修改deriv过程，增加一个条件分支：

(define (deriv exp var)

  (cond ((number? exp) 0)

        ((variable? exp)

         (if (same-variable? exp var) 1 0))

        ((sum? exp)

         (make-sum (deriv (addend exp) var)

                   (deriv (augend exp) var)))

        ((product? exp)

         (make-sum

            (make-product (multiplier exp)

                          (deriv (multiplicand exp) var))

            (make-product (multiplicand exp)

                          (deriv (multiplier exp) var))))

        ((exponentiation? exp)

         (let ((n (exponent exp)))

         (make-product (make-product n (make-exponentiation (base exp) (- n 1))) (deriv (base exp) var))))

           error "unknown expression type -- deriv" exp)))

粗体的就是我们增加的部分，两次运用make-product做乘法。

测试下：

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

(* 3 (** x 2))

> (deriv '(** (+ x 1) 5) 'x)

(* 5 (** (+ x 1) 4))

习题2.57，只要修改selector函数就够了，如果是多项的和或者积，那么被乘数和被加数也是列表，可以直接表示为符号表达式而不求值

 (define (augend s)

 (let ((rest (cddr s)))

    (if (null? (cdr rest))

        (car rest) 

        (cons '+ rest))))

(define (multiplicand p)

  (let ((rest (cddr p)))

        (cons '* rest))))

习题2.58，分为a和b，a倒是很容易解答，修改下谓词、选择函数和构造函数就可以了，将运算符号放在列表中间，注意，题目已经提示，假设+和*的参数都是两个，因此

(a)题目：

(define (=number? x y)

  (and (number? x) (= x y)))

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

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

(define (sum? x)

  (let ((op (cadr x)))

    (and (symbol? op) (eq? op '+))))

(define (addend s) (car s))

(define (augend s) (caddr s))

(define (make-sum a1 a2)

  (cond ((=number? a1 0) a2)

        ((=number? a2 0) a1)

        ((and (number? a1) (number? a2)) (+ a1 a2))

         (list a1 '+ a2))))

(define (product? x)

    (and (symbol? op) (eq? op '*))))

(define (multiplier x) (car x))

(define (multiplicand x) (caddr x))

(define (make-product a1 a2)

  (cond ((or (=number? a1 0) (=number? a2 0)) 0)

        ((=number? a1 1) a2)

        ((=number? a2 1) a1)

        ((and (number? a1) (number? a2)) (* a1 a2))

          (list a1 '* a2))))

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

4

> (deriv '(x + 3) 'x)

1

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

2

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

5

习题2.59，求集合的交集，遍历集合set1，如果(car set1)不在集合set2中，就将它加入set2，否则继续，当集合set1为空时返回set2。

(define (union-set set1 set2)

  (cond ((null? set1) set2)

        ((null? set2) set1)

        ((element-of-set? (car set1) set2) set2)

          (union-set set1 (cons (car set1) set2))))) 

习题2.60，需要修改的仅仅是adjoin-set：

(define (adjoin-set x set)

  (cons x set))

效率由原来的n变成常量。其他操作的效率与原来的一样。有重复元素的集合，比如成绩单、钱币等等。

习题2.61，关键点就是在于插入元素后要保持集合仍然是排序的，如果x小于(car set)，那么最小的就应该排在前面了，如果大于(car set)，那么将(car set)保留下来，继续往下找：

  (cond ((null? set) (list x))

        ((= x (car set)) set)

        ((< x (car set)) (cons x set))

           (cons (car set) (adjoin-set x (cdr set))))))

习题2.62，与求交集类似：

         (let ((x1 (car set1))

               (x2 (car set2)))

           (cond ((= x1 x2)

                  (cons x1

                        (union-set (cdr set1) (cdr set2))))

                 ((< x1 x2)

                        (union-set (cdr set1) set2)))

                 ((> x1 x2)

                  (cons x2

                        (union-set set1 (cdr set2)))))))))

> (define set1 (list 2 3 4 5 9 20))

> (define set2 (list 1 2 3 5 6 8))

> (union-set set1 set2)

(1 2 3 4 5 6 8 9 20)

习题2.63，其实两个变换过程都可以看成是对树的遍历

a)通过测试可以得知，产生一样的结果，两者都是中序遍历二叉树，书中图的那些树结果都是(1 3 5 7 9 11)

b)对于tree->list-1过程来说，考虑append过程，并且每一步并没有改变搜索规模，而append的增长阶是o(n)，因此tree->list-1的增长阶应该是o(n2)，n的二次方

而对于tree-list-2过程，增长阶显然是o(n)

习题2.64，这题非常有趣，用一个数组构造一棵平衡的树，显然，方法就是将数组对半拆分，并分别对两个部分进行构造，这两个部分还可以拆分直到遇到数组元素（左右子树都是'())，中间元素作为entry。这个过程可以一直递归下去。这里采用的正是这种方式

a)解释如上，(1 3 5 7 9 11)将形成下列的二叉树：

        5

       /  \

      1    9

       \  /  \

        3 7   11

显然，列表的对半拆分，以5作为根节点，然后左列表是(1 3)，右列表是(7 9 11)，左列表拆分就以1为节点，右列表拆分以9为节点，其他两个为子树。

b)仍然是o(n)

习题2.65，很简单了，转过来转过去就是了：

(define (union-set-1 tree1 tree2)

  (list->tree (union-set (tree->list-2 tree1)

                         (tree->list-2 tree2))))

(define (intersection-set-1 tree1 tree2)

  (list->tree (intersection-set (tree->list-2 tree1)

                                (tree->list-2 tree2))))

 习题2.66，与element-of-set?类似：

(define (lookup given-key set-of-records)

  (cond ((null? set-of-records) #f)

        ((= given-key (key (entry set-of-records))) (entry set-of-records))

        ((< given-key (key (entry set-of-records))) 

           (lookup given-key (left-branch set-of-records)))

        ((> given-key (key (entry set-of-records))) 

           (lookup given-key (right-branch set-of-records)))))

习题2.67，结果是(a d a b b c a) ，drscheme字母符号是小写

习题2.68，使用到memq过程用于判断符号是否在列表中：

(define (encode-symbol symbol tree)

  (define (iter branch)

    (if (leaf? branch)

        '()

        (if (memq symbol (symbols (left-branch branch)))

            (cons 0 (iter (left-branch branch)))

            (cons 1 (iter (right-branch branch))))

        ))

  (if (memq symbol (symbols tree))

      (iter tree)

      (display "bad symbol -- unknown symbol")))

习题2.69，因为make-leaf-set产生的已经排序的集合，因此从小到大两两合并即可：

(define (generate-huffman-tree pairs)

  (successive-merge (make-leaf-set pairs)))

(define (successive-merge set)

习题2.70，利用generate-huffman-tree和encode过程得到消息，使用length测量下消息长度就知道多少位了：

(define roll-tree (generate-huffman-tree '((a 2) (na 16) (boom 1) (sha 3) (get 2) (yip 9) (job 2) (wah 1))))

(define message (encode

         '(get a job sha na na na na na na na na get a job sha na na na na na na na na wah yip yip yip yip yip yip yip yip yip sha boom)

         roll-tree))

> (length message)

84

  通过huffman编码后的位数是84位，如果采用定长编码，因为需要表示8个不同符号，因此需要log2(8)=3位二进制，总位数至少是36*3=108位，压缩比为22.22%

习题2.71，很显然，最频繁出现的符号肯定在根节点下来的子树，位数是1，而最不频繁的符号是n-1位

文章转自庄周梦蝶  ，原文发布时间2007-07-03