计算机程序的构造和解释(SICP) 第2章 习题解析 Part5

这次回顾第二章第五部分习题。

学习资料：

https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-001-structure-and-interpretation-of-computer-programs-spring-2005/index.htm

https://github.com/DeathKing/Learning-SICP

https://mitpress.mit.edu/sites/default/files/sicp/index.html

https://www.bilibili.com/video/BV1Xx41117tr?from=search&seid=14983483066585274454

参考资料：

https://sicp.readthedocs.io/en/latest

2.59(p104)

(load "unordered-set.scm")

(define (union-set set1 set2)
    (cond ((null? set1) set2)
          ((null? set2) set1)
          (else (union-set (cdr set1) (adjoin-set (car set1) set2)))))

; test
(define set1 (list 1 2 3 4))
(define set2 (list 7 6 5 4))
(define set3 '())
(display (union-set set1 set2))
(newline)
(display (union-set set1 set3))
(exit)

结果如下：

(3 2 1 7 6 5 4)
(1 2 3 4)

2.60(p104)

时间复杂度：

• element-of-set?: $\Theta(n)$
• adjoin-set: $\Theta(1)$
• intersection-set: $\Theta(n^2)$
• union-set: $\Theta(n)$

在adjoin-set操作以及union操作较多的时候使用这种表达，代码如下：

(define true #t)
(define false #f)

(define (element-of-set? x set)
    (cond ((null? set) false)
          ((equal? x (car set)) true)
          (else (element-of-set? x (cdr set)))))

(define (adjoin-set x set)
    (cons x set))

(define (intersection-set set1 set2)
    (cond ((or (null? set1) (null? set2)) '())
          ((element-of-set? (car set1) set2)
            (cons (car set1)
                  (intersection-set (cdr set1) set2)))
          (else (intersection-set (cdr set1) set2))))

(define (union-set set1 set2)
    (cond ((null? set1) set2)
          ((null? set2) set1)
          (else (union-set (cdr set1) (adjoin-set (car set1) set2)))))

; test
(define set1 (list 1 2 3 4))
(define set2 (list 7 6 5 4))
(define set3 '())
(display (intersection-set set1 set2))
(newline)
(display (union-set set1 set2))
(newline)
(display (union-set set1 set3))
(exit)

结果如下：

(4)
(4 3 2 1 7 6 5 4)
(1 2 3 4)

2.61(p105)

(load "ordered-set.scm")

(define (adjoin-set x set)
    (cond ((null? set) (list x))
          ((< x (car set)) (cons x set))
          ((= x (car set)) set)
          ((> x (car set)) (cons (car set) (adjoin-set x (cdr set))))))

; test
(define set1 (list 1 3 4))
(define set2 '())
(display (adjoin-set 0 set1))
(newline)
(display (adjoin-set 2 set1))
(newline)
(display (adjoin-set 5 set1))
(newline)
(display (adjoin-set 1 set2))
(newline)
(exit)

结果如下：

(0 1 3 4)
(1 2 3 4)
(1 3 4 5)
(1)

2.62(p105)

(load "ordered-set.scm")

(define (union-set set1 set2)
    (cond ((null? set1) set2)
          ((null? set2) set1)
          ((let ((x1 (car set1))
                 (x2 (car set2)))
                (cond ((= x1 x2) (cons x1 (union-set (cdr set1) (cdr set2))))
                      ((< x1 x2) (cons x1 (union-set (cdr set1) set2)))
                      ((> x1 x2) (cons x2 (union-set set1 (cdr set2)))))))))

; test
(define set1 (list 1 2 3 4))
(define set2 (list 4 5 6 7))
(define set3 '())
(display (union-set set1 set2))
(newline)
(display (union-set set1 set3))
(exit)

结果如下：

(1 2 3 4 5 6 7)
(1 2 3 4)

2.63(p108)

(a)

一样，都是集合中元素从大到小的排列。

(b)

tree->list-1：

append的时间复杂度为$\Theta(n+m)$，递推关系为

$$T(n)= T(i) +T(n - 1-i) +\Theta(n)$$

所以时间复杂度为

$$O(n^2)$$

tree->list-2：

递推关系为

$$T(n)= T(i) +T(n - 1-i) +\Theta(1)$$

所以时间复杂度为

$$O(n)$$

代码如下：

(load "helper.scm")

(define (tree->list-1 tree)
  (if (null? tree)
      '()
      (append (tree->list-1 (left-branch tree))
              (cons (entry tree)
                    (tree->list-1 (right-branch tree))))))

(define (tree->list-2 tree)
  (define (copy-to-list tree result-list)
    (if (null? tree)
        result-list
        (copy-to-list (left-branch tree)
                      (cons (entry tree)
                            (copy-to-list (right-branch tree)
                                          result-list)))))
  (copy-to-list tree '()))

; test
(define a (make-tree 7
            (make-tree 3
                (make-tree 1 '() '())
                (make-tree 5 '() '()))
            (make-tree 9
                '()
                (make-tree 11 '() '()))))

(define b (make-tree 3
            (make-tree 1 '() '())
            (make-tree 7
                (make-tree 5 '() '())
                (make-tree 9
                    '()
                    (make-tree 11 '() '())))))

(define c (make-tree 5
            (make-tree 3
                (make-tree 1 '() '())
                '())
            (make-tree 9
                (make-tree 7 '() '())
                (make-tree 11 '() '()))))

; test
(display (tree->list-1 a))
(newline)
(display (tree->list-2 a))
(newline)
(display (tree->list-1 b))
(newline)
(display (tree->list-2 b))
(newline)
(display (tree->list-1 c))
(newline)
(display (tree->list-2 c))
(newline)
(exit)

结果如下：

(1 3 5 7 9 11)
(1 3 5 7 9 11)
(1 3 5 7 9 11)
(1 3 5 7 9 11)
(1 3 5 7 9 11)
(1 3 5 7 9 11)

2.64(p108)

(a)

左右两棵子树的元素数量之差小于等于$1$，首先递归的产生左右子树（平衡二叉树），然后再拼接成当前的平衡二叉树。

(b)

时间复杂度：

partial-tree:

$$\begin{aligned} T(n)&=2T\left(\frac n 2\right) +\Theta(1)\\ T(n)&=\Theta(n) \end{aligned}$$

list->tree调用了partial-tree, length，所以时间复杂度为$\Theta(n)$。

2.65(p108)

代码如下：

(load "helper.scm")

(define (intersection-set set1 set2)
    (define (intersection-set-iter a1 a2 res)
        (cond ((null? a1) res)
              ((null? a2) res)
              (else (let ((x1 (car a1))
                          (x2 (car a2)))
                    (cond ((> x1 x2) (intersection-set-iter a1 (cdr a2) res))
                          ((< x1 x2) (intersection-set-iter (cdr a1) a2 res))
                          (else (intersection-set-iter (cdr a1) (cdr a2) (cons x1 res))))))))
    (list->tree (reverse (intersection-set-iter (tree->list set1) (tree->list set2) '()))))

(define (union-set set1 set2)
    (define (union-set-iter a1 a2 res)
        (cond ((null? a1) (append (reverse a2) res))
              ((null? a2) (append (reverse a1) res))
              (else (let ((x1 (car a1))
                          (x2 (car a2)))
                    (cond ((> x1 x2) (union-set-iter a1 (cdr a2) (cons x2 res)))
                          ((< x1 x2) (union-set-iter (cdr a1) a2 (cons x1 res)))
                          (else (union-set-iter (cdr a1) (cdr a2) (cons x1 res))))))))
    (list->tree (reverse (union-set-iter (tree->list set1) (tree->list set2) '()))))

; test
(define set1 (list->tree (list 1 2 3 4)))
(define set2 (list->tree (list 4 5 6 7)))
(define set3 (list->tree '()))
(display (tree->list (intersection-set set1 set2)))
(newline)
(display (tree->list (intersection-set set1 set3)))
(newline)
(display (tree->list (union-set set1 set2)))
(newline)
(display (tree->list (union-set set1 set3)))
(exit)

结果如下：

(4)
()
(1 2 3 4 5 6 7)
(1 2 3 4)

时间复杂度分析：

两个集合长度每次至少减少$1$，所以时间复杂度为$\Theta(n)$。

2.66(p127)

(load "helper.scm")

(define (lookup given-key set-of-records)
    (cond ((null? set-of-records) false)
          ((equal? given-key (key (car set-of-records)))
            (car set-of-records))
          ((< given-key (key (car set-of-records)))
            (lookup given-key (left-branch set-of-records)))
          (else (lookup given-key (right-branch set-of-records)))))

2.67(p114)

编码：

A: 0
B: 10
C: 111
D: 110

代码如下：

(load "huffman.scm")

(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)))))

(define sample-message '(0 1 1 0 0 1 0 1 0 1 1 1 0))

; test
(display sample-tree)
(newline)
(display (decode sample-message sample-tree))
(exit)

结果如下：

((leaf A 4) ((leaf B 2) ((leaf D 1) (leaf C 1) (D C) 2) (B D C) 4) (A B D C) 8)
(A D A B B C A)

2.68(p114)

(load "huffman.scm")

(define (element-of-list element l)
    (cond ((null? l) #f)
          ((equal? (car l) element) #t)
          (else (element-of-list element (cdr l)))))

(define (encode-symbol symbol tree)
    (define (encode-symbol-iter symbol tree res)
        (let ((tree-symbols (symbols tree))
              (left (left-branch tree))
              (right (right-branch tree)))
            (if (element-of-list symbol tree-symbols)
                ; 叶节点
                (cond ((null? (cdr tree-symbols)) res)
                      ((element-of-list symbol left) (encode-symbol-iter symbol left (cons '0 res)))
                      (else (encode-symbol-iter symbol right (cons '1 res))))
                ((error "bad symbol" symbol)))))
    (reverse (encode-symbol-iter symbol tree '())))

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

; test
(define message '(A D A B B C A))

(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)))))

; test
(display (encode message sample-tree))
(exit)

结果如下：

(0 1 1 0 0 1 0 1 0 1 1 1 0)

2.69(p114)

(load "huffman.scm")

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

(define (successive-merge leaf-set)
    (define (successive-merge-iter set tree)
        (if (null? set)
            tree
            (successive-merge-iter 
                (cdr set)
                (make-code-tree (car set)
                                tree))))
    (successive-merge-iter (cdr leaf-set) (car leaf-set)))

; test
(define pairs '((A 4) (B 2) (D 1) (C 1)))
(define leaf-set (make-leaf-set pairs))
(display (generate-huffman-tree pairs))
(exit)

结果如下：

((leaf A 4) ((leaf B 2) ((leaf D 1) (leaf C 1) (D C) 2) (B D C) 4) (A B D C) 8)

2.70(p114)

(load "huffman.scm")

; test
(define pairs '((A 2) (NA 16) (BOOM 1) (SHA 3)
                (GET 2) (YIP 9) (JOB 2) (WAH 1)))
(define tree (generate-huffman-tree pairs))
(define t1 '(GET A JOB))
(define t2 '(SHA NA NA NA NA NA NA NA NA))
(define t3 '(WAH YIP YIP YIP YIP YIP YIP YIP YIP YIP))
(define t4 '(SHA BOOM))
(define c1 (encode t1 tree))
(define c2 (encode t2 tree))
(define c3 (encode t3 tree))
(define c4 (encode t4 tree))
(display c1)
(newline)
(display c2)
(newline)
(display c3)
(newline)
(display c4)
(newline)
(display (+ (* 2 (length c1)) (* 2 (length c2)) (length c3) (length c4)))
(newline)
(display (* 3 (+ (* 2 (length t1)) (* 2 (length t2)) (length t3) (length t4))))
(newline)
(exit)

结果如下：

(1 1 1 1 0 1 1 1 0 1 1 1 1 1 0)
(1 1 0 0 0 0 0 0 0 0 0)
(1 1 1 1 1 1 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0)
(1 1 0 1 1 1 1 1 1 0)
87
108

• huffman编码需要87个二进制位
• 定长编码需要108个二进制位

2.71(p115)

形成树的过程：

$$\begin{aligned} 0&:1,2,4,\ldots, 2^{n-1}\\ 1&: 2^2-1,4,\ldots, 2^{n-1}\\ \ldots\\ i&: 2^{i+1} -1, 2^{i+1},\ldots, 2^{n-1}\\ n-2&:2^{n-1} -1,2^{n-1}\\ n-1&:2^{n}-1 \end{aligned}$$

最频繁：$1$个二进制位。

最不频繁：$n-1$个二进制位。

2.72(p115)

时间复杂度：

• (element-of-list symbol tree-symbols): $\Theta(i),i=n,n-1,\ldots, 1$

所以：

• 最频繁：$\Theta(n)$。
• 最不频繁：$\Theta\left(\sum_{i=1}^n i \right)=\Theta\left(n^2 \right)$。