開発環境
- 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.1(データ抽象入門)、2.1.4(拡張問題: 区間算術演算)の問題 2.10、問題 2.11を解いてみる。
その他参考書籍
問題 2.10
コード
sample.scm
(define (add-interval x y)
(make-interval (+ (lower-bound x) (lower-bound y))
(+ (upper-bound x) (upper-bound y))))
(define (mul-interval x y)
(let ((p1 (* (lower-bound x) (lower-bound y)))
(p2 (* (lower-bound x) (upper-bound y)))
(p3 (* (upper-bound x) (lower-bound y)))
(p4 (* (upper-bound x) (upper-bound y))))
(make-interval (min p1 p2 p3 p4)
(max p1 p2 p3 p4))))
(define (div-interval x y)
(cond ((= (width-interval y) 0) (newline) (display "error"))
(else (mul-interval x
(make-interval (/ 1.0 (upper-bound y))
(/ 1.0 (lower-bound y)))))))
(define (make-interval a b) (cons a b))
(define (upper-bound x) (cdr x))
(define (lower-bound x) (car x))
(define (sub-interval x y)
(make-interval (- (lower-bound x) (upper-bound y))
(- (upper-bound x) (lower-bound y))))
(define (width-interval x)
(/ (- (upper-bound x) (lower-bound x))
2))
(define a (make-interval 10 100))
(define b (make-interval -50 50))
(define zero1 (make-interval 0 0))
(define zero2 (make-interval 10 10))
(define zero3 (make-interval -10 -10))
入出力結果(Terminal, REPL(Read, Eval, Print, Loop))
1 ]=> (div-interval a b) ;Value 11: (-2. . 2.) 1 ]=> (div-interval a zero1) error ;Unspecified return value 1 ]=> (div-interval a zero2) error ;Unspecified return value 1 ]=> (div-interval a zero3) error ;Unspecified return value 1 ]=> (div-interval b zero1) error ;Unspecified return value 1 ]=> (div-interval b zero2) error ;Unspecified return value 1 ]=> (div-interval b zero3) error ;Unspecified return value 1 ]=> (div-interval zero1 a) ;Value 12: (0 . 0) 1 ]=> (div-interval zero2 a) ;Value 13: (.1 . 1.) 1 ]=> (div-interval zero3 a) ;Value 14: (-1. . -.1)
問題 2.11
区間の端点の符号は(正、正)、(負、正)、(負、負)の3通り。(正確には0も含むので、正ではなく非負。以下同様) mul-intervalは2つの区間を引数とするので3の二乗で9通り。
そのうち、二回を超える乗算を必要とするのは、(負、正)と(負、正)の2つの区間を引数とする場合。他の場合は、例えば2つの区間が(正1、正2)、(正3、正4)の場合は、下限は(* 正1 正3)、上限は(* 正2 正4)となる。同様に他の場合も同様に二回の乗算で分かる。
このことに従って手続きを書き直す。
書き直す前。
コード
sample.scm
(define (mul-interval x y)
(let ((p1 (* (lower-bound x) (lower-bound y)))
(p2 (* (lower-bound x) (upper-bound y)))
(p3 (* (upper-bound x) (lower-bound y)))
(p4 (* (upper-bound x) (upper-bound y))))
(make-interval (min p1 p2 p3 p4)
(max p1 p2 p3 p4))))
(define (make-interval a b) (cons a b))
(define (upper-bound x) (cdr x))
(define (lower-bound x) (car x))
(define a (make-interval 10 100))
(define b (make-interval -50 50))
(define c (make-interval -200 -20))
入出力結果(Terminal, REPL(Read, Eval, Print, Loop))
1 ]=> (mul-interval a a) ;Value 2: (100 . 10000) 1 ]=> (mul-interval a b) ;Value 3: (-5000 . 5000) 1 ]=> (mul-interval a c) ;Value 4: (-20000 . -200) 1 ]=> (mul-interval b a) ;Value 5: (-5000 . 5000) 1 ]=> (mul-interval b b) ;Value 6: (-2500 . 2500) 1 ]=> (mul-interval b c) ;Value 7: (-10000 . 10000) 1 ]=> (mul-interval c a) ;Value 8: (-20000 . -200) 1 ]=> (mul-interval c b) ;Value 9: (-10000 . 10000) 1 ]=> (mul-interval c c) ;Value 10: (400 . 40000)
書き直した後。
コード
sample.scm
(define (mul-interval x y)
(let ((x1 (lower-bound x))
(y1 (upper-bound x))
(x2 (lower-bound y))
(y2 (upper-bound y))
(negative? (lambda (n) (< n 0))))
(let ((x1-sign (negative? x1))
(y1-sign (negative? y1))
(x2-sign (negative? x2))
(y2-sign (negative? y2)))
(cond ((and x1-sign (not y1-sign) x2-sign (not y2-sign))
(let ((p1 (* x1 y2))
(p2 (* x2 y1))
(p3 (* x1 y1))
(p4 (* y2 y2)))
(make-interval (min p1 p2) (max p3 p4))))
((and (not x1-sign) (not x2-sign))
(make-interval (* x1 x2) (* y1 y2)))
((and (not x1-sign) (not y2-sign))
(make-interval (* y1 x2) (* y1 y2)))
((not x1-sign) (make-interval (* y1 x2) (* x1 y2)))
((and x1-sign (not y1-sign) (not x2-sign))
(make-interval (* x1 y2) (* y1 y2)))
((and x1-sign (not y1-sign))
(make-interval (* y1 x2) (* x1 x2)))
(y2-sign (make-interval (* y1 y2) (* x1 x2)))
((not x2-sign) (make-interval (* x1 y2) (* y1 x2)))
(else (make-interval (* x1 y2) (* x1 x2)))))))
入出力結果(Terminal, REPL(Read, Eval, Print, Loop))
;Value: mul-interval 1 ]=> (mul-interval a a) ;Value 11: (100 . 10000) 1 ]=> (mul-interval a b) ;Value 12: (-5000 . 5000) 1 ]=> (mul-interval a c) ;Value 13: (-20000 . -200) 1 ]=> (mul-interval b a) ;Value 14: (-5000 . 5000) 1 ]=> (mul-interval b b) ;Value 15: (-2500 . 2500) 1 ]=> (mul-interval b c) ;Value 16: (-10000 . 10000) 1 ]=> (mul-interval c a) ;Value 17: (-20000 . -200) 1 ]=> (mul-interval c b) ;Value 18: (-10000 . 10000) 1 ]=> (mul-interval c c) ;Value 19: (400 . 40000)
0 コメント:
コメントを投稿