1.33

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

a)求出在区间a到b中所有素数之和(假定你已经写出了谓词prime?)。

b)小于n的所有与n互素的正整数(即所有满足GCD(i, n)=1的整数i < n)之乘积。

a) 迭代实现:

(define (filtered-accumulate filter combiner null-value term a next b) (define (iter a result) (if (> a b) result (if (filter a) (iter (next a) (combiner result (term a ))) (iter (next a) result)))) (iter a null-value)) (define (always-true x) true) (define (accumulate combiner null-value term a next b) (filtered-accumulate always-true combiner null-value term a next b)) (define (sum term a next b) (accumulate + 0 term a next b)) (define (product term a next b) (accumulate * 1 term a next b)) (define (cube x) (* x x x)) (define (inc x) (+ x 1)) (sum cube 1 inc 10) (define (identity x) x) (product identity 1 inc 10) (define (smallest-divisor n) (find-divisor n 2)) (define (square x) (* x x)) (define (find-divisor n test-divisor) (cond ((> (square test-divisor) n) n) ((divides? test-divisor n) test-divisor) (else (find-divisor n (+ test-divisor 1))))) (define (divides? x y) (= (remainder y x) 0)) (define (prime? x) (= x (smallest-divisor x))) (prime? 1) (prime? 2) (prime? 3) (prime? 4) (define (sum-prime-numbers a b) (filtered-accumulate prime? + 0 identity a inc b)) (sum-prime-numbers 1 10) (+ 1 2 3 5 7)

b) 迭代实现:

(define (filtered-accumulate filter combiner null-value term a next b) (define (iter a result) (if (> a b) result (if (filter a) (iter (next a) (combiner result (term a ))) (iter (next a) result)))) (iter a null-value)) (define (always-true x) true) (define (accumulate combiner null-value term a next b) (filtered-accumulate always-true combiner null-value term a next b)) (define (sum term a next b) (accumulate + 0 term a next b)) (define (product term a next b) (accumulate * 1 term a next b)) (define (cube x) (* x x x)) (define (inc x) (+ x 1)) (sum cube 1 inc 10) (define (identity x) x) (product identity 1 inc 10) (define (smallest-divisor n) (find-divisor n 2)) (define (square x) (* x x)) (define (find-divisor n test-divisor) (cond ((> (square test-divisor) n) n) ((divides? test-divisor n) test-divisor) (else (find-divisor n (+ test-divisor 1))))) (define (divides? x y) (= (remainder y x) 0)) (define (prime? x) (= x (smallest-divisor x))) (prime? 1) (prime? 2) (prime? 3) (prime? 4) (define (sum-prime-numbers a b) (filtered-accumulate prime? + 0 identity a inc b)) (sum-prime-numbers 1 10) (+ 1 2 3 5 7) (define (gcd a b) (if (= b 0) a (gcd b (remainder a b)))) (define (product-prime-numbers-less-than n) (define (prime-to x) (= 1 (gcd x n))) (filtered-accumulate prime-to * 1 identity 1 inc (- n 1))) (product-prime-numbers-less-than 2) (product-prime-numbers-less-than 3) (product-prime-numbers-less-than 4) (product-prime-numbers-less-than 5) (product-prime-numbers-less-than 6) (product-prime-numbers-less-than 7) (product-prime-numbers-less-than 8) (product-prime-numbers-less-than 9) (product-prime-numbers-less-than 10)

results matching ""

    No results matching ""