Hatena::Groupsicp

SICP読書記

 | 

2009-11-20

問題2.61

問題2.61 - SICP読書記 を含むブックマーク はてなブックマーク - 問題2.61 - SICP読書記

;; 順序づけられていない場合は、element-of-setを使って
;; リストの最後まで探索する必要があるが、
;; 順序づけられている場合は挿入位置が見つかるまで探索すればよい
;; これはsetの要素数がnの場合平均n/2の計算量になる
(define (adjoin-set x set)
  (if (null? set)
	  (list x)
	  (if (< x (car set))
		  (cons x set)
		  (cons (car set) (adjoin-set x (cdr set))))))


(print (adjoin-set 5 '(1 2 4 8 10)))
;; => (1 2 4 5 8 10)

xが入る場所を探して、見つかったら入れる。

問題2.62

 問題2.62 - SICP読書記 を含むブックマーク はてなブックマーク -  問題2.62 - SICP読書記



(define (union-set set1 set2)
	(cond ((null? set1) set2)
		  ((null? set2) set1)
		  (else  (let ((x1 (car set1))
					   (x2 (car set2)))
				   (cond ((eq? x1 x2) 
						  (cons x1 
								(union-set (cdr set1) (cdr set2))))
						 ((< x1 x2)
						  (cons x1 (union-set (cdr set1) set2)))
						 (else 
						  (cons x2 (union-set set1 (cdr set2)))))))))

(print (union-set '(1 3 5 7 9) '(0 1 2 4 7)))
;; ->  (0 1 2 3 4 5 7 9)

要するにマージソートかつuniqueしろと言ってますよね。

2.4 抽象データの多重表現

2.4 抽象データの多重表現 - SICP読書記 を含むブックマーク はてなブックマーク - 2.4 抽象データの多重表現 - SICP読書記

オブジェクト指向的な話をしているよね。

まあ細かく掘る必要ないか、ということでここもスキップ!

2.5 汎用演算のシステム

2.5 汎用演算のシステム - SICP読書記 を含むブックマーク はてなブックマーク - 2.5 汎用演算のシステム - SICP読書記

Numeric型からはじまるいろんな数値型を統一的に扱うようなことを言っているよね。まあここも飛ばすか。

 |