练习 1.33

filtered-accumulate 函数比 练习 1.33accumulate 函数多增加一个谓词函数参数 valid? ,用于确保在计算时只对符合条件的项进行累积:

;;; 33-filtered-accumulate.scm

(define (filtered-accumulate combine null-value term a next b valid?)
    (if (> a b)
        null-value
        (let ((rest-terms (filtered-accumulate combine
                                               null-value
                                               term
                                               (next a)
                                               next
                                               b
                                               valid?)))
            (if (valid? a)
                (combine (term a) rest-terms)
                rest-terms))))

a) 计算素数之和

使用 filtered-accumulate 定义 primes-sum ,它加起给定范围内的所有素数,其中素数检测函数 prime? 来自书本 33 页:

;;; 33-primes-sum.scm

(load "33-filtered-accumulate.scm")
(load "p33-prime.scm")

(define (primes-sum a b)
    (filtered-accumulate + 
                         0
                         (lambda (x) x)
                         a
                         (lambda (i) (+ i 1))
                         b
                         prime?))

测试:

1 ]=> (load "33-primes-sum.scm")

;Loading "33-primes-sum.scm"...
;  Loading "33-filtered-accumulate.scm"... done
;  Loading "p33-prime.scm"...
;    Loading "p33-smallest-divisor.scm"...
;      Loading "p33-divides.scm"... done
;      Loading "p33-find-divisor.scm"... done
;    ... done
;  ... done
;... done
;Value: primes-sum

1 ]=> (primes-sum 1 10)     ; 1 + 2 + 3 + 5 + 7 = 18

;Value: 18

b) 计算互素正整数之乘积

根据题目给出的互素性质,使用 gcd 函数写出 coprime? 谓词,用于检查两个整数是否互素:

;;; 33-coprime.scm

(define (coprime? i n)
    (and (< i n)
         (= 1 (gcd i n))))

测试:

1 ]=> (load "33-coprime.scm")

;Loading "33-coprime.scm"... done
;Value: coprime?

1 ]=> (coprime? 2 7)

;Value: #t

1 ]=> (coprime? 2 4)

;Value: #f

然后将这个 coprime?filtered-accumulate 组合起来,写成 product-of-coprimes

;;; 33-product-of-coprimes.scm

(load "33-coprime.scm")
(load "33-filtered-accumulate.scm")

(define (product-of-coprimes n)
    (filtered-accumulate *
                         1
                         (lambda (x) x)
                         1
                         (lambda (i) (+ i 1))
                         n
                         (lambda (x) (coprime? x n))))

注意,因为 coprime? 函数需要两个参数,所以在 accumulate 函数的最后部分,使用了一个 lambda 表达式将参数 n 闭包进去,作为 coprime? 的第二个参数。

测试:

1 ]=> (load "33-product-of-coprimes.scm")

;Loading "33-product-of-coprimes.scm"...
;  Loading "33-filtered-accumulate.scm"... done
;  Loading "33-coprime.scm"... done
;... done
;Value: product-of-coprimes

1 ]=> (product-of-coprimes 10)      ; 1 * 3 * 7 * 9 = 189

;Value: 189

迭代版 filtered-accumulate

;;; 33-iter-filtered-accumulate.scm

(define (filtered-accumulate combine null-value term a next b valid?)
    (define (iter i result)
        (cond ((> i b)
                result)
              ((valid? i)
                (iter (next i) (combine (term i) result)))
              (else 
                (iter (next i) result))))
    (iter a null-value))

测试:

1 ]=> (load "33-iter-filtered-accumulate.scm")

;Loading "33-iter-filtered-accumulate.scm"... done
;Value: filtered-accumulate

1 ]=> (filtered-accumulate +                ; 2 + 4 + 6 + 8 + 10 = 30
               0
               (lambda (x) x)
               1
               (lambda (i) (+ i 1))
               10
               even?)

;Value: 30

讨论

blog comments powered by Disqus