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が入る場所を探して、見つかったら入れる。

 |