問題1.33

問題1.33 – SICP（計算機プログラムの構造と解釈）その16

2008年11月19日

まず再帰的プロセスのものを書く。

(define (filtered-accumulate combiner null-value filter-pre term a next b)
  (cond ((> a b) null-value)
        ((filter-pre a)
         (combiner
           (term a)
           (filtered-accumulate combiner null-value filter-pre term (next a) next b)))
        (else (filtered-accumulate combiner null-value filter-pre term (next a) next b))))

a. 区間 `a,b`の素数の2乗の和

(define (sum-squared-primes a b)
  (filtered-accumulate + 0 prime? square a inc b))

(sum-squared-primes 1 10)

gosh> sum-squared-primes
gosh> 88

b. `i かつ GCD(i,n)=1 な整数の積`


(define (product-with-gcd n)
  (define (term i) i)
  (define (p i)
    (if (and (> n i) (= (gcd i n) 1))
        #t
        #f))
  (filtered-accumulate * 1 p term 1 inc n))

(product-with-gcd 10)

gosh> product-with-gcd
gosh> 189

次に、反復的プロセスで書いてみる。
(define (filtered-accumulate-re combiner null-value filter-pre term a next b)
  (define (filtered-accumulate-iter a result)
    (cond ((> a b) result)
          ((filter-pre a)
           (filtered-accumulate-iter (next a)
                                     (combiner (term a) result)))
          (else (filtered-accumulate-iter (next a) result))))
  (filtered-accumulate-iter a null-value))

a. 区間 a,bの素数の2乗の和
(define (sum-squared-primes-re a b)
  (filtered-accumulate-re + 0 prime? square a inc b))

(sum-squared-primes-re 1 10)

gosh> sum-squared-primes-re
gosh> 88

b. i かつ GCD(i,n)=1 な整数の積

(define (product-with-gcd-re n)
  (define (term i) i)
  (define (p i)
    (if (and (> n i) (= (gcd i n) 1))
        #t
        #f))
  (filtered-accumulate-re * 1 p term 1 inc n))

(product-with-gcd-re 10)

gosh> product-with-gcd-re
gosh> 189




計算機プログラムの構造と解釈
posted with amazlet at 08.11.07

ジェラルド・ジェイ サスマン ジュリー サスマン ハロルド エイブルソン 
ピアソンエデュケーション 
売り上げランキング: 6542
Amazon.co.jp で詳細を見る