SICP 习题参考答案 3.3

win_hate

造成计数混乱的原因是数据中有共享部分，这些共享部分被重复计算。

1. 
   
2. (define s3 (cons (cons 1 2) (cons 3 4)))
   
3. 
   
4. (define a (cons 2 3))
   
5. (define b (cons a a))
   
6. (define s4 (cons 1 b))
   
7. (define s7 (cons b b))
   

复制代码

测试

1. 
   
2. > (load "3.16.scm")
   
3. 
   
4. > (count-pairs s3)
   
5. 3
   
6. 
   
7. > (count-pairs s4)
   
8. 4
   
9. 
   
10. > (count-pairs s7)
    
11. 7
    

复制代码

win_hate

Exercise 3.17.  Devise a correct version of the count-pairs procedure of exercise 3.16 that returns the number of distinct pairs in any structure. (Hint: Traverse the structure, maintaining an auxiliary data structure that is used to keep track of which pairs have already been counted.)

win_hate

最直接的想法是记住已经访问过的部分。可以把已经访问过的节点（地址）存放在一个 hash 表内。

1. 
   
2. (define (count-pairs x)
   
3.   (let ((table (make-hash-table)))
   
4.     (define (f x)
   
5.       (cond ((not (pair? x)) 0)
   
6.             ((hashq-ref table x) 0)
   
7.             (else  (hashq-set! table x #t)
   
8.                    (+ (f (car x)) (f (cdr x)) 1))))
   
9.     (f x)))
   

复制代码

这里的 make-hash-table 是 guile 里提供的. 哈希表不是 scheme 的标准组成部分，所以不同的 shceme 中的 hash 接口并不一致。

测试

1. 
   
2. > (load "3.16.scm")
   
3. > (load "3.17.scm")
   
4. 
   
5. > (count-pairs s3)
   
6. 3
   
7. 
   
8. > (count-pairs s4)
   
9. 3
   
10. 
    
11. > (count-pairs s7)
    
12. 3
    

复制代码

如果用 3.13 中的 make-cycle 生成一个循环列表，则 3.16 中的 count-pairs 不会返回，而这里的 count-pairs 能返回。

1. 
   
2. > (define x (make-cycle (list 1 2 3 4 5 6 7)))
   
3. 
   
4. > (count-pairs x)
   
5. 7
   
6. 
   
7. > (define y (make-cycle (list 1 1 1 1 1 1 1)))
   
8. 
   
9. > (count-pairs x)
   
10. 7
    

复制代码

[ 本帖最后由 win_hate 于 2008-12-14 12:42 编辑 ]

win_hate

Exercise 3.18.  Write a procedure that examines a list and determines whether it contains a cycle, that is, whether a program that tried to find the end of the list by taking successive cdrs would go into an infinite loop. Exercise 3.13 constructed such lists.

win_hate

跟上一题类似的思路

1. 
   
2. (define (check-cycle xs)
   
3.   (let ((table (make-hash-table)))
   
4.     (define (f ys)
   
5.       (cond ((null? ys) '#f)
   
6.             ((hashq-ref table ys) '#t)
   
7.             (else (hashq-set! table ys #t)
   
8.                   (f (cdr ys)))))
   
9.     (f xs)))
   

复制代码

测试

1. 
   
2. > (load "3.13.scm")
   
3. > (load "3.18.scm")
   
4. 
   
5. > (define x (make-cycle (list 1 2 3 4 5 6 7)))
   
6. > (check-cycle x)
   
7. #t
   
8. 
   
9. > (define y (make-cycle (list 1 1 1 1 1 1 1)))
   
10. > (check-cycle y)
    
11. #t
    
12. 
    
13. > (define z (list 1 2 3 4 5 6 7))
    
14. > (check-cycle z)
    
15. #f
    

复制代码

[ 本帖最后由 win_hate 于 2008-12-14 12:46 编辑 ]

win_hate

Exercise 3.19.  Redo exercise 3.18 using an algorithm that takes only a constant amount of space. (This requires a very clever idea.)

win_hate

1. 
   
2. (define (check-cycle xs)
   
3.   (define (f s1 s2)
   
4.     (cond ((null? s2) #f)
   
5.           ((eq? s1 s2) #t)
   
6.           ((null? (cdr s2)) #f)
   
7.           (else (f (cdr s1) (cddr s2)))))
   
8.            
   
9.   (cond ((null? xs) #f)
   
10.         ((null? (cdr xs)) #f)
    
11.         (else (f xs (cddr xs)))))
    

复制代码

解释：

• 从列表 X 的第一个节点起编号，记为 X(0), X(1), X(2) .... 如果 X 中含有一个环，则 X(n) 的下标 n 可无限增大。
  
• 可以用 eq? 来判断 X(i), X(j) 是否同一个节点。
  
• 具体做法为：选取 {X(i)} 的一个子列 {X(2i)}，不断地用 eq? 比较 X(i) 与 X(2i)。如果子列 X(2i) 在前移中碰到表尾(NIL)，则表明没有环。如果 X(2i) 没碰到表尾，发现某个 i 使 X(i) 与 X(2i) 是同一个点，则表明有环。在有环的情形下，X(2i) 永远不会碰到表尾。
  
• 这个算法一定能发现环。
  
  设有环且环的大小为 b, 则 X(i) 与 X(2i) 重合等价与 i=2i (mod b) => i=0 (mod b)。环中只有一个节点下标是 b 的倍数，当 X(i) 达到这个节点时，就能发现环。
  
• 这个算法的时间复杂度是 O(n)，空间复杂度为 O(1)
  
  

关于这个题目，在 CU 上有更深入一些的讨论，请参考

• 有什么简单的办法检查单链表里是否有环？
  
• 一个关于单向链表的面试题
  

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

win_hate

Exercise 3.20.  Draw environment diagrams to illustrate the evaluation of the sequence of expressions

(define x (cons 1 2))
(define z (cons x x))
(set-car! (cdr z) 17)
(car x)
17

using the procedural implementation of pairs given above. (Compare exercise 3.11.)

win_hate

<wait for pic>

win_hate

Exercise 3.21.  Ben Bitdiddle decides to test the queue implementation described above. He types in the procedures to the Lisp interpreter and proceeds to try them out:

(define q1 (make-queue))
(insert-queue! q1 'a)
((a) a)
(insert-queue! q1 'b)
((a b) b)
(delete-queue! q1)
((b) b)
(delete-queue! q1)
(() b)

``It's all wrong!'' he complains. ``The interpreter's response shows that the last item is inserted into the queue twice. And when I delete both items, the second b is still there, so the queue isn't empty, even though it's supposed to be.'' Eva Lu Ator suggests that Ben has misunderstood what is happening. ``It's not that the items are going into the queue twice,'' she explains. ``It's just that the standard Lisp printer doesn't know how to make sense of the queue representation. If you want to see the queue printed correctly, you'll have to define your own print procedure for queues.'' Explain what Eva Lu is talking about. In particular, show why Ben's examples produce the printed results that they do. Define a procedure print-queue that takes a queue as input and prints the sequence of items in the queue.