庄周梦蝶

生活、程序、未来
   :: 首页 ::  ::  :: 聚合  :: 管理

sicp 习题1.31,1.32,1.33解答

Posted on 2007-05-14 15:10 dennis 阅读(685) 评论(0)  编辑  收藏
    此题与1.32、1.33是一个系列题,没什么难度,只不过把sum的加改成乘就可以了,递归与迭代版本相应修改即可:
;(define (product term a next b)
;  (
if (> a b)
;      
1
;      (
* (term a) (product term (next a) next b))))
(define (product
-iter term a next b result)
  (
if (> a b)
      result
      (product
-iter term (next a)  next b (* result (term a)))))
   分号注释的是递归版本。利用product过程生成一个计算pi的过程,也是很简单,通过观察公式的规律即可得出:
(define (product term a next b)
  (product
-iter term a next b 1))
(define (inc x) (
+ x 2))
(define (pi
-term n)(/ (* (- n 1) (+ n 1)) (* n n)))
(define (product
-pi a b)
   (product pi
-term a inc b))
测试一下:

> (* 4 (product-pi 3 1000))
3.1431638424191978569077933

再来看习题1.32,如果说sum和product过程是一定程度的抽象,将对累积项和下一项的处理抽象为过程作为参数提取出来,那么这个题目要求将累积的操作也作为参数提取出来,是更高层次的抽象,同样也难不倒我们:
(define (accumulate combiner null-value term a next b)
  (
if (> a b)
      null
-value
      (combiner (term a) (accumulate combiner null
-value term (next a) next b))))

OK,其中combiner是进行累积的操作,而null-value值基本值。现在改写sum和product过程,对于sum过程来说,累积的操作就是加法,而基本值当然是0了:
(define (sum term a next b)
  (accumulate 
+ 0 term a next b))

而对于product,累积操作是乘法,而基本值是1,因此:
(define (product term a next b)
  (accumulate 
* 1 term a next b))

测试一下过去写的那些测试程序,比如生成pi的过程,可以验证一切正常!

上面的accumulate过程是递归版本,对应的迭代版本也很容易改写了:
(define (accumulate-iter combiner term a next b result)
  (
if (> a b)
      result
      (accumulate
-iter combiner term (next a) next b (combiner result (term a)))))
(define (accumulate  combiner null
-value term a next b)
  (accumulate
-iter combiner term a next b null-value))

再看习题1.33,在accumulate的基础上多增加一个filter的参数(也是一个过程,用于判断项是否符合要求),在accumulate的基础上稍微修改下,在每次累积之前进行判断即可:

(define (filtered-accumulate combiner null-value term a next b filter)
  (cond ((
> a b) null-value)
        ((filter a) (combiner (term a) (filtered
-accumulate combiner null-value term (next a) next b filter))) 
        (
else (filtered-accumulate combiner null-value term (next a) next b filter))))

比如,求a到b中的所有素数之和的过程可以写为(利用以前写的prime?过程来判断素数):
(define (sum-primes a b)
  (filtered
-accumulate + 0 identity a inc b prime?))

测试一下:
> (sum-primes 2 4)
5
> (sum-primes 2 7)
17
> (sum-primes 2 11)
28
> (sum-primes 2 100)
1060


只有注册用户登录后才能发表评论。


网站导航: