Hatena::Groupcsnagoya-sicp

クラなんとかの日記 このページをアンテナに追加 RSSフィード

 | 

2009-04-11SICP 加速会という名の合宿を行いました

問題 2.11

| 問題 2.11 - クラなんとかの日記 を含むブックマーク はてなブックマーク - 問題 2.11 - クラなんとかの日記 問題 2.11 - クラなんとかの日記 のブックマークコメント

区間の端点の符号を考える.つまり区間と零との比較を考える.

区間A=\[L(A),\hspace{2em} U(A)\]に対しては,以下の3通りが考えられる.

\left\{ \begin{eqnarray} 0 & < & L(A) & < & U(A) & \hfill{325}\hspace{10} \rm(1) \\ L(A) & < & 0 & < & U(A) & \hfill{325}\hspace{10} \rm(2) \\ L(A) & < & U(A) & < & 0 & \hfill{325}\hspace{10} \rm(3) \end{eqnarray}

積の場合,2つの区間A, B を必要とするので,

考えるのは3×3の9 通りになる.

引数の状態
(1)-(1)\[L(A)\cdot L(B),\hspace{2em} U(A)\cdot U(B) \]
(1)-(2)\[U(A)\cdot L(B),\hspace{2em} U(A)\cdot U(B) \]
(1)-(3)\[U(A)\cdot L(B),\hspace{2em} L(A)\cdot U(B) \]
(2)-(1)\[L(A)\cdot U(B),\hspace{2em} U(A)\cdot U(B) \]
(2)-(2)\[{\rm min}(U(A)\cdot L(B),\hspace{2em} L(A)\cdot U(B)),\hspace{2em} {\rm max}(L(A)\cdot L(B),\hspace{2em} U(A)\cdot U(B)) \]
(2)-(3)\[U(A)\cdot L(B),\hspace{2em} L(A)\cdot L(B) \]
(3)-(1)\[L(A)\cdot U(B),\hspace{2em} U(A)\cdot L(B) \]
(3)-(2)\[L(A)\cdot U(B),\hspace{2em} L(A)\cdot L(B) \]
(3)-(3)\[U(A)\cdot U(B),\hspace{2em} L(A)\cdot L(B) \]

符号が負の数を両辺に掛けると,不等号が反転することに注意.

(1)-(1) の場合

L(B) < U(B)の両辺に,L(A), U(A)を掛ける\begin{eqnarray} L(A)\cdot L(B)&<&L(A)\cdot U(B) \\ U(A)\cdot L(B) &<& U(A)\cdot U(B) \end{eqnarray}

小さい方,大きい方同士を比較すると\begin{eqnarray} L(A)\cdot L(B) &<& U(A)\cdot L(B) \\ L(A)\cdot U(B) &<& U(A)\cdot U(B) \end{eqnarray}

なので,解は\[L(A)\cdot L(B),\hspace{2em} U(A)\cdot U(B)\]

(1)-(2) の場合

L(B) < U(B)の両辺に,L(A), U(A)を掛ける\begin{eqnarray} L(A)\cdot L(B)&<&L(A)\cdot U(B) \\ U(A)\cdot L(B) &<& U(A)\cdot U(B) \end{eqnarray}

小さい方,大きい方同士を比較すると\begin{eqnarray} L(A)\cdot L(B) &>& U(A)\cdot L(B) \\ L(A)\cdot U(B) &<& U(A)\cdot U(B) \end{eqnarray}

(L(B)のみ負なので)

なので,解は\[U(A)\cdot L(B),\hspace{2em} U(A)\cdot U(B)\]

(1)-(3) の場合

L(B) < U(B)の両辺に,L(A), U(A)を掛ける\begin{eqnarray} L(A)\cdot L(B)&<&L(A)\cdot U(B) \\ U(A)\cdot L(B) &<& U(A)\cdot U(B) \end{eqnarray}

小さい方,大きい方同士を比較すると\begin{eqnarray} L(A)\cdot L(B) &>& U(A)\cdot L(B) \\ L(A)\cdot U(B) &>& U(A)\cdot U(B) \end{eqnarray}

(L(B),U(B)ともに負なので)

なので,解は\[U(A)\cdot L(B),\hspace{2em} L(A)\cdot U(B)\]

(2)-(1) の場合

L(B) < U(B)の両辺に,L(A), U(A)を掛ける\begin{eqnarray} L(A)\cdot L(B)&>&L(A)\cdot U(B) \\ U(A)\cdot L(B) &<& U(A)\cdot U(B) \end{eqnarray}

小さい方,大きい方同士を比較すると\begin{eqnarray} L(A)\cdot U(B) &<&0&<& U(A)\cdot L(B) \\ L(A)\cdot L(B) &<&0&<& U(A)\cdot U(B) \end{eqnarray}

(L(A) のみが負なので,符号は明らか)

なので,解は\[L(A)\cdot U(B),\hspace{2em} U(A)\cdot U(B)\]

(2)-(2) の場合

L(B) < U(B)の両辺に,L(A), U(A)を掛ける\begin{eqnarray} L(A)\cdot L(B)&>&L(A)\cdot U(B) \\ U(A)\cdot L(B) &<& U(A)\cdot U(B) \end{eqnarray}

小さい方,大きい方同士を比較するが,関係は決められない.

なので,解は\[{\rm min}(L(A)\cdot U(B),\hspace{2em} U(A)\cdot L(B)),\hspace{2em} {\rm max}(L(A)\cdot L(B),\hspace{2em} U(A)\cdot U(B))\]

以降同じなので割愛します.

#!/usr/bin/env gosh
;; -*- coding: utf-8; -*-
; 範囲を持った数表現(interval) - mul

;; 準備

;; 答え
(define (mul-interval x y)
  (define (cmp-interval x value)
    (cond ((< value (lower-bound x)) -1)
          ((< (upper-bound x) value) 1)
          (else 0)))
  (let ((x_cmp_0 (cmp-interval x 0))
        (y_cmp_0 (cmp-interval y 0)))
    (cond ((and (< x_cmp_0 0) (< y_cmp_0 0))
           (make-interval (* (lower-bound x) (lower-bound y))
                          (* (upper-bound x) (upper-bound y))))
          ((and (< x_cmp_0 0) (= y_cmp_0 0))
           (make-interval (* (upper-bound x) (lower-bound y))
                          (* (upper-bound x) (upper-bound y))))
          ((and (< x_cmp_0 0) (> y_cmp_0 0))
           (make-interval (* (upper-bound x) (lower-bound y))
                          (* (lower-bound x) (upper-bound y))))
          ((and (= x_cmp_0 0) (< y_cmp_0 0))
           (make-interval (* (lower-bound x) (upper-bound y))
                          (* (upper-bound x) (upper-bound y))))
          ((and (= x_cmp_0 0) (> y_cmp_0 0))
           (make-interval (* (upper-bound x) (lower-bound y))
                          (* (lower-bound x) (lower-bound y))))
          ((and (> x_cmp_0 0) (< y_cmp_0 0))
           (make-interval (* (lower-bound x) (upper-bound y))
                          (* (upper-bound x) (lower-bound y))))
          ((and (> x_cmp_0 0) (= y_cmp_0 0))
           (make-interval (* (lower-bound x) (upper-bound y))
                          (* (lower-bound x) (lower-bound y))))
          ((and (> x_cmp_0 0) (> y_cmp_0 0))
           (make-interval (* (upper-bound x) (upper-bound y))
                          (* (lower-bound x) (lower-bound y))))
          (else
           (make-interval (min (* (upper-bound x) (lower-bound y))
                               (* (lower-bound x) (upper-bound y)))
                          (max (* (lower-bound x) (lower-bound y))
                               (* (upper-bound x) (upper-bound y))))))))

; 問題 2.10 より
(define (div-interval x y)
  (define (include-interval i value)
    (and (<= (lower-bound i) value)
         (<= value (upper-bound i))))
  (if (include-interval y 0)
      (error "divider include zero value")
      (mul-interval x
                    (make-interval (/ 1.0 (upper-bound y))
                                   (/ 1.0 (lower-bound y))))))

; 問題 2.8 より
(define (sub-interval x y)
  (add-interval x
                (make-interval (- (upper-bound y))
                               (- (lower-bound y)))))

; 問題 2.7 より
(define (upper-bound interval)
  (cdr interval))
(define (lower-bound interval)
  (car interval))

; 問題文 2.7 より
(define (make-interval a b)
  (cons a b))

; 2.1.4 より
(define (add-interval x y)
  (make-interval (+ (lower-bound x) (lower-bound y))
                 (+ (upper-bound x) (upper-bound y))))

(define (mul-interval-org 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 i1 (make-interval 1 2))
(define i2 (make-interval -1 1))
(define i3 (make-interval -2 -1))

(define (display-interval-org-and-new x y)
  (define (display-interval-2d i)
    (format #t "[~@d, ~@d]" (lower-bound i) (upper-bound i)))
  (define (display-prompt x y)
    (display-interval-2d x)
    (display " * ")
    (display-interval-2d y)
    (display " = "))
  (let ((org-result (mul-interval-org x y))
        (new-result (mul-interval x y)))
    (display-prompt x y)
    (display-interval-2d new-result)
    (if (equal? org-result new-result)
        (display " org and new result are same"))
    (newline)))

(display-interval-org-and-new i1 i1)
(display-interval-org-and-new i1 i2)
(display-interval-org-and-new i1 i3)
(display-interval-org-and-new i2 i1)
(display-interval-org-and-new i2 i2)
(display-interval-org-and-new i2 i3)
(display-interval-org-and-new i3 i1)
(display-interval-org-and-new i3 i2)
(display-interval-org-and-new i3 i3)
 |