SICP: Exercise 1.31

問題 1.31

1. sum 手続きは高階手続きとして書ける、同様な数多い抽象の最も単純なものに過ぎない。与えられた範囲の点での関数値の積を返す product という似た手続きを書け。product を使って、factorial を定義せよ。また式 $$ \frac{\pi}{4} = \frac{2 \cdot 4 \cdot 4 \cdot 6 \cdot 6 \cdot 8 \cdots}{3 \cdot 3 \cdot 5 \cdot 5 \cdot 7 \cdot 7 \cdots} $$ によって \( \pi \) の近似値を計算するのに product を使え。

2. 上の product が再帰的プロセスを生成するなら、反復的プロセスを生成するものを書け。反復的プロセスを生成するなら、再帰的プロセスを生成するものを書け。

「計算機プログラムの構造と解釈 第二版 1.3.1 引数としての手続き」より

a

和と同様に積 $$ \prod_{n = a}^b\,f(n) = f(a) \times \cdots \times f(b) $$ を表す手続きを書けばよい。

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

ochaochaocha3.hateblo.jp

階乗

階乗は sum-integers と同様になる。

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

(factorial 0)
; 1
(factorial 1)
; 1
(factorial 5)
; 120
(factorial 10)
; 3628800

π の近似値

\( \pi \) の近似値は、初見時は一般項の表現に困ったが、 $$ \frac{2 \cdot 4}{3 \cdot 3} \cdot \frac{4 \cdot 6}{5 \cdot 5} \cdot \frac{6 \cdot 8}{7 \cdot 7} \cdots $$ と見たら分かりやすくなった。左上の数を \( k \) とおくと $$ \frac{k(k + 2)}{(k + 1)^2} $$ と表せる。このように表現したときは、\( k \) に 2 を加えて次の項を作る。

(define (pi-prod n)
  (define (pi-term x)
    (/ (* x (+ x 2.0))
       (square (+ x 1))))
  (define (pi-next x)
    (+ x 2))
  (product pi-term 2 pi-next n))

実際に近似値を計算すると

(* 4 (pi-prod 10000000)) ; 少し時間がかかる
; 3.1415928106708866

3.141592 まで合った。

b

a の product は再帰的プロセスなので反復的プロセスで書く。問題 1.30 と同様に書けばよい。

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

ochaochaocha3.hateblo.jp