乐正

Actions speak louder than words.

Sicp-ex1-31

问题

a) 过程sum是可以用高阶过程表示的大量类似抽象中最简单的一个。请写出一个类似的, 称为product的过程,它返回在给定范围中各点的某个函数值的乘积。请说明如果和product 定义factorial。另请按照下面公式计算$\pi$的近似值:

$$ \frac {\pi} {4} = \frac {2 \cdot 4 \cdot 4 \cdot 6 \cdot 6 \cdot 8 \cdots} {3 \cdot 3 \cdot 5 \cdot 5 \cdot 7 \cdot 7 \cdots} $$

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

解答(a)

下面是迭代版product过程:

迭代product过程 (ex1-31-a.scm) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
;;; Iterate product
(define (product term a b next)
  (define (iter a result)
    (if (> a b)
        result
        (iter (next a) (* (term a) result))))

  (iter a 1))

(define (factorial n)
  (define (term x) x)

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

  (product term 1 n next))

(define (wallis-pi n)
  (define (dec k) (- k 1))

  (define (inc k) (+ k 1))

  (define (term k)
    (* (/ (dec k) k)
       (/ (inc k) k)))

  (define (next k) (+ k 2.0))

  (* 4 (product term 3.0 n next)))

上述计算$\pi$值的过程由于:

$$ \frac {\pi} {4} = \frac {2 \cdot 4 \cdot 4 \cdot 6 \cdot 6 \cdot 8 \cdots} {3 \cdot 3 \cdot 5 \cdot 5 \cdot 7 \cdot 7 \cdots} = (\frac {2} {3} \cdot \frac {4} {3}) \cdot (\frac {4} {5} \cdot \frac {6} {5}) \cdot (\frac {6} {7} \cdot \frac {8} {7}) \cdots = f(3) \cdot f(5) \cdot f(7) \cdots $$

测试

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

(factorial 3)
;Value: 6

(wallis-pi 100)
;Value: 3.1570301764551676

(wallis-pi 1000)
;Value: 3.1431607055322663

(wallis-pi 10000)
;Value: 3.1417497057380523

解答(b)

下面给出递归版product过程:

迭代product过程 (ex1-31-b.scm) download
1
2
3
4
5
(define (product term a b next)
  (if (> a b)
      1
      (* (term a)
         (product term (next a) b next))))

测试

1
2
3
4
5
(factorial 10)
;Value: 3628800

(factorial 3)
;Value: 6

draft

« sicp-ex1-30 sicp-ex1-32 »

Comments