Chinaunix

标题: SICP 习题参考答案 2.3 [打印本页]

---

作者: win_hate    时间: 2008-10-05 10:37
标题: SICP 习题参考答案 2.3

此帖为 SICP 章节 2.3 的参考答案。为保持可读性，请勿直接在本帖讨论。讨论请另开新帖。

• 本节电子版：[Symbolic Data]
  
• 答案目录：[点这里]
  
  

---

作者: win_hate    时间: 2008-10-05 10:38
标题: Exercise 2.53.
Exercise 2.53.  What would the interpreter print in response to evaluating each of the following expressions?

(list 'a 'b 'c)

(list (list 'george))
(cdr '((x1 x2) (y1 y2)))

(cadr '((x1 x2) (y1 y2)))
(pair? (car '(a short list)))
(memq 'red '((red shoes) (blue socks)))

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

---

作者: win_hate    时间: 2008-10-05 10:44
标题: Exercise 2.53. 答案

1. 
   
2. > (list 'a 'b 'c)
   
3. (a b c)
   
4. 
   
5. > (list (list 'george))
   
6. ((george))
   
7. 
   
8. > (cdr '((x1 x2) (y1 y2)))
   
9. ((y1 y2))
   
10. 
    
11. > (cadr '((x1 x2) (y1 y2)))
    
12. (y1 y2)
    
13. 
    
14. > (pair? (car '(a short list)))
    
15. #f
    
16. 
    
17. > (memq 'red '((red shoes) (blue socks)))
    
18. #f
    
19. 
    
20. > (memq 'red '(red shoes blue socks))
    
21. (red shoes blue socks)
    

复制代码

---

作者: win_hate    时间: 2008-10-05 10:45
标题: Exercise 2.54.
Exercise 2.54.  Two lists are said to be equal? if they contain equal elements arranged in the same order. For example,

(equal? '(this is a list) '(this is a list))

is true, but

(equal? '(this is a list) '(this (is a) list))

is false. To be more precise, we can define equal? recursively in terms of the basic eq? equality of symbols by saying that a and b are equal? if they are both symbols and the symbols are eq?, or if they are both lists such that (car a) is equal? to (car b) and (cdr a) is equal? to (cdr b). Using this idea, implement equal? as a procedure.

---

作者: win_hate    时间: 2008-10-05 11:01
标题: Exercise 2.54. 答案

1. 
   
2. (define (Equal? a b)
   
3.   (if (and (pair? a) (pair? b))
   
4.       (and (Equal? (car a) (car b))
   
5.            (Equal? (cdr a) (cdr b)))
   
6.       (eq? a b)))
   

复制代码

[ 本帖最后由 win_hate 于 2008-10-5 11:03 编辑 ]

---

作者: win_hate    时间: 2008-10-05 11:03
标题: Exercise 2.55.
Exercise 2.55.  Eva Lu Ator types to the interpreter the expression

(car ''abracadabra)

To her surprise, the interpreter prints back quote. Explain.

[ 本帖最后由 win_hate 于 2008-10-5 11:08 编辑 ]

---

作者: win_hate    时间: 2008-10-05 11:05
标题: Exercise 2.55. 答案
这是因为 'x 是个缩写，等价于 (quote x)。所以 ''abracadabra 是 (quote (quote abracadabra)).

---

作者: win_hate    时间: 2008-10-22 10:23
标题: Exercise 2.56.
Exercise 2.56.  Show how to extend the basic differentiator to handle more kinds of expressions. For instance, implement the differentiation rule



by adding a new clause to the deriv program and defining appropriate procedures exponentiation?, base, exponent, and make-exponentiation. (You may use the symbol ** to denote exponentiation.) Build in the rules that anything raised to the power 0 is 1 and anything raised to the power 1 is the thing itself.

---

作者: win_hate    时间: 2008-10-22 10:29
标题: Exercis2 2.56. 答案

1. 
   
2. (define (exponentiation? exp)
   
3.   (and (pair? exp) (eq? (car exp) '**)))
   
4. 
   
5. (define base cadr)
   
6. (define exponent caddr)
   
7. 
   
8. (define (make-exponentiation b e)
   
9.     (cond ((=number? e 0) 1)
   
10.         ((=number? b 1) 1)
    
11.         ((and (number? b) (number? e)) (expt b e))
    
12.         (else (list '** b e))))
    

复制代码

1. 
   
2. (define (deriv exp var)
   
3.   (cond ((number? exp) 0)
   
4.         ((variable? exp)
   
5.          (if (same-variable? exp var) 1 0))
   
6.         ((sum? exp)
   
7.          (make-sum (deriv (addend exp) var)
   
8.                    (deriv (augend exp) var)))
   
9.         ((product? exp)
   
10.          (make-sum
    
11.           (make-product (multiplier exp)
    
12.                         (deriv (multiplicand exp) var))
    
13.           (make-product (deriv (multiplier exp) var)
    
14.                         (multiplicand exp))))
    
15.         ((exponentiation? exp)
    
16.          (make-product
    
17.           (make-product
    
18.            (exponent exp)
    
19.            (make-exponentiation (base exp)
    
20.                                 (- (exponent exp) 1)))
    
21.           (deriv (base exp) var)))
    
22.          (else
    
23.           (error "unknown expression type -- DERIV" exp))))
    

复制代码

1. 
   
2. > (deriv '(** x 1) 'x)
   
3. 1
   
4. > (deriv '(** x 10) 'x)
   
5. (* 10 (** x 9))
   
6. > (deriv (make-exponentiation 'x 0) 'x)
   
7. 0
   

复制代码

---

作者: win_hate    时间: 2008-10-28 17:49
标题: Exercise 2.57.
Exercise 2.57.  Extend the differentiation program to handle sums and products of arbitrary numbers of (two or more) terms. Then the last example above could be expressed as

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

Try to do this by changing only the representation for sums and products, without changing the deriv procedure at all. For example, the addend of a sum would be the first term, and the augend would be the sum of the rest of the terms.

---

作者: win_hate    时间: 2008-10-28 17:52
标题: Exercise 2.57. 答案
只要把两个选择函数略为修改就可以了：

1. 
   
2. (define (augend s)
   
3.   (let ((rest (cddr s)))
   
4.     (if (null? (cdr rest))
   
5.         (car rest)
   
6.         (cons '+ rest))))
   
7. 
   
8. (define (multiplicand p)
   
9.   (let ((rest (cddr p)))
   
10.     (if (null? (cdr rest))
    
11.         (car rest)
    
12.         (cons '* rest))))
    

复制代码

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

复制代码

前缀表达式不是很好看。对比一下 maxima 的微分

1. 
   
2. (%i1) diff(x*y*(x+3), x);
   
3. (%o1)                           (x + 3) y + x y
   

复制代码

[ 本帖最后由 win_hate 于 2008-10-29 10:15 编辑 ]

---

作者: win_hate    时间: 2008-10-29 09:36
标题: Exercise 2.58.
Exercise 2.58.  Suppose we want to modify the differentiation program so that it works with ordinary mathematical notation, in which + and * are infix rather than prefix operators. Since the differentiation program is defined in terms of abstract data, we can modify it to work with different representations of expressions solely by changing the predicates, selectors, and constructors that define the representation of the algebraic expressions on which the differentiator is to operate.

a. Show how to do this in order to differentiate algebraic expressions presented in infix form, such as (x + (3 * (x + (y + 2)))). To simplify the task, assume that + and * always take two arguments and that expressions are fully parenthesized.

b. The problem becomes substantially harder if we allow standard algebraic notation, such as (x + 3 * (x + y + 2)), which drops unnecessary parentheses and assumes that multiplication is done before addition. Can you design appropriate predicates, selectors, and constructors for this notation such that our derivative program still works?

---

作者: win_hate    时间: 2008-10-29 09:44
标题: Exercise 2.58. 答案
把 a, b 一起做了。

• 这个题目并没有看上去那么难。因为只有两种运算，而且 scheme 天生具有处理括号的能力，所以不用考虑括号平衡的问题。
  
• 为了去除多余的括号，比如 (x), ((x+y))，加进了一个 strip 函数
  
• 为了 make-product 和 make-sum 不产生多余的括号，相应的代码有点胖
  
• 满足了题目 “只修改建构函数和选择函数，不改动 deriv" 的要求。
  

1. 
   
2. (define (strip exp)
   
3.   (if (and (list? exp) (null? (cdr exp)))
   
4.       (strip (car exp))
   
5.       exp))
   
6. 
   
7. (define (sum? s)
   
8.   (member '+ s))
   
9. 
   
10. (define (addend s)
    
11.   (define (f ini xs)
    
12.     (let ((x (car xs)))
    
13.       (if (eq? x '+)
    
14.           ini
    
15.           (f (append ini (list x)) (cdr xs)))))
    
16.   (strip (f '() s)))
    
17.   
    
18. (define (augend s)
    
19.   (strip (cdr (member '+ s))))
    
20. 
    
21. (define (product? s)
    
22.   (and (member '* s) (not (member '+ s))))
    
23. 
    
24. (define (multiplier p)
    
25.   (strip (car p)))
    
26. 
    
27. (define (multiplicand p)
    
28.   (strip (cddr p)))
    
29. 
    
30. (define (make-sum a1 a2)
    
31.   (cond ((=number? a1 0) (strip a2))
    
32.         ((=number? a2 0) (strip a1))
    
33.         ((and (number? a1) (number? a2)) (+ a1 a2))
    
34.         (else (let ((A1 (if (list? a1) a1 (list a1)))
    
35.                     (A2 (if (list? a2) a2 (list a2))))
    
36.                 (append A1 (cons '+ A2))))))
    
37. 
    
38. (define (make-product m1 m2)
    
39.   (cond ((or (=number? m1 0) (=number? m2 0)) 0)
    
40.         ((=number? m1 1) (strip m2))
    
41.         ((=number? m2 1) (strip m1))
    
42.         ((and (number? m1) (number? m2)) (* m1 m2))
    
43.         (else (let ((M1 (if (list? m1)
    
44.                             (if (sum? m1) (list m1) m1)
    
45.                             (list m1)))
    
46.                     (M2 (if (list? m2)
    
47.                             (if (sum? m2) (list m2) m2)
    
48.                             (list m2))))
    
49.                 (append M1 (cons '* M2))))))
    

复制代码

演示：

1. 
   
2. > (deriv '(x + 3) 'x)
   
3. 1
   
4. 
   
5. > (deriv '(x * y) 'x)
   
6. y
   
7. 
   
8. > (deriv '( x * y * ( x + 3)) 'x)
   
9. (x * y + y * (x + 3))
   
10. 
    
11. > (deriv '(x + (3 * (x + (y + 2)))) 'x)
    
12. 4
    
13. 
    
14. > (deriv '(x + 3 * (x + y + 2)) 'x)
    
15. 4
    

复制代码

[ 本帖最后由 win_hate 于 2008-10-29 09:52 编辑 ]

---

作者: win_hate    时间: 2008-10-30 23:14
标题: Exercise 2.59.
Exercise 2.59.  Implement the union-set operation for the unordered-list representation of sets.

---

作者: win_hate    时间: 2008-10-30 23:15
标题: Exercise 2.59. 答案

1. 
   
2. (define (union-set set1 set2)
   
3.   (if (null? set1) set2
   
4.       (union-set (cdr set1)
   
5.                 (adjoin-set (car set1) set2))))
   

复制代码

[ 本帖最后由 win_hate 于 2008-10-30 23:19 编辑 ]

---

作者: win_hate    时间: 2008-10-30 23:19
标题: Exercise 2.60.
Exercise 2.60.  We specified that a set would be represented as a list with no duplicates. Now suppose we allow duplicates. For instance, the set {1,2,3} could be represented as the list (2 3 2 1 3 2 2). Design procedures element-of-set?, adjoin-set, union-set, and intersection-set that operate on this representation. How does the efficiency of each compare with the corresponding procedure for the non-duplicate representation? Are there applications for which you would use this representation in preference to the non-duplicate one?

---

作者: win_hate    时间: 2008-10-30 23:24

1. 
   
2. (define (adjoin-set x set)
   
3.   (cons x set))
   
4. 
   
5. (define (union-set set1 set2)
   
6.   (append set1 set2))
   

复制代码

其它函数不变。adjoin 变成 O(1) 的了。 union-set 的效率与 set1 的长度成线性关系。作用在相同集合上时，其它函数效率不变。但由于构造出来的数据含有重复的元素，会引会引发数据膨胀。

[ 本帖最后由 win_hate 于 2008-10-30 23:29 编辑 ]

---

作者: win_hate    时间: 2008-10-31 09:42
标题: Exercise 2.61.
Exercise 2.61.  Give an implementation of adjoin-set using the ordered representation. By analogy with element-of-set? show how to take advantage of the ordering to produce a procedure that requires on the average about half as many steps as with the unordered representation.

---

作者: win_hate    时间: 2008-10-31 09:48

1. 
   
2. (define (adjoin-set x set)
   
3.   (if (null? set) (cons x '())
   
4.       (let ((y (car set)))
   
5.         (cond ((= x y) set)
   
6.               ((> x y) (cons y (adjoin-set x (cdr set))))
   
7.               (else (cons x set))))))
   

复制代码

书本上 “requires on the average about half as many steps” 疑有误。已排序的情况下，查找的次数是少了，但对插入元素的位置有要求。构造新表的开销比无需排序时大。

---

作者: win_hate    时间: 2008-10-31 09:50
标题: Exercise 2.62.
Exercise 2.62.  Give a (n) implementation of union-set for sets represented as ordered lists.

---

作者: win_hate    时间: 2008-10-31 09:51
标题: Exercise 2.62. 答案

1. 
   
2. (define (union-set set1 set2)
   
3.   (cond ((null? set1) set2)
   
4.         ((null? set2) set1)
   
5.         (else (let ((x1 (car set1)) (x2 (car set2))
   
6.                     (s1 (cdr set1)) (s2 (cdr set2)))
   
7.                 (cond ((= x1 x2) (cons x1 (union-set s1 s2)))
   
8.                       ((> x1 x2) (cons x2 (union-set set1 s2)))
   
9.                       (else (cons x1 (union-set s1 set2))))))))
   

复制代码

---

作者: win_hate    时间: 2008-11-02 10:14
标题: Exercise 2.63.
Exercise 2.63.  Each of the following two procedures converts a binary tree to a list.

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

a. Do the two procedures produce the same result for every tree? If not, how do the results differ? What lists do the two procedures produce for the trees in figure 2.16?

b. Do the two procedures have the same order of growth in the number of steps required to convert a balanced tree with n elements to a list? If not, which one grows more slowly?

---

作者: win_hate    时间: 2008-11-02 10:21
标题: Exercise 2.63. 答案

• a. 一样的，都是中序遍历一棵树；
• b. 第二个写法的复杂度为 O(n)，本质上是通过  cons 把一棵树的 n 个节点串成一个表。第一个写法在递归时使用了 append，所以会慢得多。cons 是个 O(1) 的操作，而 (append  L1 L2) 的复杂度为 O( |L1| ).
  
  设第一个写法的复杂度为 T(n)，有 T(n)=2 T(n/2) + n/2，可以算出，其复杂度为 O(n log n).
  

---

作者: win_hate    时间: 2008-11-04 21:35
标题: Exercise 2.64
Exercise 2.63.  Each of the following two procedures converts a binary tree to a list.

Exercise 2.64.  The following procedure list->tree converts an ordered list to a balanced binary tree. The helper procedure partial-tree takes as arguments an integer n and list of at least n elements and constructs a balanced tree containing the first n elements of the list. The result returned by partial-tree is a pair (formed with cons) whose car is the constructed tree and whose cdr is the list of elements not included in the tree.

(define (list->tree elements)
  (car (partial-tree elements (length elements))))

(define (partial-tree elts n)
  (if (= n 0)
      (cons '() elts)
      (let ((left-size (quotient (- n 1) 2)))
        (let ((left-result (partial-tree elts left-size)))
          (let ((left-tree (car left-result))
                (non-left-elts (cdr left-result))
                (right-size (- n (+ left-size 1))))
            (let ((this-entry (car non-left-elts))
                  (right-result (partial-tree (cdr non-left-elts)
                                              right-size)))
              (let ((right-tree (car right-result))
                    (remaining-elts (cdr right-result)))
                (cons (make-tree this-entry left-tree right-tree)
                      remaining-elts))))))))

a. Write a short paragraph explaining as clearly as you can how partial-tree works. Draw the tree produced by list->tree for the list (1 3 5 7 9 11).

b. What is the order of growth in the number of steps required by list->tree to convert a list of n elements?

[ 本帖最后由 win_hate 于 2008-11-6 22:41 编辑 ]

---

作者: win_hate    时间: 2008-11-04 21:39
标题: Exercise 2.64. 答案
a. 递归，先构造出左子树，提取当前节点，再构造出右子树.

对指定数据产生的树为 (5 (1 () 3) (9 7 11))

b. 把表遍历两次， O(n).

[ 本帖最后由 win_hate 于 2008-11-6 22:42 编辑 ]

---

作者: win_hate    时间: 2008-11-06 22:42
标题: Exercise 2.65.
Exercise 2.65.  Use the results of exercises 2.63 and  2.64 to give (n) implementations of union-set and intersection-set for sets implemented as (balanced) binary trees.

---

作者: win_hate    时间: 2008-11-06 22:46
标题: Exercise 2.65. 答案
tree->list-2 是 O(n) 的, list->tree 也是 O(n) 的， union-set 和 intersection-set 都是 O(n) 的。所以只要

• tree->list-2 变为排序表
• union-set, intersection-set
• list->tree 变为树
  

---

作者: win_hate    时间: 2008-11-12 10:49
标题: Exercise 2.66.
Exercise 2.66.  Implement the lookup procedure for the case where the set of records is structured as a binary tree, ordered by the numerical values of the keys.

---

作者: win_hate    时间: 2008-11-12 10:50
标题: Exercise 2.66.
<wait>

这题没有什么意思，以后再做。

---

作者: win_hate    时间: 2008-11-12 14:18
标题: Exercise 2.67.
Exercise 2.67.  Define an encoding tree and a sample message:

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

Use the decode procedure to decode the message, and give the result.


======================================================

参考资料

Huffman never tried to patent an invention from his work. Instead, he concentrated his efforts on education. In Huffman's own words, "My products are my students."

• Huffman 的生平见 [David A. Huffman]
  
• Huffman 编码见 [Huffman coding]
  

David A Huffman

1925 - 1999

美国

信息论、编码专家

[ 本帖最后由 win_hate 于 2008-11-14 21:18 编辑 ]

---

作者: win_hate    时间: 2008-11-12 14:19
标题: Exercise 2.67. 答案

1. 
   
2. guile> (decode sample-message sample-tree)
   
3. (A D A B B C A)
   

复制代码

---

作者: win_hate    时间: 2008-11-12 14:20
标题: Exercise 2.68.
Exercise 2.68.  The encode procedure takes as arguments a message and a tree and produces the list of bits that gives the encoded message.

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

Encode-symbol is a procedure, which you must write, that returns the list of bits that encodes a given symbol according to a given tree. You should design encode-symbol so that it signals an error if the symbol is not in the tree at all. Test your procedure by encoding the result you obtained in exercise 2.67 with the sample tree and seeing whether it is the same as the original sample message.

---

作者: win_hate    时间: 2008-11-12 14:21
标题: Exercise 2.68. 答案

1. 
   
2. (define (encode-symbol symb tree)
   
3.   (cond ((leaf? tree) (if (eq? symb (symbol-leaf tree)) '()
   
4.                           (error "bat symbol -- ENCODE-SYMBOL" symb)))
   
5.         ((member symb (symbols (left-branch tree)))
   
6.          (cons 0 (encode-symbol symb (left-branch tree))))
   
7.         (else (cons 1 (encode-symbol symb (right-branch tree))))))
   

复制代码

1. 
   
2. guile> (decode sample-message sample-tree)
   
3. (A D A B B C A)
   
4. guile> (encode '(A D A B B C A) sample-tree)
   
5. (0 1 1 0 0 1 0 1 0 1 1 1 0)
   
6. guile> sample-message
   
7. (0 1 1 0 0 1 0 1 0 1 1 1 0)
   

复制代码

---

作者: win_hate    时间: 2008-12-03 17:38
标题: Exercise 2.69.
Exercise 2.69.  The following procedure takes as its argument a list of symbol-frequency pairs (where no symbol appears in more than one pair) and generates a Huffman encoding tree according to the Huffman algorithm.

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

Make-leaf-set is the procedure given above that transforms the list of pairs into an ordered set of leaves. Successive-merge is the procedure you must write, using make-code-tree to successively merge the smallest-weight elements of the set until there is only one element left, which is the desired Huffman tree. (This procedure is slightly tricky, but not really complicated. If you find yourself designing a complex procedure, then you are almost certainly doing something wrong. You can take significant advantage of the fact that we are using an ordered set representation.)

---

作者: win_hate    时间: 2008-12-03 17:39
标题: Exercise 2.69. 答案

1. 
   
2. (define (generate-huffman-tree pairs)
   
3.   (successive-merge (make-leaf-set pairs)))
   
4. 
   
5. (define (successive-merge leaf-set)
   
6.   (let ((fst (car leaf-set))
   
7.         (rst (cdr leaf-set)))
   
8.     (if (null? rst) fst
   
9.         (let* ((snd (car rst))
   
10.               (new (make-code-tree fst snd)))
    
11.           (successive-merge (adjoin-set new (cdr rst)))))))
    

复制代码

---

作者: win_hate    时间: 2008-12-03 17:40
标题: Exercise 2.70.
Exercise 2.70.  The following eight-symbol alphabet with associated relative frequencies was designed to efficiently encode the lyrics of 1950s rock songs. (Note that the ``symbols'' of an ``alphabet'' need not be individual letters.)

A         2         NA         16
BOOM         1         SHA         3
GET         2         YIP         9
JOB         2         WAH         1
Use generate-huffman-tree (exercise 2.69) to generate a corresponding Huffman tree, and use encode (exercise 2.68) to encode the following message:

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

How many bits are required for the encoding? What is the smallest number of bits that would be needed to encode this song if we used a fixed-length code for the eight-symbol alphabet?

[ 本帖最后由 win_hate 于 2008-12-3 18:00 编辑 ]

---

作者: win_hate    时间: 2008-12-03 17:45
标题: Exercise 2.70. 答案

1. 
   
2. (define L '((A 2) (NA 16)
   
3.             (BOOM 1) (SHA 3)
   
4.             (GET 2) (YIP 9)
   
5.             (JOB 2) (WAH 1)))
   
6. 
   
7. (define SONG-TREE (generate-huffman-tree L))
   
8. 
   
9. (define SONG '(GET A JOB
   
10.                SHA NA NA NA NA NA NA NA NA
    
11.                GET A JOB   
    
12.                SHA NA NA NA NA NA NA NA NA
    
13.                WAH YIP YIP YIP YIP YIP YIP YIP YIP YIP
    
14.                SHA BOOM))
    

复制代码

1. 
   
2. guile> (encode SONG SONG-TREE)
   
3. (1 1 1 1 1 1 1 0 0 1 1 1 1 0 1 1 1 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 0 0 1 1 1 1 0 1 1 1 0 0 0 0 0 0 0 0 0 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 1 0 1 1 0 1 1)
   
4. guile> (length (encode SONG SONG-TREE))
   
5. 84
   

复制代码

如果用定长码，需要 36*([log_2 6]+1)=108 个比特。

---

作者: win_hate    时间: 2008-12-04 11:01
标题: Exercise 2.71.
Exercise 2.71.  Suppose we have a Huffman tree for an alphabet of n symbols, and that the relative frequencies of the symbols are 1, 2, 4, ..., 2^{n-1}. Sketch the tree for n=5; for n=10. In such a tree (for general n) how may bits are required to encode the most frequent symbol? the least frequent symbol?

---

作者: win_hate    时间: 2008-12-04 11:14

• 5 个的
  
  
• 10 个的
  
  

树长成这样，是因为 1+2+...+ 2^i < 2^{i+1}

[ 本帖最后由 win_hate 于 2008-12-4 15:30 编辑 ]

---

作者: win_hate    时间: 2008-12-04 11:26
Exercise 2.72.  Consider the encoding procedure that you designed in exercise 2.68. What is the order of growth in the number of steps needed to encode a symbol? Be sure to include the number of steps needed to search the symbol list at each node encountered. To answer this question in general is difficult. Consider the special case where the relative frequencies of the n symbols are as described in exercise 2.71, and give the order of growth (as a function of n) of the number of steps needed to encode the most frequent and least frequent symbols in the alphabet.

---

作者: win_hate    时间: 2008-12-04 11:29
最常用的符号显然是 O(n)

最不常用的符号在最底下。每向下一层要搜索一个长度以 n 为界的列表。复杂度为 n*O(n) ，即 O(n^2).

---

作者: win_hate    时间: 2008-12-04 11:48
本节完。

---

欢迎光临 Chinaunix (http://bbs.chinaunix.net/)

Powered by Discuz! X3.2