SICP 問題1.33

2017/08/30

#sicp

組み合せる項にフィルタ(filter)の考えを入れることで, accumulate(問題1.32)の更に一般的なものが得られる.
つまり範囲から得られて, 指定した条件を満した項だけを組み合せる.
出来上ったfiltered-accumulate抽象は, accumulate と同じ引数の他, フィルタを指定する一引数の述語をとる.
filtered-accumulateを手続きとして書け.
filtered-accumulateを使い, 次をどう表現するかを示せ.
a. 区間a, bの素数の二乗の和(prime?述語は持っていると仮定する.)
b. nと互いに素で, nより小さい正の整数(つまりi < nでGCD(i, n)=1なる全整数i)の積

まずaccumulateはこちら。

(define (accumulate combiner null-value term a next b)
  (define (iter a result)
    (if (> a b)
        result
        (iter (next a) (combiner (term a) result))))
  (iter a null-value))

filterで指定した条件に合致したものだけcombineしていけばよいので、下記になるのかな。

(define (filtered-accumulate filter combiner null-value term a next b)
  (define (iter a result)
    (if (> a b)
        result
        (iter (next a)
              (if (filter a)
                  (combiner (term a) result)
                  result))))
  (iter a null-value))

a.区間a, bの素数の二乗の和

(prime?述語は持っていると仮定する.)

とのことなので、prime?はあるものと仮定するので、自分で書かずにネットから拾ってきた。

(define (double x) (* x x))
(define (inc n) (+ n 1))
(define (prime? number)
  (cond
      ((< number 2) #f)
      ((< number 4) #t)
      ((even? number) #f)
      (else
          (let loop((i 3))
              (if (<= i (sqrt number))
                  (if (= (modulo number i) 0)
                      #f
                      (loop (+ i 2)))
                  #t)))))

(print (filtered-accumulate prime? + 0 double 0 inc 10))
; => 87

できたっぽいかな？

b. nと互いに素で, nより小さい正の整数の積

GCDは前のほうで手続きが書いてあったのでそれを持ってくる。

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

(define (calc n a b)
  (define (filter i)
    (if (and (< i n) (= (gcd i n) 1)) #t #f))
  (filtered-accumulate filter * 1 + a inc b))

(print (calc 5 1 10))
; => 24

あってるのかわからん。