sicp 习题1.31,1.32,1.33解答

    此题与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

dennis 2007-05-14 15:10 发表评论