乐正

Actions speak louder than words.

Sicp-ex1-33

问题

你可以通过引进一个处理被组合项的过滤器(filter)概念,写出一个比accumulate更一般 的版本。也就是说,在计算过程中,只组合起由给定范围得到的项里的那些满足特定条件的 项。这样得到的filtered-accumulate抽象取与上面累积过程同样的参数,再加上一个另 外的描述有关过滤器的谓词参数。请写出filtered-accumulate作为一个过程,说明如何用 filtered-accumulate表达以下内容:

a) 求出在区间$a$和$b$中所有素数之和(假定你已经写出了谓词prime?)。
b) 小于$n$的所有与$n$互素的正整数(即所有满足$GCD(i,n) = 1$的整数$i<n$)之乘积。

解答

练习1.33 (ex1-33.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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
(define (filtered-accumulate combiner null-value filter term a next b)
  (define (iter a result)
    (if (> a b)
        result
        (if (filter a)
            (iter
             (next a)
             (combiner (term a)
                       result))
            (iter
             (next a)
             result))))

  (iter a null-value))

;;; Load 练习1.28 miller-rabin-test

;;; 实现在区间a和b之间所有素数之和
(define (primes-sum a b)

  (define (fast-prime? n)
    (miller-rabin-prime? n 10))

  (define (indentity x) x)

  (define (next x)
    (if (even? x)
        (+ x 1)
        (+ x 2)))

  (filtered-accumulate + 0 fast-prime? indentity a next b))

;;; GCD
(define (gcd a b)
  (if (= b 0)
      a
      (gcd b (remainder a b))))

;;; 实现小于n所有与n互素的正整数之乘积
(define (coprimes-product n)
  (define (filter i)
    (= 1 (gcd i n)))

  (define (indentity x) x)

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

  (filtered-accumulate * 1 filter indentity 1 next n))

测试

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
;;; 测试区间a和b中所有素数之和
(primes-sum 2 100)
;Value: 1060

(primes-sum 3 1000)
;Value: 76125

(primes-sum 2 4)
;Value: 5

;;; 测试小于n的所有与n互素的正整数之乘积
(coprimes-product 3)
;Value: 2

(coprimes-product 4)
;Value: 3

(coprimes-product 10)
;Value: 189

draft

« sicp-ex1-32 sicp-ex1-34 »

Comments