SICPゼミ第11回 - SICPゼミ

練習問題2.59

(define (union-set set1 set2)
	(cond
		((null? set1) set2)
		(else (adjoin-set (car set1) (union-set (cdr set1) set2)))
		)
	)

by dolicas

練習問題2.60

union-set、adjoin-setは実装が楽で計算も軽い。intersectionの効率が悪い。これ役に立つシチュエーションってあるの？

練習問題2.61

(define (adjoin-set x set)
	(cond
		((null? set) (list x))
		((= (car set) x) set)
		((> (car set) x) (cons x set))
		(else (cons (car set) (adjoin-set x (cdr set))))
		)
	)

by dolicas

練習問題2.62

(define (union-set set1 set2)
	(cond
		((null? set1) set2)
		((null? set2) set1)
		(else
			(let
				((a1 (car set1))
					(a2 (car set2))
					(as1 (cdr set1))
					(as2 (cdr set2)))
				(cond
					((= a1 a2) (cons a1 (union-set as1 as2)))
					((< a1 a2) (cons a1 (union-set as1 set2)))
					(else (cons a2 (union-set set1 as2)))
					)
				)
			)
		)
	)

by dolicas

(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)))
                  ((< x2 x1)
                   (cons x2 (union-set set1 (cdr set2)))))))))

by pine

練習問題2.63

図2.16の木

(define tree-left
(make-tree 7 
	(make-tree 3 (make-tree 1 nil nil) (make-tree 5 nil nil))
	(make-tree 9 nil (make-tree 11 nil nil)))
)

(define t5 (make-tree 11 '() '()))
(define t3 (make-tree 5 '() '()))
(define t4 (make-tree 9 '() t5))
(define t2 (make-tree 7 t3 t4))
(define t1 (make-tree 1 '() '()))
(define t0 (make-tree 3 t1 t2))

(define p-tree (make-tree 5 
                          (make-tree 3
                                     (make-tree 1 nil nil)
                                     nil)
                          (make-tree 9 
                                     (make-tree 7 nil nil)
                                     (make-tree 11 nil nil))))

a) 同じ。

b) 1 は n 回 append (O(n)) するので O(n^2), 2 は n 回 cons (O(1)) なので O(n). (?)

by tube

練習問題2.64

left tree sizeが $(n-1)/2$ を越えない最大の整数になることを考えれば，どのような部分木が生成されるかはすぐわかる．また，部分木の数がエントリの数と一致するのでO(n)で終わる．

練習問題2.65

二分木の union-set と intersection-set について O(n) のアルゴリズムなので、tree->list-2 を使ってリストに直し、union-set, intersection-set して、list->tree でおしまい。
by tube

練習問題2.66

set の element-of-set? と一緒。

練習問題2.67

gosh> (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))
sample-tree
gosh> sample-message
gosh> (decode sample-message sample-tree)
(A D A B B C A)

練習問題2.68

(define (element-of-set? x set)
  (cond (( null? set) #f)
        (( equal? x (car set)) #t)
        (else (element-of-set? x (cdr set )))))

(define (encode-symbol symbol tree)
  (define (encode-symbol-acc current-branch)
    (if (leaf? current-branch)
        nil
        (cond ((element-of-set? symbol (symbols (left-branch current-branch)))
               (cons 0 (encode-symbol-acc (left-branch current-branch))))
              ((element-of-set? symbol (symbols (right-branch current-branch)))
               (cons 1 (encode-symbol-acc (right-branch current-branch))))
              (else (error "bad symbol: CHOOSE-BRANCH" symbol )))))
  (encode-symbol-acc tree))
    
        
(define (encode message tree)
  (if (null? message)
      nil
      (append (encode-symbol (car message) tree)
              (encode (cdr message) tree ))))

by pine

練習問題2.69

(define (successive-merge leaf-sets)
  (define (successive-merge-acc sets leaf1 leaf2)
    (let ((next-set (adjoin-set (make-code-tree leaf2 leaf1) sets)))
      (if (null? (cddr next-set))
          (make-code-tree (cadr next-set) (car next-set))
          (successive-merge-acc (cddr next-set) (car next-set) (cadr next-set)))))
  (successive-merge-acc (cddr leaf-sets) (car leaf-sets) (cadr leaf-sets)))

ちなみにこれを使うと2.67と違う結果が出てしまうが、adjoinでの重みがイコールの時の挿入が末尾になっているから

(define (adjoin-set x set)
  (cond (( null? set) (list x))
        ((<= (weight x) (weight (car set ))) (cons x set))
        (else (cons (car set)
                    (adjoin-set x (cdr set ))))))

に定義し直すと2.67と同じ結果が出る。
by pine