SICP-2.1.3节练习
SICP-2.2.1节练习

SICP-2.1.4节练习

lispor posted @ Feb 26, 2011 05:20:25 PM in Scheme with tags SICP , 1697 阅读

练习 2.7 - 2.16

 
练习 2.7:
Alyssa's program is incomplete because she has not specified the implementation of the interval
abstraction. Here is a definition of the interval constructor:
(define (make-interval a b) (cons a b))
Define selectors upper-bound and lower-bound to complete the implementation.
我的解答:
(define (make-interval a b)
  (cons a b))

(define (upper-bound z)
  (max (car z)
       (cdr z)))

(define (lower-bound z)
  (min (car z)
       (cdr z)))
 
练习 2.8:
Using reasoning analogous to Alyssa's, describe how the difference of two intervals may be
computed. Define a corresponding subtraction procedure, called sub-interval.
我的解答:
(define (add-interval x y)
  (make-interval (+ (lower-bound x)
                    (lower-bound y))
                 (+ (upper-bound x)
                    (upper-bound y))))

(define (sub-interval x y)
  (add-interval x
                (make-interval (- (upper-bound y))
                               (- (lower-bound y)))))
 
练习 2.9:
The width of an interval is half of the difference between its upper and lower bounds. The width is
a measure of the uncertainty of the number specified by the interval. For some arithmetic operations
the width of the result of combining two intervals is a function only of the widths of the argument
intervals, whereas for others the width of the combination is not a function of the widths of the
argument intervals. Show that the width of the sum (or difference) of two intervals is a function
only of the widths of the intervals being added (or subtracted). Give examples to show that this is
not true for multiplication or division.
我的解答:
证明:
已知任意两个区间分别为:I1 = [x1, x2], I2 = [x3, x4],
则 I1 的宽度 d1 = (x2-x1)/2, I2 的宽度为 d2 = (x4-x3)/2,
I1 和 I2 的和 I3 = I1+I2 = [x1, x2] + [x3, x4] = [x1+x3, x2+x4]
则 I3 的宽度 d3 = [(x2+x4)-(x1+x3)]/2 = (x2-x1)/2 + (x4-x3)/2 = d1+d2
同理,
I1 和 I2 的差 I4 = I1-I2 = [x1, x2]-[x3, x4] = [x1-x4, x2-x3]
则 I4 的宽度 d4 = [(x2-x3)-(x1-x4)]/2 = (x2-x1)/2+(x4-x3)/2 = d1+d2
因此,两个区间的和(与差)的宽度就是被加(减)的区间的宽度的函数。
以下举例证明两个区间的积(与商)的宽度则不然:
先假设两个区间的积(与商)的宽度是被乘(除)的区间的宽度的函数,则任意两对相同宽度的区间积(商)的宽度相等,
已知 I1 = [1, 4], I2 = [5, 8], I3 = [2, 6], I4 = [7, 11],
则 d1 = d2 = 1.5, d3 = d4 = 2,
根据以上假设,则区间 I5 = I1*I3 = [2, 24] 的宽度与区间 I6 = I2*I4 = [35, 88] 的宽度相同,
而 d5 = 11, d6 = 26.5, d5 != d6,
此处与假设矛盾,假设不成立,
故两个区间的积(与商)的宽度不是被乘(除)的区间的宽度的函数
 
练习 2.10:
Ben Bitdiddle, an expert systems programmer, looks over Alyssa's shoulder and comments that it is
not clear what it means to divide by an interval that spans zero. Modify Alyssa's code to check for
this condition and to signal an error if it occurs.
我的解答:
(define (div-interval x y)
  (let ((lower-y (lower-bound y))
        (upper-y (upper-bound y)))
    (if (<= lower-y 0 upper-y)
        (error "divide by an interval that spans zero")
        (mul-interval x
                      (make-interval (/ 1.0 lower-y)
                                     (/ 1.0 upper-y))))))
 
