首页 > 代码库 > SICP_2.61-2.62

SICP_2.61-2.62

 1 #lang racket
 2 
 3 ;;;;;;;;;;;;;;;;;2.61
 4 (define (element-of-set? x set)
 5   (cond ((null? set) false)
 6   ((= x (car set)) true)
 7   ((< x (car set)) false)
 8   (else (element-of-set? x (cdr set)))))
 9 
10 (define (intersection-set set1 set2)
11   (if (or (null? set1) (null? set2))
12       ()
13       (let ((x1 (car set1)) (x2 (car set2)))
14         (cond ((= x1 x2)
15                (cons x1
16                      (intersection-set (cdr set1)
17                                       (cdr set2))))
18               ((< x1 x2)
19                (intersection-set (cdr set1) set2))
20               ((< x2 x1)
21                (intersection-set set1 (cdr set2)))))))
22 
23 (define (adjion-set x set)
24   (cond 
25         ((null? set) (cons x set))
26         ((= x (car set)) set)
27         ((< x (car set)) (cons x set))
28         ((> x (car set)) (cons (car set) (adjion-set x (cdr set))))))
29 
30 ;;;;;;;;;;;;;;;;;;;2.62 只有当两列表有顺序时成立
31 (define (union-set set1 set2)
32   (cond ((null? set1) set2)
33         ((null? set2) set1)
34         ((< (car set1) (car set2))
35          (cons (car set1) (union-set (cdr set1) set2)))
36         ((< (car set2) (car set1))
37          (cons (car set2) (union-set set1 (cdr set2))))
38         ((= (car set1) (car set2))
39          (cons (car set1) (union-set (cdr set1) (cdr set2))))))
40 
41 ;;;;;;;;;;;;test
42 (adjion-set 6 (2 3 4 5 7))
43 (adjion-set 1 (2 3 4 5 7))
44 (adjion-set 8 (2 3 4 5 7))
45 (union-set (1 2 3 4 5) (2 3 4 5 7))
46 (union-set (1 3 5 6 8) (2 3 4 5 9))

 

注意2.62的算法是在有顺序条件下才能实现的

SICP_2.61-2.62