379 阿裏雲技術社區[雲棲]

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)))
#f
> (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)
        (else
          (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))))
        (else
           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)))
    (if (null? (cdr rest))
        (car rest)
        (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))
        (else
         (list a1 '+ a2))))
(define (product? x)
  (let ((op (cadr 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))
        (else
          (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)
        (else
          (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)保留下來，繼續往下找：

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

習題2.62，與求交集類似：

(define (union-set set1 set2)
  (cond ((null? set1) set2)
        ((null? set2) set1)
        (else
         (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)))))))))

測試下：

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

  (if (= 1 (length set))

(car set)

(successive-merge 

(adjoin-set (make-code-tree (car set) (cadr set)) (cddr 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

最後更新：2017-05-17 15:31:17

sicp 2.3小結習題嚐試解答

上一篇： PHP異步的玩法

下一篇： vi常用命令

相關內容

熱門內容

最新內容