乐正

Actions speak louder than words.

Sicp-ex1-32

问题

a) 请说明,sumproduct都是另一称为accumulate的更一般概念的特殊情况,accumulate 使用某些一般性的积累函数组合起一系列项:

1
(accumulate combiner null-value term a next b)

accumulate取的是与sumproduct一样的项和范围描述参数,再加上一个(两个参数 的)combiner过程,它描述如何将当前项与前面各项的积累结果组合起来,另外还有一个 null-value参数,它描述在所有的项都用完时的基本值。请写出accumulate,并说明我 们能怎样基于简单地调用accumulate,定义出sumproduct来。

b) 如果你的accumulate过程生成的是一个递归计算过程,那么请写出生成迭代计算过程的过 程。如果它生成一个迭代计算过程,请写出一个生成递归计算过程的过程。

解答(a)

迭代accumulate过程 (ex1-32-a.scm) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
;;; 迭代的
(define (accumulate combiner null-value term a next b)
  (define (iter a result)
    (if (> a b)
        result
        (iter (next a) (combiner (term a) result))))

  (iter a null-value))

;;; 使用accumulate定义sum
(define (sum term a next b)
  (accumulate + 0 term a next b))

;;; 使用accumulate定义product
(define (product term a b next)
  (accumulate * 1 term a next b))

测试

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
(factorial 10)
;Value: 3628800

(factorial 6)
;Value: 720

(factorial 3)
;Value: 6

(define (indentity x) x)

(define (next x) (+ x 1))

(sum indentity 1 next 10)
;Value: 55

(sum indentity 1 next 100)
;Value: 5050

解答(b)

递归accumulate过程 (ex1-32-b.scm) download
1
2
3
4
5
(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))))

测试

1
2
3
4
5
(sum indentity 1 next 100)
;Value: 5050

(sum indentity 1 next 10)
;Value: 55

draft

« sicp-ex1-31 sicp-ex1-33 »

Comments