開発環境
- macOS Sierra - Apple (OS)
- Emacs (Text Editor)
- Scheme (プログラミング言語)
- kscheme (ksi)(github) (処理系)
計算機プログラムの構造と解釈[第2版](ハロルド エイブルソン (著)、ジュリー サスマン (著)、ジェラルド・ジェイ サスマン (著)、Harold Abelson (原著)、Julie Sussman (原著)、Gerald Jay Sussman (原著)、和田 英一 (翻訳)、翔泳社、原著: Structure and Interpretation of Computer Programs (MIT Electrical Engineering and Computer Science)(SICP))の第2章(データによる抽象の構築)、2.3(記号データ)、2.3.3(例: 集合の表現)、二進木としての集合、問題2.63、64、65.を取り組んでみる。
その他参考書籍
問題2.63、64、65.
コード(Emacs)
((lambda ()
(load "procedures.scm")
(newline)
(define (p obj) (display obj) (newline))
(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)
(if (null? set)
#f
((lambda (e)
(if (= x e)
#t
(if (< x e)
(element-of-set? x (left-branch set))
(element-of-set? x (right-branch set)))))
(entry set))))
(define set1 (make-tree 7
(make-tree 3
(make-tree 1 '() '())
(make-tree 5 '() '()))
(make-tree 9
'()
(make-tree 11 '() '()))))
(define set2 (make-tree 3
(make-tree 1 '() '())
(make-tree 7
(make-tree 5 '() '())
(make-tree 9
'()
(make-tree 11 '() '())))))
(define set3 (make-tree 5
(make-tree 3
(make-tree 1 '() '())
'())
(make-tree 9
(make-tree 7 '() '())
(make-tree 11 '() '()))))
(define sets (list set1 set2 set3))
(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 '()))
(p 2.63)
;; a. 同じ結果
(for-each (lambda (tree)
(p (tree->list-1 tree))
(p (tree->list-2 tree)))
sets)
;; b. ステップ数の増加の程度は違い、2の方がより遅く増加する(append)
(p "2.64-a")
(define (list->tree elements)
(car (partial-tree elements (length elements))))
(define (partial-tree elts n)
(if (= n 0)
(cons '() elts)
((lambda (left-size)
((lambda (left-result)
((lambda (left-tree non-left-elts right-size)
((lambda (this-entry right-result)
((lambda (right-tree remaining-elts)
(cons (make-tree this-entry left-tree right-tree)
remaining-elts))
(car right-result) (cdr right-result)))
(car non-left-elts) (partial-tree (cdr non-left-elts)
right-size)))
(car left-result) (cdr left-result) (- n (+ left-size 1))))
(partial-tree elts left-size)))
(quotient (- n 1) 2))))
(define tree1 (make-tree 5
(make-tree 1
'()
(make-tree 3 '() '()))
(make-tree 9
(make-tree 7 '() '())
(make-tree 11 '() '()))))
(define tree2 (list->tree '(1 3 5 7 9 11)))
(p tree1)
(p tree2)
(p (equal? tree1 tree2))
;; b. ステップ数の増加の程度 Θ(n)
(p 2.65)
(define tree->list tree->list-2)
(define (union-set set1 set2)
((lambda (list1 list2)
(define (iter list1 list2)
(if (null? list1)
list2
(if (null? list2)
list1
((lambda (x y)
(if (< x y)
(cons x (iter (cdr list1) list2))
(if (= x y)
(cons x (iter (cdr list1) (cdr list2)))
(cons y (iter list1 (cdr list2))))))
(car list1) (car list2)))))
(list->tree (iter list1 list2)))
(tree->list set1) (tree->list set2)))
(define (intersection-set set1 set2)
((lambda (list1 list2)
(define (iter list1 list2)
(if (or (null? list1) (null? list2))
'()
((lambda (x y)
(if (< x y)
(iter (cdr list1) list2)
(if (= x y)
(cons x (iter (cdr list1) (cdr list2)))
(iter list1 (cdr list2)))))
(car list1) (car list2))))
(list->tree (iter list1 list2)))
(tree->list set1) (tree->list set2)))
(define odd (list->tree '(1 3 5 7 9)))
(define even (list->tree '(2 4 6 8 10)))
(define nums (list->tree '(1 2 3 4 5)))
(define sets (list odd even nums))
(for-each (lambda (set1)
(for-each (lambda (set2)
(display "set1: ")
(p (tree->list set1))
(display "set2: ")
(p (tree->list set2))
(display "union: ")
(p (tree->list (union-set set1 set2)))
(display "intersection: ")
(p (tree->list (intersection-set set1 set2)))
(newline))
sets))
sets)
'done))
入出力結果(Terminal(kscheme), REPL(Read, Eval, Print, Loop))
$ ksi < sample63.scm ksi> 2.63 (1 3 5 7 9 11) (1 3 5 7 9 11) (1 3 5 7 9 11) (1 3 5 7 9 11) (1 3 5 7 9 11) (1 3 5 7 9 11) 2.64-a (5 (1 () (3 () ())) (9 (7 () ()) (11 () ()))) (5 (1 () (3 () ())) (9 (7 () ()) (11 () ()))) #t 2.65 set1: (1 3 5 7 9) set2: (1 3 5 7 9) union: (1 3 5 7 9) intersection: (1 3 5 7 9) set1: (1 3 5 7 9) set2: (2 4 6 8 10) union: (1 2 3 4 5 6 7 8 9 10) intersection: () set1: (1 3 5 7 9) set2: (1 2 3 4 5) union: (1 2 3 4 5 7 9) intersection: (1 3 5) set1: (2 4 6 8 10) set2: (1 3 5 7 9) union: (1 2 3 4 5 6 7 8 9 10) intersection: () set1: (2 4 6 8 10) set2: (2 4 6 8 10) union: (2 4 6 8 10) intersection: (2 4 6 8 10) set1: (2 4 6 8 10) set2: (1 2 3 4 5) union: (1 2 3 4 5 6 8 10) intersection: (2 4) set1: (1 2 3 4 5) set2: (1 3 5 7 9) union: (1 2 3 4 5 7 9) intersection: (1 3 5) set1: (1 2 3 4 5) set2: (2 4 6 8 10) union: (1 2 3 4 5 6 8 10) intersection: (2 4) set1: (1 2 3 4 5) set2: (1 2 3 4 5) union: (1 2 3 4 5) intersection: (1 2 3 4 5) => done ksi> $
0 コメント:
コメントを投稿