SICP-2.3.3节练习
练习 2.59 - 2.66
练习 2.59:
Implement the union-set operation for the unordered-list representation of sets.
我的解答：
(define (element-of-set? x set)
(cond ((null? set) #f)
((equal? x (car set)) #t)
(else (element-of-set? x (cdr set)))))
(define (adjoin-set x set)
(if (element-of-set? x set)
set
(cons x set)))
(define (intersection-set set1 set2)
(cond ((or (null? set1) (null? set2)) '())
((element-of-set? (car set1) set2)
(cons (car set1)
(intersection-set (cdr set1) set2)))
(else (intersection-set (cdr set1) set2))))
(define (union-set set1 set2)
(cond ((null? set1) set2)
((element-of-set? (car set1) set2)
(union-set (cdr set1) set2))
(else (cons (car set1)
(union-set (cdr set1) set2)))))
练习 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?
我的解答：
(define (element-of-set? x set)
(cond ((null? set) #f)
((equal? x (car set)) #t)
(else (element-of-set? x (cdr set)))))
(define (adjoin-set x set)
(cons x set))
(define (union-set set1 set2)
(append set1 set2))
(define (remove-element x set)
(let iter ((acc '()) (rest set))
(cond ((null? rest) acc)
((equal? x (car rest))
(iter acc (cdr rest)))
(else
(iter (cons (car rest) acc)
(cdr rest))))))
(define (intersection-set set1 set2)
(cond ((or (null? set1) (null? set2)) '())
((element-of-set? (car set1) set2)
(cons (car set1)
(intersection-set (cdr set1)
(remove-element (car set1) set2))))
(else (intersection-set (cdr set1) set2))))
练习 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.
我的解答：
(define (element-of-set? x set)
(cond ((null? set) #f)
((= x (car set)) #t)
((< x (car set)) #f)
(else (element-of-set? x (cdr 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))))))
(define (intersection-set set1 set2)
(if (or (null? set1) (null? set2))
'()
(let ((x1 (car set1)) (x2 (car set2)))
(cond ((= x1 x2)
(cons x1
(intersection-set (cdr set1) (cdr set2))))
((< x1 x2)
(intersection-set (cdr set1) set2))
((> x1 x2)
(intersection-set set1 (cdr set2)))))))
(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)))))))))
练习 2.62:
Give a [theta](n) implementation of union-set for sets represented as ordered lists.
我的解答：
见练习 2.61
练习 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 '()))
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?
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?
我的解答：
a:
tree->list-1 与 tree->list-2 两个过程对所有的树产生的结果相同。
scheme@(guile-user)> (tree->list-1 '(7 (3 (1 () ())
(5 () ()))
(9 ()
(11 () ()))))
(1 3 5 7 9 11)
scheme@(guile-user)> (tree->list-2 '(7 (3 (1 () ())
(5 () ()))
(9 ()
(11 () ()))))
(1 3 5 7 9 11)
scheme@(guile-user)> (tree->list-1 '(3 (1 () ())
(7 (5 () ())
(9 () (11 () ())))))
(1 3 5 7 9 11)
scheme@(guile-user)> (tree->list-2 '(3 (1 () ())
(7 (5 () ())
(9 () (11 () ())))))
(1 3 5 7 9 11)
scheme@(guile-user)> (tree->list-1 '(5 (3 (1 () ())
())
(9 (7 () ())
(11 () ()))))
(1 3 5 7 9 11)
scheme@(guile-user)> (tree->list-2 '(5 (3 (1 () ())
())
(9 (7 () ())
(11 () ()))))
(1 3 5 7 9 11)
b:
tree->list-1 O(n log n)
tree->list-2 O(n)
练习 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))))))))
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).
What is the order of growth in the number of steps required by list->tree to convert a list of n
elements?
我的解答：
a. scheme@(guile-user)> ,trace (list->tree '(1 2 3 4 5)) trace: (list->tree (1 2 3 4 5)) trace: | (length (1 2 3 4 5)) trace: | 5 trace: | (partial-tree (1 2 3 4 5) 5) trace: | | (partial-tree (1 2 3 4 5) 2) trace: | | | (partial-tree (1 2 3 4 5) 0) trace: | | | (() 1 2 3 4 5) trace: | | | (partial-tree (2 3 4 5) 1) trace: | | | | (partial-tree (2 3 4 5) 0) trace: | | | | (() 2 3 4 5) trace: | | | | (partial-tree (3 4 5) 0) trace: | | | | (() 3 4 5) trace: | | | | (make-tree 2 () ()) trace: | | | | (2 () ()) trace: | | | ((2 () ()) 3 4 5) trace: | | | (make-tree 1 () (2 () ())) trace: | | | (1 () (2 () ())) trace: | | ((1 () (2 () ())) 3 4 5) trace: | | (partial-tree (4 5) 2) trace: | | | (partial-tree (4 5) 0) trace: | | | (() 4 5) trace: | | | (partial-tree (5) 1) trace: | | | | (partial-tree (5) 0) trace: | | | | (() 5) trace: | | | | (partial-tree () 0) trace: | | | | (()) trace: | | | | (make-tree 5 () ()) trace: | | | | (5 () ()) trace: | | | ((5 () ())) trace: | | | (make-tree 4 () (5 () ())) trace: | | | (4 () (5 () ())) trace: | | ((4 () (5 () ()))) trace: | | (make-tree 3 (1 () (2 () ())) (4 () (5 () ()))) trace: | | (3 (1 () (2 () ())) (4 () (5 () ()))) trace: | ((3 (1 () (2 () ())) (4 () (5 () ())))) trace: (3 (1 () (2 () ())) (4 () (5 () ()))) b. Θ(n)
练习 2.65:
Use the results of Exercise 2-63 and Exercise 2-64 to give [theta](n) implementations of union-set and intersection-set for sets implemented as (balanced) binary trees.
我的解答：
(define (entry tree)
(car tree))
(define (left-branch tree)
(cadr tree))
(define (right-branch tree)
(caddr tree))
(define (make-tree entry left right)
(list entry left right))
(define (element-of-set? x set)
(cond ((null? set) #f)
((= x (entry set)) #t)
((< x (entry set))
(element-of-set? x (left-branch set)))
((> x (entry set))
(element-of-set? x (right-branch set)))))
(define (adjoin-set x set)
(cond ((null? set) (make-tree x '() '()))
((= x (entry set)) set)
((< x (entry set))
(make-tree (entry set)
(adjoin-set x (left-branch set))
(right-branch set)))
((> x (entry set))
(make-tree (entry set)
(left-branch set)
(adjoin-set x (right-branch set))))))
(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 '()))
(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))))))))
(define (list->tree elements)
(car (partial-tree elements (length elements))))
(define (union-set set1 set2)
(let ((elts-1 (tree->list-1 set1))
(elts-2 (tree->list-1 set2)))
(list->tree (let union ((xs elts-1) (ys elts-2))
(cond ((null? xs) ys)
((null? ys) xs)
(else (let ((x (car xs)) (y (car ys)))
(cond ((= x y) (union (cdr xs) ys))
((< x y) (cons x (union (cdr xs) ys)))
((> x y) (cons y (union xs (cdr ys))))))))))))
(define (intersection-set set1 set2)
(let ((elts-1 (tree->list-1 set1))
(elts-2 (tree->list-1 set2)))
(list->tree (let intersection ((xs elts-1) (ys elts-2))
(cond ((or (null? xs) (null? ys)) '())
(else (let ((x (car xs)) (y (car ys)))
(cond ((= x y) (cons x (intersection (cdr xs) (cdr ys))))
((< x y) (intersection (cdr xs) ys))
((> x y) (intersection xs (cdr ys)))))))))))
练习 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.
我的解答：
(define (look-up given-key set-of-records)
(cond ((null? set-of-records) #f)
((equal? given-key (key (entry set-of-records)))
(entry set-of-records))
((less? given-key (key (entry set-of-records)))
(look-up given-key (left-branch set-of-records)))
(else
(look-up given-key (right-branch set-of-records)))))
评论 (0)