開発環境
- 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 コメント:
コメントを投稿