SICP 习题参考答案 3.1

win_hate

1. 
   
2. (define (monte-carlo trials experiment)
   
3.   (define (iter trials-remaining trials-passed)
   
4.     (cond ((= trials-remaining 0)
   
5.            (/ trials-passed trials))
   
6.           ((experiment)
   
7.            (iter (- trials-remaining 1) (+ trials-passed 1)))
   
8.           (else
   
9.            (iter (- trials-remaining 1) trials-passed))))
   
10.   (iter trials 0))
    
11.             
    
12. (define (random-in-range low high)
    
13.   (let ((range (- high low)))
    
14.     (+ low (random range))))
    
15. 
    
16. (define (test x y)
    
17.   (<= (+ (* x x) (* y y)) 1))
    
18. 
    
19. (define (estimate-integral test x1 x2 y1 y2 n)
    
20.   (let ((f (lambda ()
    
21.              (test (random-in-range x1 x2)
    
22.                    (random-in-range y2 y1)))))
    
23.     (* (monte-carlo n f) (* (- x2 x1) (- y1 y2)))))
    

复制代码

测试

1. 
   
2. guile> (estimate-integral test -1.0 1.0 1.0 -1.0 10000)
   
3. 3.1512
   
4. guile> (estimate-integral test -1.0 1.0 1.0 -1.0 10000)
   
5. 3.1364
   
6. guile> (estimate-integral test -1.0 1.0 1.0 -1.0 10000)
   
7. 3.1496
   
8. guile> (estimate-integral test -1.0 1.0 1.0 -1.0 10000)
   
9. 3.1244
   
10. guile> (estimate-integral test -1.0 1.0 1.0 -1.0 10000)
    
11. 3.1556
    
12. guile> (estimate-integral test -1.0 1.0 1.0 -1.0 10000)
    
13. 3.12
    
14. guile> (estimate-integral test -1.0 1.0 1.0 -1.0 10000)
    
15. 3.1508
    

复制代码

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

win_hate

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

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

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

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

复制代码

1. 
   
2. (define (make-random)
   
3.   (let ((state 1)
   
4.         (a 16807)
   
5.         (m 2147483647))
   
6.     (define rand
   
7.       (lambda (cmd)
   
8.         (cond ((eq? cmd 'generate)
   
9.                (let ((r (modulo (* a state) m)))
   
10.                  (set! state r)
    
11.                  r))
    
12.               ((eq? cmd 'reset)
    
13.                (lambda (seed)
    
14.                  (set! state seed)))
    
15.               (else
    
16.                (error "Not implement ---" cmd)))))
    
17.     rand))
    
18.    
    
19. (define rand (make-random))
    

复制代码

测试：

1. 
   
2. > (map rand (list 'generate 'generate 'generate 'generate))
   
3. (16807 282475249 1622650073 984943658)
   
4. 
   
5. > ((rand 'reset) 1)    ;; 把内部状态重设为 1
   
6. 
   
7. > (map rand (list 'generate 'generate 'generate 'generate))
   
8. (16807 282475249 1622650073 984943658)    ;; 产生相同的序列
   
9. 
   
10. > ((rand 'reset) 1622650073)    ;; 把内部状态设置为 1622650073，下一个会是 984943658
    
11. 
    
12. > (rand 'generate)
    
13. 984943658
    

复制代码

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

win_hate

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

1. 
   
2. (define (make-account balance password)
   
3.   (define (withdraw amount)
   
4.     (if (>= balance amount)
   
5.         (begin (set! balance (- balance amount))
   
6.                balance)
   
7.         "Insufficient funds"))
   
8.   
   
9.   (define (deposit amount)
   
10.     (set! balance (+ balance amount))
    
11.     balance)
    
12. 
    
13.   (define (share newpass)
    
14.     (dispatch newpass))
    
15. 
    
16.   (define (dispatch password)
    
17.     (lambda (pass m)
    
18.       (cond ((not (eq? password pass)) (lambda (x) "Incorrect password"))
    
19.               ((eq? m 'withdraw) withdraw)
    
20.               ((eq? m 'deposit) deposit)
    
21.               ((eq? m 'share) share)
    
22.               (else (error "Unkonwn request -- MAKE-ACCOUNT" m)))))
    
23.   
    
24.   (dispatch password))
    
25.    
    
26. (define (make-joint acc pass newpass)
    
27.   ((acc pass 'share) newpass))
    

复制代码

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

测试：

1. 
   
2. > (define acc1 (make-account 100 'xxx))
   
3. > (define acc2 ((acc1 'xxx 'share) 'yyy))
   
4. > (define acc3 ((acc1 'xxx 'share) 'zzz))
   
5. > (define acc4 ((acc3 'zzz 'share) 'www))
   
6. > (define t1 (acc1 'xxx 'withdraw))
   
7. > (define t2 (acc2 'yyy 'withdraw))
   
8. > (define t3 (acc3 'zzz 'withdraw))
   
9. > (define t4 (acc4 'www 'withdraw))
   
10. > (t1 10)
    
11. 90
    
12. > (t2 10)
    
13. 80
    
14. > (t3 10)
    
15. 70
    
16. > (t4 10)
    
17. 60
    
18. > (define p4 (acc4 'www 'deposit))
    
19. > (define p3 (acc3 'zzz 'deposit))
    
20. > (p4 1000)
    
21. 1060
    
22. > (p3 10000)
    
23. 11060
    

复制代码

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

win_hate

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

1. 
   
2. (define f
   
3.   (let ((s 1))
   
4.     (lambda (x)
   
5.       (set! s (* s x))
   
6.       s)))
   

复制代码

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

复制代码

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

复制代码

win_hate

本节完。