练习 2.11:
In passing, Ben also cryptically comments: “By testing the signs of the endpoints of the intervals,
it is possible to break mul-interval into nine cases, only one of which requires more than two
multiplications.” Rewrite this procedure using Ben's suggestion.
没做出来,参考网上:
(define (mul-interval x y)
  (define (endpoint-sign i)
    (cond ((and (>= (upper-bound i) 0)
                (>= (lower-bound i) 0))
           1)
          ((and (< (upper-bound i) 0)
                (< (lower-bound i) 0))
           -1)
          (else 0)))
  (let ((es-x (endpoint-sign x))
        (es-y (endpoint-sign y))
        (x-up (upper-bound x))
        (x-lo (lower-bound x))
        (y-up (upper-bound y))
        (y-lo (lower-bound y)))
    (cond ((> es-x 0)
           (cond ((> es-y 0)
                  (make-interval (* x-lo y-lo) (* x-up y-up)))
                 ((< es-y 0)
                  (make-interval (* x-up y-lo) (* x-lo y-up)))
                 (else
                  (make-interval (* x-up y-lo) (* x-up y-up)))))

          ((< es-x 0)
           (cond ((> es-y 0)
                  (make-interval (* x-lo y-up) (* x-up y-lo)))
                 ((< es-y 0)
                   (make-interval (* x-up y-up) (* x-lo y-lo)))
                 (else
                  (make-interval (* x-lo y-up) (* x-up y-lo)))))

          (else
           (cond ((> es-y 0)
                  (make-interval (* x-lo y-up) (* x-up y-up)))
                 ((< es-y 0)
                  (make-interval (* x-up y-lo) (* x-lo y-lo)))
                 (else
                  (make-interval (min (* x-lo y-up) (* x-up y-lo))
                                 (max (* x-lo y-lo) (* x-up y-up)))))))))
 
练习 2.12:
Define a constructor make-center-percent that takes a center and a percentage tolerance and produces
the desired interval. You must also define a selector percent that produces the percentage tolerance
for a given interval. The center selector is the same as the one shown above.
我的解答:
(define (make-center-width c w)
  (make-interval (- c w) (+ c w)))

(define (center z)
  (/ (+ (lower-bound z)
        (upper-bound z))
     2))

(define (width z)
  (/ (- (upper-bound z)
        (lower-bound z))
     2))

(define (make-center-percent center percent)
  (make-center-width center (* center percent)))

(define (percent z)
  (let ((c (center z))
        (w (width z)))
    (/ w c)))
 
练习 2.13:
Show that under the assumption of small percentage tolerances there is a simple formula for the
approximate percentage tolerance of the product of two intervals in terms of the tolerances of the
factors. You may simplify the problem by assuming that all numbers are positive.
我的解答:
已知任意两个区间 I1, I2,其中心点和误差值分别为 c1, t1 和 c2,t2,
则 I1 = [c1*(1-0.5t1), (c1*(1+0.5)t1], I2 = [c2*(1-0.5t2), c2*(1+0.5)t2]
因为上下界均为正,所以
I1*I2 = [c1*(1-0.5)t1*c2*(1-0.5)t2, c1*(1+0.5)t1*c2(1+0.5)t2]
      = [c1*c2*(1-0.5(t1+t2)+0.25t1t2), c1*c2*(1+0.5(t1+t2)+0.25t1t2)]
因为 t1, t2 很小,所以 t1*t2 可以忽略不计,
所以 I1*I2 = [c1*c2*(1-0.5(t1+t2)), c1*c2*(1+0.5(t1+t2))]
以上可知:在误差为极小的百分数条件下,两区间(上下界均为正)乘积所得误差值为这两个区间误差值之和。
 
练习 2.14:
Demonstrate that Lem is right. Investigate the behavior of the system on a variety of arithmetic
expressions. Make some intervals A and B, and use them in computing the expressions A/A and A/B. You
will get the most insight by using intervals whose width is a small percentage of the center
value. Examine the results of the computation in center-percent form (see Exercise 2-12).
 
练习 2.15:
Eva Lu Ator, another user, has also noticed the different intervals computed by different but
algebraically equivalent expressions. She says that a formula to compute with intervals using
Alyssa's system will produce tighter error bounds if it can be written in such a form that no
variable that represents an uncertain number is repeated. Thus, she says, par2 is a “better” program
for parallel resistances than par1. Is she right? Why?
 
练习 2.16:
Explain, in general, why equivalent algebraic expressions may lead to different answers. Can you
devise an interval-arithmetic package that does not have this shortcoming, or is this task
impossible? (Warning: This problem is very difficult.)
 
以上三题还没有做出来,先放一放,以后再回来做。
 
net worth 说:
Dec 11, 2023 09:00:50 PM

All the basic information about every celebrity is available now on the largest database of idol net worth where you can find all the information and net worth of a singer, actor, businessman...

seo service UK 说:
Jan 13, 2024 10:29:50 PM

I just want to let you know that I just check out your site and I find it very interesting and informative..


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter