Chinaunix

标题: SICP 习题参考答案 3.1 [打印本页]

作者: win_hate 时间: 2008-10-05 11:12
标题: SICP 习题参考答案 3.1

此帖为 SICP 章节 3.1 的参考答案。为保持可读性，请勿直接在本帖讨论。讨论请另开新帖。

本节电子版：[Assignment and Local State]
答案目录：[点这里]

作者: win_hate 时间: 2008-10-05 11:17
标题: Exercise 3.1.
Exercise 3.1. An accumulator is a procedure that is called repeatedly with a single numeric argument and accumulates its arguments into a sum. Each time it is called, it returns the currently accumulated sum. Write a procedure make-accumulator that generates accumulators, each maintaining an independent sum. The input to make-accumulator should specify the initial value of the sum; for example

(define A (make-accumulator 5))
(A 10)
15
(A 10)
25

作者: win_hate 时间: 2008-10-05 11:18
标题: Exercise 3.1. 答案

(define (make-accumulator init)
(lambda (x)
(set! init (+ init x))
init))

复制代码

作者: win_hate 时间: 2008-10-05 11:25
标题: Exercise 3.2.
Exercise 3.2. In software-testing applications, it is useful to be able to count the number of times a given procedure is called during the course of a computation. Write a procedure make-monitored that takes as input a procedure, f, that itself takes one input. The result returned by make-monitored is a third procedure, say mf, that keeps track of the number of times it has been called by maintaining an internal counter. If the input to mf is the special symbol how-many-calls?, then mf returns the value of the counter. If the input is the special symbol reset-count, then mf resets the counter to zero. For any other input, mf returns the result of calling f on that input and increments the counter. For instance, we could make a monitored version of the sqrt procedure:

(define s (make-monitored sqrt))

(s 100)
10

