乐正

Actions speak louder than words.

Sicp-ex3-17

问题

请设计出练习3.16中count-pairs过程的一个正确版本,使它对任何结构都能返回不同序对的个数。(提示:遍历有关的结构,维护一个辅助性数据结构,用它记录已经计算过的序对的轨迹。)

解答

练习3.17 (ex3-17.scm) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
(define (count-pairs x)
  (let ((computed '()))
    (define (in? item lst)
      (cond ((null? lst) #f)
            ((eq? item (car lst)) #t)
            (else (in? item (cdr lst)))))
    (define (iter y)
      (cond ((not (pair? y)) 0)
            ((in? y computed) 0)
            (else (begin
                    (set! computed (cons y computed))
                    (+ (iter (car y))
                       (iter (cdr y))
                       1)))))
    (iter x)))

测试

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
(count-pairs (list 'a 'b 'c))
;Value: 3

(define z (list 'b 'c))
;Value: z

(define a (cons z z))
;Value: a

(count-pairs a)
;Value: 3

(define a (list 'a 'b 'c))
;Value: a

(set-cdr! (last-pair a) a)
;Unspecified return value

(count-pairs a)
;Value: 3

draft

« sicp-ex3-16 sicp-ex3-18 »

Comments