開発環境
- OS X Lion - Apple(OS)
- Emacs、BBEdit - Bare Bones Software, Inc. (Text Editor)
- プログラミング言語: MIT/GNU Scheme
計算機プログラムの構造と解釈(Gerald Jay Sussman(原著)、Julie Sussman(原著)、Harold Abelson(原著)、和田 英一(翻訳)、ピアソンエデュケーション)の2(データによる抽象の構築)、2.2(階層データ構造と閉包)、2.2.2(階層構造)の問題 2.29、問題 2.30、問題 2.31、問題 2.32を解いてみる。
その他参考書籍
問題 2.29
a, b.
コード
sample.scm
(define (make-mobile left right)
(list left right))
(define (make-branch length structure)
(list length structure))
(define (left-branch mobile)
(car mobile))
(define (right-branch mobile)
(car (cdr mobile)))
(define (branch-length branch)
(car branch))
(define (branch-structure branch)
(car (cdr branch)))
(define (total-weight mobile)
(define (iter mobile result)
(define left-branch-structure (branch-structure (left-branch mobile)))
(define right-branch-structure (branch-structure (right-branch mobile)))
(+ (if (pair? left-branch-structure)
(iter left-branch-structure 0)
left-branch-structure)
(if (pair? right-branch-structure)
(iter right-branch-structure 0)
right-branch-structure)
result))
(iter mobile 0))
(define mobile-1 (make-mobile branch-1 branch-2))
(define branch-1 (make-branch 5 10))
(define branch-2 (make-branch 15 mobile-2))
(define mobile-2 (make-mobile branch-3 branch-4))
(define branch-3 (make-branch 20 25))
(define branch-4 (make-branch 30 35))
入出力結果(Terminal, REPL(Read, Eval, Print, Loop))
1 ]=> (total-weight mobile-1) ;Value: 70 1 ]=> (total-weight mobile-2) ;Value: 60
c.
コード
sample.scm
(define (balanced? mobile)
(define left (left-branch mobile))
(define right (right-branch mobile))
(define left-length (branch-length left))
(define right-length (branch-length right))
(define left-structure (branch-structure left))
(define right-structure (branch-structure right))
(and (= (* left-length
(if (pair? left-structure)
(total-weight left-structure)
left-structure))
(* right-length
(if (pair? right-structure)
(total-weight right-structure)
right-structure)))
(if (pair? left-structure)
(balanced? left-structure)
true)
(if (pair? right-structure)
(balanced? right-structure)
true)))
; 釣り合っている
(define mobile-1 (make-mobile branch-1 branch-1))
(define mobile-2 (make-mobile branch-1 branch-2))
(define mobile-3 (make-mobile branch-3 branch-4))
; 釣り合っていない
(define mobile-4 (make-mobile branch-1 branch-4))
(define mobile-5 (make-mobile branch-1 branch-5))
(define branch-0 (make-branch 0 0))
(define branch-1 (make-branch 5 10))
(define branch-2 (make-branch 2 25))
(define branch-3 (make-branch 2 mobile-2))
(define branch-4 (make-branch 10 7))
(define branch-5 (make-branch 1 (make-mobile branch-0 (make-branch 1 50))))
入出力結果(Terminal, REPL(Read, Eval, Print, Loop))
1 ]=> (balanced? mobile-1) ;Value: #t 1 ]=> (balanced? mobile-2) ;Value: #t 1 ]=> (balanced? mobile-3) ;Value: #t 1 ]=> (balanced? mobile-4) ;Value: #f 1 ]=> (balanced? mobile-5) ;Value: #f
d.
プログラムの二進モービルの右の枝に関係する部分と、枝のstructureが関係する部分を変更しなければならない。
コード
sample.scm
;(define (make-mobile left right) ; (list left right)) (define (make-mobile left right) (cons left right)) ;(define (make-branch length structure) ; (list length structure)) (define (make-branch length structure) (cons length structure)) (define (left-branch mobile) (car mobile)) ;(define (right-branch mobile) ; (car (cdr mobile))) (define (right-branch mobile) (cdr mobile)) (define (branch-length branch) (car branch)) ;(define (branch-structure branch) ; (car (cdr branch))) (define (branch-structure branch) (cdr branch)) (define branch-1 (make-branch 5 10)) (define branch-2 (make-branch 15 20)) (define mobile-1 (make-mobile branch-1 branch-2)) (define branch-3 (make-branch 25 mobile-1)) (define branch-4 (make-branch 30 35)) (define mobile-2 (make-mobile branch-3 branch-4))
入出力結果(Terminal, REPL(Read, Eval, Print, Loop))
1 ]=> branch-1 ;Value 2: (5 . 10) 1 ]=> (left-branch mobile-1) ;Value 2: (5 . 10) 1 ]=> branch-2 ;Value 3: (15 . 20) 1 ]=> (right-branch mobile-1) ;Value 3: (15 . 20) 1 ]=> branch-3 ;Value 4: (25 (5 . 10) 15 . 20) 1 ]=> (left-branch mobile-2) ;Value 4: (25 (5 . 10) 15 . 20) 1 ]=> branch-4 ;Value 5: (30 . 35) 1 ]=> (right-branch mobile-2) ;Value 5: (30 . 35) 1 ]=> (branch-length branch-1) ;Value: 5 1 ]=> (branch-length branch-2) ;Value: 15 1 ]=> (branch-length branch-3) ;Value: 25 1 ]=> (branch-length branch-4) ;Value: 30 1 ]=> (branch-structure branch-1) ;Value: 10 1 ]=> (branch-structure branch-2) ;Value: 20 1 ]=> (branch-structure branch-3) ;Value 6: ((5 . 10) 15 . 20) 1 ]=> mobile-1 ;Value 6: ((5 . 10) 15 . 20) 1 ]=> (branch-structure branch-4) ;Value: 35
問題 2.30
高階手続きを使わずに直接定義。
コード
sample.scm
(define (square-tree tree)
(cond ((null? tree) tree)
((not (pair? tree)) (square tree))
(else (cons (square-tree (car tree))
(square-tree (cdr tree))))))
入出力結果(Terminal, REPL(Read, Eval, Print, Loop))
1 ]=> (square-tree tree) ;Value 2: (1 (4 (9 16) 25) (36 49))
mapと再帰を使って定義。
コード
sample.scm
(define (square-tree tree)
(map (lambda (sub-tree)
(if (pair? sub-tree)
(square-tree sub-tree)
(square sub-tree)))
tree))
入出力結果(Terminal, REPL(Read, Eval, Print, Loop))
1 ]=> (square-tree tree) ;Value 2: (1 (4 (9 16) 25) (36 49))
問題 2.31
コード
sample.scm
(define (tree-map proc tree)
(define (inner tree)
(map (lambda (sub-tree)
(if (pair? sub-tree)
(inner sub-tree)
(proc sub-tree)))
tree))
(inner tree))
(define (square-tree tree) (tree-map square tree))
(define tree (list 1
(list 2 (list 3 4) 5)
(list 6 7)))
入出力結果(Terminal, REPL(Read, Eval, Print, Loop))
1 ]=> (square-tree tree) ;Value 2: (1 (4 (9 16) 25) (36 49))
問題 2.32
コード
sample.scm
(define (subsets s)
(if (null? s)
(list s)
(let ((rest (subsets (cdr s))))
(append rest (map (lambda (x)
(append (list (car s))
x))
rest)))))
(define s (list 1 2 3))
入出力結果(Terminal, REPL(Read, Eval, Print, Loop))
1 ]=> (subsets s) ;Value 2: (() (3) (2) (2 3) (1) (1 3) (1 2) (1 2 3))
うまくいくのは、ある1つの要素(car s)を含まない部分集合全て(rest)と、その1つの要素を含む部分集合全て(mapを使ったところ)を要素とする集合を作成しているから上手くいく。(明快に説明できてるかなぁ〜。。)
0 コメント:
コメントを投稿