Edited at

SICP読書録 #11 練習問題1.31 - 練習問題1.33

More than 1 year has passed since last update.

hiroshi-manabe様の日本語訳を使わせてもらいます。

練習問題等はGaucheで実行。

前回はこちら


練習問題1.31

前回定義したsum手続きをちょっと改造して、積を返すようにしてみよう。


_.scm

(define (product term a next b)

(if (> a b)
1
(* (term a)
(product term (next a) next b))))

階乗を計算する手続きは、以下のように定義できる。


_.scm

(define (inc n) (+ n 1))

(define (identity x) x)
(define (factorial n) (product identity 1 inc n))

ところで、$\pi$の近似値は以下の式で得られる。

\frac{\pi}{4} = \frac{2 \cdot 4 \cdot 4 \cdot 6 \cdot 6 \cdot 8 ...}{3 \cdot 3 \cdot 5 \cdot 5 \cdot 7 \cdot 7...}

作ってみよう。後で時間計測もしてみたいので、繰り返し回数を大きめにしてみる。


_.scm

(define (pi)

(define (term x)
(if (even? x) (/ (+ x 2.0) (+ x 1.0))
(/ (+ x 1.0) (+ x 2.0))))
(* (product term 1 inc 1000000) 4))

実行結果。


_.scm

gosh> (time (pi))

;(time (pi))
; real 0.841
; user 0.740
; sys 0.520
3.1415942243828017

続いて、反復プロセス版のproductを作ってみる。


_.scm

(define (product term a next b)

(define (iter a result)
(if (> a b)
result
(iter (next a) (* (term a) result))))
(iter a 1))

pi手続きを再定義して実行してみよう。


_.scm

gosh> (time (pi))

;(time (pi))
; real 0.223
; user 0.220
; sys 0.000
3.141594224382854


練習問題 1.32

前回のsumは繰り返しのたびに和を、そしてさっきのproductは積を計算する手続きだったが、これを抽象化すればもっと一般的な集積関数を定義できる。

combinerとnull-valueという引数を新たに追加するのだ。


_.scm

(define (accumulate combiner null-value term a next b)

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

このaccumulate手続きがあれば、sumやproductを簡単に定義しなおせる。


_.scm

(define (sum term a next b)

(accumulate + 0 term a next b))

(define (product term a next b)
(accumulate * 1 term a next b))


反復プロセス版のaccumulateも定義してみよう。


_.scm

(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))


練習問題 1.33

accumulate手続きにfilterを指定できるようにしよう。指定された条件をパスした値だけが集積されるようにするのだ。


_.scm

(define (filtered-accumulate filter combiner null-value term a next b)

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

このfilterd-accumulate手続きを使って、指定された区間の素数の2乗の和を求めてみる。

だいぶ前に作成したprime?手続きを引っ張り出してこよう。


_.scm

(define (inc n) (+ n 1))

(define (smallest-divisor n) (find-divisor n 2))
(define (find-divisor n test-divisor)
(cond ((> (square test-divisor) n) n)
((divisor? test-divisor n) test-divisor)
(else (find-divisor n (+ test-divisor 1)))))
(define (divisor? a b) (= (remainder b a) 0))
(define (prime? n)
(= n (smallest-divisor n)))

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


実行結果。


_.scm

gosh> (sum-of-prime 1 10)

88 ; 1から10の間にある素数は1,2,3,5,7なので、1+4+9+25+49=88。

続いて、nと違いに素であるn未満の全ての整数の積、というのを求める。

「nと違いに素」とは、nとの最大公約数(GCD)が1になるということ。

だいぶ前に作ったGCD手続きを、また引っ張り出してこよう。


_.scm

(define (inc n) (+ n 1))

(define (identity x) x)

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

(define (product-of-coprime n)
(define (coprime? a)
(= (gcd n a) 1))
(filtered-accumulate coprime? * 1 identity 1 inc n))


実行結果。


_.scm

gosh> (product-of-coprime 10)

189 ; 1*3*7*9=189