計算機プログラムの構造と解釈 第二版 P53 問題2.11
やることは、
・Benが言っているように手続きを書き直す。
Benがそもそもなにを狙っているかというと、
今まで使っていた、mul-intervalはmaxとかminをつかって、
最小値と最大値を出していて結構ずるっこい。
だけど、これをちゃんと整理して作り直しましょうよ、
ってこと。
区間の掛け算(mul-interval)について考える。
Ben曰く、各区間の符号を考えると9つあると。
なるほど、たとえば、区間 xとyがあったとする。
xl:xの下限値
xu:xの上限値
yl:yの下限値
yu:yの上限値
端点(上限値か下限値)を意識してみると。
xl >= 0 (xの下限値が、0より大きい場合)(xlもxuも0か正の数)
xu <= 0 (xの上限値が、0より小さい場合)(xlもxuも0か負の数)
xが0に跨がる場合 (xuが正の数で、xlが負の数)
の三つに分けられそうだし、
yもまた、
yl >= 0 (yの下限値が、0より大きい場合)(ylもyuも0か正の数)
yu <= 0 (yの上限値が、0より小さい場合)(ylもyuも0か負の数)
yが0に跨がる場合 (yuが正の数で、ylが負の数)
だ。
そうすると、mul-intervalの結果の中身は
| yl >= 0 | yu <= 0 | yl<0, yu>0 -----------+---------------+---------------+---------------- xl >= 0 | (xlyl . xuyu) | (xuyl . xlyu) | (xuyl . xuyu) xu <= 0 | (xlyu . xuyl) | (xuyu . xlyu) | (xlyu . xlyl) xl<0, xu>0 | (xlyu . xuyu) | (xuyl . xlyl) | min(xlyu, xuyl), max(xlyl, xuyu)
なんて感じでケース別にわけられるよねぇ。
あとは粛々と実装するのみ。
以下実装
#!/usr/local/bin/gosh ;; -*- coding: utf-8 -*- (use ggc.debug.trace) (use math.mt-random) ;;積 (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)))) ;;interval (define (make-interval a b) (cons a b)) (define upper-bound cdr) (define lower-bound car) ;;問題2-11 (define (mul-interval2 x y) (let ((xl (lower-bound x)) (xu (upper-bound x)) (yl (lower-bound y)) (yu (upper-bound y))) (cond ((>= xl 0) (cond ((>= yl 0) (make-interval (* xl yl) (* xu yu))) ((<= yu 0) (make-interval (* xu yl) (* xl yu))) (else (make-interval (* xu yl) (* xu yu))))) ((<= xu 0) (cond ((>= yl 0) (make-interval (* xl yu) (* xu yl))) ((<= yu 0) (make-interval (* xu yu) (* xl yl))) (else (make-interval (* xl yu) (* xl yl))))) (else (cond ((>= yl 0) (make-interval (* xl yu) (* xu yu))) ((<= yu 0) (make-interval (* xu yl) (* xl yl))) (else (make-interval (min (* xl yu) (* xu yl)) (max (* xl yl) (* xu yu))))))))) (define intervalx1 (make-interval 3 5)) (define intervalx2 (make-interval -6 -2)) (define intervalx3 (make-interval -4 2)) (define intervaly1 (make-interval 4 7)) (define intervaly2 (make-interval -8 -1)) (define intervaly3 (make-interval -3 3)) ;; main (define (main args) (newline) (display "intervalx1: ") (display intervalx1) (newline) (display "intervalx2: ") (display intervalx2) (newline) (display "intervalx3: ") (display intervalx3) (newline) (display "intervaly1: ") (display intervaly1) (newline) (display "intervaly2: ") (display intervaly2) (newline) (display "intervaly3: ") (display intervaly3) (newline)(newline) (display "xl >= 0の時 ")(newline) (display "且つ yl >= 0の時 ")(newline) (display "(mul-interval intervalx1 intervaly1): ") (display (mul-interval intervalx1 intervaly1)) (newline) (display "(mul-interval2 intervalx1 intervaly1): ") (display (mul-interval2 intervalx1 intervaly1)) (newline) (display "且つ yu <= 0の時 ")(newline) (display "(mul-interval intervalx1 intervaly2): ") (display (mul-interval intervalx1 intervaly2)) (newline) (display "(mul-interval2 intervalx1 intervaly2): ") (display (mul-interval2 intervalx1 intervaly2)) (newline) (display "且つ yl<0, yu>0の時 ")(newline) (display "(mul-interval intervalx1 intervaly3): ") (display (mul-interval intervalx1 intervaly3)) (newline) (display "(mul-interval2 intervalx1 intervaly3): ") (display (mul-interval2 intervalx1 intervaly3)) (newline)(newline) (display "xu <= 0の時 ")(newline) (display "且つ yl >= 0の時 ")(newline) (display "(mul-interval intervalx2 intervaly1): ") (display (mul-interval intervalx2 intervaly1)) (newline) (display "(mul-interval2 intervalx2 intervaly1): ") (display (mul-interval2 intervalx2 intervaly1)) (newline) (display "且つ yu <= 0の時 ")(newline) (display "(mul-interval intervalx2 intervaly2): ") (display (mul-interval intervalx2 intervaly2)) (newline) (display "(mul-interval2 intervalx2 intervaly2): ") (display (mul-interval2 intervalx2 intervaly2)) (newline) (display "且つ yl<0, yu>0の時 ")(newline) (display "(mul-interval intervalx2 intervaly3): ") (display (mul-interval intervalx2 intervaly3)) (newline) (display "(mul-interval2 intervalx2 intervaly3): ") (display (mul-interval2 intervalx2 intervaly3)) (newline)(newline) (display "xl<0, xu>0の時 ")(newline) (display "且つ yl >= 0の時 ")(newline) (display "(mul-interval intervalx2 intervaly1): ") (display (mul-interval intervalx2 intervaly1)) (newline) (display "(mul-interval2 intervalx2 intervaly1): ") (display (mul-interval2 intervalx2 intervaly1)) (newline) (display "且つ yu <= 0の時 ")(newline) (display "(mul-interval intervalx2 intervaly2): ") (display (mul-interval intervalx2 intervaly2)) (newline) (display "(mul-interval2 intervalx2 intervaly2): ") (display (mul-interval2 intervalx2 intervaly2)) (newline) (display "且つ yl<0, yu>0の時 ")(newline) (display "(mul-interval intervalx2 intervaly3): ") (display (mul-interval intervalx2 intervaly3)) (newline) (display "(mul-interval2 intervalx2 intervaly3): ") (display (mul-interval2 intervalx2 intervaly3)) (newline)(newline) (newline) 0)
実行
intervalx1: (3 . 5) intervalx2: (-6 . -2) intervalx3: (-4 . 2) intervaly1: (4 . 7) intervaly2: (-8 . -1) intervaly3: (-3 . 3) xl >= 0の時 且つ yl >= 0の時 (mul-interval intervalx1 intervaly1): (12 . 35) (mul-interval2 intervalx1 intervaly1): (12 . 35) 且つ yu <= 0の時 (mul-interval intervalx1 intervaly2): (-40 . -3) (mul-interval2 intervalx1 intervaly2): (-40 . -3) 且つ yl<0, yu>0の時 (mul-interval intervalx1 intervaly3): (-15 . 15) (mul-interval2 intervalx1 intervaly3): (-15 . 15) xu <= 0の時 且つ yl >= 0の時 (mul-interval intervalx2 intervaly1): (-42 . -8) (mul-interval2 intervalx2 intervaly1): (-42 . -8) 且つ yu <= 0の時 (mul-interval intervalx2 intervaly2): (2 . 48) (mul-interval2 intervalx2 intervaly2): (2 . 48) 且つ yl<0, yu>0の時 (mul-interval intervalx2 intervaly3): (-18 . 18) (mul-interval2 intervalx2 intervaly3): (-18 . 18) xl<0, xu>0の時 且つ yl >= 0の時 (mul-interval intervalx2 intervaly1): (-42 . -8) (mul-interval2 intervalx2 intervaly1): (-42 . -8) 且つ yu <= 0の時 (mul-interval intervalx2 intervaly2): (2 . 48) (mul-interval2 intervalx2 intervaly2): (2 . 48) 且つ yl<0, yu>0の時 (mul-interval intervalx2 intervaly3): (-18 . 18) (mul-interval2 intervalx2 intervaly3): (-18 . 18)
おけ。