問題2.63
SICP超久しぶり。
思えば学部2-3年のころに一生懸命やっていたな。
ranobaの開発に移ってから、ずっとほったらかしにしていた。
やっぱり難しい。あまり成長してないのか。。。。
なんにしろ、いい加減に終わらせないとね。ぱっぱと飛ばしてこう。
(define (entry tree) (car tree)) (define (left-branch tree) (if (> (length tree) 1) (cadr tree) '())) (define (right-branch tree) (if (> (length tree) 2) (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)) true) ((< x (entry set)) (element-of-set? x (left-branch set))) ((> x (entry set)) (element-of-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 '())) ;; a ;; 同じである ;; b ;; 1は再帰的手続きであり、appendを使っているのでステップ数の増加の程度ははO(n^2)である。 ;; 2も再帰的手続きであるcopy-to-listが入れ子になっているので、反復的手続きではない)が、ステップ数の増加の程度はO(n)である。 ;; 多分。