(s 'how-many-calls?)
1

作者: win_hate 时间: 2008-10-05 11:25
标题: Exercise 3.2. 答案

(define (make-monitored f)
(let ((cnt 0))
(lambda (x)
(cond ((eq? x 'how-many-calls?) cnt)
(else (set! cnt (+ cnt 1))
(f x))))))

复制代码

作者: win_hate 时间: 2008-10-05 12:00
标题: Exercise 3.3.
Exercise 3.3. Modify the make-account procedure so that it creates password-protected accounts. That is, make-account should take a symbol as an additional argument, as in

(define acc (make-account 100 'secret-password))

The resulting account object should process a request only if it is accompanied by the password with which the account was created, and should otherwise return a complaint:

((acc 'secret-password 'withdraw) 40)
60

((acc 'some-other-password 'deposit) 50)
"Incorrect password"

作者: win_hate 时间: 2008-10-05 12:01

(define (make-account balance password)
(define (withdraw amount)
(if (>= balance amount)
(begin (set! balance (- balance amount))
balance)
"Insufficient funds"))
(define (deposit amount)
(set! balance (+ balance amount))
balance)
(define (dispatch pass m)
(cond ((not (eq? password pass)) (lambda (x) "Incorrect password"))
((eq? m 'withdraw) withdraw)
((eq? m 'deposit) deposit)
(else (error "Unkonwn request -- MAKE-ACCOUNT" m))))
dispatch)

复制代码

作者: win_hate 时间: 2008-10-05 12:42
标题: Exercise 3.4.
Exercise 3.4. Modify the make-account procedure of exercise 3.3 by adding another local state variable so that, if an account is accessed more than seven consecutive times with an incorrect password, it invokes the procedure call-the-cops.

作者: win_hate 时间: 2008-10-05 12:43
标题: Exerciese 3.4. 答案

(define (make-account balance password)
(let ((cnt 0))
(define (call-the-cap)
(lambda (x) "Cap Called"))
(define (withdraw amount)
(if (>= balance amount)
(begin (set! balance (- balance amount))
balance)
"Insufficient funds"))
(define (deposit amount)
(set! balance (+ balance amount))
balance)
(define (dispatch pass m)
(cond ((= cnt 7) (lambda (x) "Account Locked"))
((not (eq? password pass)) (begin
(set! cnt (+ cnt 1))
(if (= cnt 7) (call-the-cap)
(lambda (x) "Incorrect password"))))
(else (set! cnt 0)
(cond ((eq? m 'withdraw) withdraw)
((eq? m 'deposit) deposit)
(else (error "Unkonwn request -- MAKE-ACCOUNT" m))))))
dispatch))

复制代码

[ 本帖最后由 win_hate 于 2008-12-6 22:00 编辑 ]

作者: win_hate 时间: 2008-12-06 22:31
标题: Exercise 3.5.
Exercise 3.5. Monte Carlo integration is a method of estimating definite integrals by means of Monte Carlo simulation. Consider computing the area of a region of space described by a predicate P(x, y) that is true for points (x, y) in the region and false for points not in the region. For example, the region contained within a circle of radius 3 centered at (5, 7) is described by the predicate that tests whether (x - 5)^2 + (y - 7)^2< 32. To estimate the area of the region described by such a predicate, begin by choosing a rectangle that contains the region. For example, a rectangle with diagonally opposite corners at (2, 4) and (8, 10) contains the circle above. The desired integral is the area of that portion of the rectangle that lies in the region. We can estimate the integral by picking, at random, points (x,y) that lie in the rectangle, and testing P(x, y) for each point to determine whether the point lies in the region. If we try this with many points, then the fraction of points that fall in the region should give an estimate of the proportion of the rectangle that lies in the region. Hence, multiplying this fraction by the area of the entire rectangle should produce an estimate of the integral.

Implement Monte Carlo integration as a procedure estimate-integral that takes as arguments a predicate P, upper and lower bounds x1, x2, y1, and y2 for the rectangle, and the number of trials to perform in order to produce the estimate. Your procedure should use the same monte-carlo procedure that was used above to estimate

. Use your estimate-integral to produce an estimate of by measuring the area of a unit circle.

You will find it useful to have a procedure that returns a number chosen at random from a given range. The following random-in-range procedure implements this in terms of the random procedure used in section 1.2.6, which returns a nonnegative number less than its input.8

(define (random-in-range low high)
(let ((range (- high low)))
(+ low (random range))))

[ 本帖最后由 win_hate 于 2008-12-6 22:33 编辑 ]

作者: win_hate 时间: 2008-12-06 22:34
标题: Exerciese 3.5. 答案

(define (monte-carlo trials experiment)
(define (iter trials-remaining trials-passed)
(cond ((= trials-remaining 0)
(/ trials-passed trials))
((experiment)
(iter (- trials-remaining 1) (+ trials-passed 1)))
(else
(iter (- trials-remaining 1) trials-passed))))
(iter trials 0))
(define (random-in-range low high)
(let ((range (- high low)))
(+ low (random range))))
(define (test x y)
(<= (+ (* x x) (* y y)) 1))
(define (estimate-integral test x1 x2 y1 y2 n)
(let ((f (lambda ()
(test (random-in-range x1 x2)
(random-in-range y2 y1)))))
(* (monte-carlo n f) (* (- x2 x1) (- y1 y2)))))

复制代码

测试

guile> (estimate-integral test -1.0 1.0 1.0 -1.0 10000)
3.1512
guile> (estimate-integral test -1.0 1.0 1.0 -1.0 10000)
3.1364
guile> (estimate-integral test -1.0 1.0 1.0 -1.0 10000)
3.1496
guile> (estimate-integral test -1.0 1.0 1.0 -1.0 10000)
3.1244
guile> (estimate-integral test -1.0 1.0 1.0 -1.0 10000)
3.1556
guile> (estimate-integral test -1.0 1.0 1.0 -1.0 10000)
3.12
guile> (estimate-integral test -1.0 1.0 1.0 -1.0 10000)
3.1508

复制代码

[ 本帖最后由 win_hate 于 2008-12-6 22:37 编辑 ]

作者: win_hate 时间: 2008-12-06 22:37
标题: Exerciese 3.6.
Exercise 3.6. It is useful to be able to reset a random-number generator to produce a sequence starting from a given value. Design a new rand procedure that is called with an argument that is either the symbol generate or the symbol reset and behaves as follows: (rand 'generate) produces a new random number; ((rand 'reset) <new-value>) resets the internal state variable to the designated <new-value>. Thus, by resetting the state, one can generate repeatable sequences. These are very handy to have when testing and debugging programs that use random numbers.

作者: win_hate 时间: 2008-12-06 22:48
书本这个题目出得不是太好。因为在书里没有介绍随机数生成的理论。所以要做这个题目有两个选择，一是用 scheme 中现成的函数，另一个选择是自己去学一下随机数生成算法。

在这里，我使用线性同余来产生随机数。公式为

x(0)=1
x(n+1)=x(n)*16807 (mod 2147483647)

复制代码

(define (make-random)
(let ((state 1)
(a 16807)
(m 2147483647))
(define rand
(lambda (cmd)
(cond ((eq? cmd 'generate)
(let ((r (modulo (* a state) m)))
(set! state r)
r))
((eq? cmd 'reset)
(lambda (seed)
(set! state seed)))
(else
(error "Not implement ---" cmd)))))
rand))
(define rand (make-random))

复制代码

测试：

> (map rand (list 'generate 'generate 'generate 'generate))
(16807 282475249 1622650073 984943658)
> ((rand 'reset) 1) ;; 把内部状态重设为 1
> (map rand (list 'generate 'generate 'generate 'generate))
(16807 282475249 1622650073 984943658) ;; 产生相同的序列
> ((rand 'reset) 1622650073) ;; 把内部状态设置为 1622650073，下一个会是 984943658
> (rand 'generate)
984943658

复制代码

[ 本帖最后由 win_hate 于 2008-12-6 22:50 编辑 ]

作者: win_hate 时间: 2008-12-10 13:08
标题: Exercise 3.7.
Exercise 3.7. Consider the bank account objects created by make-account, with the password modification described in exercise 3.3. Suppose that our banking system requires the ability to make joint accounts. Define a procedure make-joint that accomplishes this. Make-joint should take three arguments. The first is a password-protected account. The second argument must match the password with which the account was defined in order for the make-joint operation to proceed. The third argument is a new password. Make-joint is to create an additional access to the original account using the new password. For example, if peter-acc is a bank account with password open-sesame, then

(define paul-acc
(make-joint peter-acc 'open-sesame 'rosebud))

will allow one to make transactions on peter-acc using the name paul-acc and the password rosebud. You may wish to modify your solution to exercise 3.3 to accommodate this new feature.

作者: win_hate 时间: 2008-12-10 13:21
标题: Exercise 3.7. 答案

(define (make-account balance password)
(define (withdraw amount)
(if (>= balance amount)
(begin (set! balance (- balance amount))
balance)
"Insufficient funds"))
(define (deposit amount)
(set! balance (+ balance amount))
balance)
(define (share newpass)
(dispatch newpass))
(define (dispatch password)
(lambda (pass m)
(cond ((not (eq? password pass)) (lambda (x) "Incorrect password"))
((eq? m 'withdraw) withdraw)
((eq? m 'deposit) deposit)
((eq? m 'share) share)
(else (error "Unkonwn request -- MAKE-ACCOUNT" m)))))
(dispatch password))
(define (make-joint acc pass newpass)
((acc pass 'share) newpass))

复制代码

在 3.3 的基础上修改得到的。为 dispatch 增加了局部变量。

测试：

> (define acc1 (make-account 100 'xxx))
> (define acc2 ((acc1 'xxx 'share) 'yyy))
> (define acc3 ((acc1 'xxx 'share) 'zzz))
> (define acc4 ((acc3 'zzz 'share) 'www))
> (define t1 (acc1 'xxx 'withdraw))
> (define t2 (acc2 'yyy 'withdraw))
> (define t3 (acc3 'zzz 'withdraw))
> (define t4 (acc4 'www 'withdraw))
> (t1 10)
90
> (t2 10)
80
> (t3 10)
70
> (t4 10)
60
> (define p4 (acc4 'www 'deposit))
> (define p3 (acc3 'zzz 'deposit))
> (p4 1000)
1060
> (p3 10000)
11060

复制代码

[ 本帖最后由 win_hate 于 2008-12-10 21:16 编辑 ]

作者: win_hate 时间: 2008-12-10 13:22
标题: Exercise 3.8.
Exercise 3.8. When we defined the evaluation model in section 1.1.3, we said that the first step in evaluating an expression is to evaluate its subexpressions. But we never specified the order in which the subexpressions should be evaluated (e.g., left to right or right to left). When we introduce assignment, the order in which the arguments to a procedure are evaluated can make a difference to the result. Define a simple procedure f such that evaluating (+ (f 0) (f 1)) will return 0 if the arguments to + are evaluated from left to right but will return 1 if the arguments are evaluated from right to left.

作者: win_hate 时间: 2008-12-10 13:25
标题: 3.8 答案

(define f
(let ((s 1))
(lambda (x)
(set! s (* s x))
s)))

复制代码

> (load "3.8.scm")
> (+ (f 0) (f 1))
0

复制代码

> (load "3.8.scm")
> (+ (f 1) (f 0))
1

复制代码

作者: win_hate 时间: 2008-12-10 13:25
本节完。

欢迎光临 Chinaunix (http://bbs.chinaunix.net/)