SICP读书笔记2.3 | Senghoo Kim

练习2.53

#;1359> (list 'a 'b 'c)
(a b c)
#;1400> (list (list 'george))
((george))
#;1451> (cdr '((x1 x2) (y1 y2)))
((y1 y2))
#;1501> (cadr '((x1 x2) (y1 y2)))
(y1 y2)
#;1559> (pair? (car '(a short list)))
#f
#;1606> (memq 'red '((red shose) (blue socks)))
#f
#;1698> (memq 'red '(red shoes blue socks))
(red shoes blue socks)

练习2.54

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

练习2.55

对一个表达式取引号其实是 (quote sth) 的语法糖

所以题目中描述的表达式相当于

(car (quote (quote abracadabra)))

所以得出结果为quote

练习2.56

实现相关函数

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

(define (base s) (cadr s))
(define (exponent s) (caddr s))

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

添加相关代码到`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 (deriv (multiplier exp) var)
                        (multiplicand exp))))
        ((exponentiation? exp)
         (make-product (make-product (exponent exp)
                                     (make-exponentiation (base exp) (make-sum (exponent exp) -1)))
                       (deriv (base exp) var)))
        (else
         (error "unknown expression type: DERIV" exp))))

练习2.57

添加这个新特性，只需要改动make-product函数。

为了与以前的代码兼容，新的乘法以(* m1 (* m2 (* m3 m4))) 这类方式表示。

为了得到最简单形态需要：

首先从参数里选择所有数字相乘简化这些数字。
如果简化得到的数字是0，直接返回数字0
如果简化得到的数字是1，返回其他部分组成的结果
如果简化得到其他结果，返回其他部分乘以简化的到数字的结果

(define (make-product . args)
  (define (inner args)
    (if (null? (cdr args))
        (car args)
        (list '* (car args) (inner (cdr args)))))
  (let ((n (reduce * 1 (filter number? args)))
        (exps (filter (lambda (x) (not (number? x))) args)))
    (cond ((= 0 n) 0)
          ((= 1 n) (inner exps))
          (else (list '* n (inner exps))))))

练习2.58

只需要修改 make-sum,addend,augend,sum?,make-product,multiplier,multiplicand,product?这些与内部表达相关的代码就可以表示为中缀表达式。
同理修改上述函数即可实现。

练习2.59

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

练习2.60

只需要修改adjoin-set函数即可满足新的表示方式

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

允许重复的表示方式相对于不允许重复的表示方式在插入数据时速度更快（不需要遍历查找是否存在）但是更费存储空间以及其他操作的速度更慢。

在涉及大量插入，极少涉及其他操作以及空间不敏感的场合可以使用可以重复的表示方式，其他场合使用不允许重复的表示方式。

练习2.61

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

同element-of-set? 最坏情况下，也就是要添加的是最大元素的情况需要O(n)的复杂度。但是平均情况下只需要遍历到一半即可插入数据。

练习2.62

(define (union-set set1 set2)
  (cond ((null? set1) set2)
        ((null? set2) set1)
        ((= (car set1) (car set2))
         (cons (car set1) (union-set (cdr set1) (cdr set2))))
        ((< (car set1) (car set2))
         (cons (car set1) (union-set (cdr set1) set2)))
        (else (cons (car set2) (union-set set1 (cdr set2))))))

练习2.63

两者执行结果一致
tree->list-1 的复杂度为 $O(n^2)$ tree->list-2的复杂度为 $O(n)$

练习2.64

partial-tree每次将以排序的列表分成两半，并分别当作左右分支从而达到生成平衡树的目的。

partial-tree对列表中每个元素都会执行make-tree所以复杂度为 $O(n)$

练习2.65

主要思路为先转换为排序的表，再进行操作然后再把表转换成平衡树。

练习2.66

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

练习2.67

(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))
(decode sample-message sample-tree)
(A D A B B C A)

练习2.68

(define (encode-symbol symbol tree)
  (cond ((leaf? tree) '())
        ((memq symbol (symbols (left-branch tree)))
         (cons 0 (encode-symbol symbol (left-branch tree))))
        ((memq symbol (symbols (right-branch tree)))
         (cons 1 (encode-symbol symbol (right-branch tree))))
        (else (error "bad symbol: " symbol))))

练习2.69

关键在于使用adjoin-set 组织起所有节点，每次取前两个节点（权重最小的两个）进行合并，直到集合里只剩下一个节点(根)。

(define (successive-merge ordered-set)
  (cond ((= 0 (length ordered-set))
         '())
        ((= 1 (length ordered-set))
         (car ordered-set))
        (else
         (let ((new-sub-tree (make-code-tree (car ordered-set)
                                             (cadr ordered-set)))
               (remained-ordered-set (cddr ordered-set)))
           (successive-merge (adjoin-set new-sub-tree remained-ordered-set))))))

练习2.70

经过huffman 编码后的消息长度为84位。

如果使用定长编码，因为符号表中有8个符号，所以3位即可表示一个符号，消息中一共有36个符号，所以编码后的长度为：

$3 * 36 = 108$

练习2.71

最频繁的符号使用1位，最不频繁的符号使用n-1位

练习2.72

对于最频繁的情况下，编码只需要查找左边的树即找到相应符号，所以复杂度是: $O(1)$

对于最不频繁的情况下，编码过程需要下降n-1次，每次查找n,n-1,n-2…1个项目，所以复杂度为 $O(n^2)$