SICP 問題 1.31 （抽象的総積演算）

SICP Scheme

休み時間のうちに・・・

【問題】

a)
sum手続きは高階手続きとして書ける、同様な数多い抽象の最も単純なものに過ぎない。
与えられた範囲の点での関数値の積を返すproductという似た手続きを書け。
productを使って、factorialを定義せよ。
また式、



π   2・4・4・6・6・8・・・

— = ———————————

４   3・3・5・5・7・7・・・
によってπの近似値を計算するのにproductを使え

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

【解答】

和を求めるのがコレ。

(define (sum term a next b)
  (define (iter a result)
    (if (> a b)
        result
        (iter (next a) (+ result (term a)))))
  (iter a 0))

ならば積を求めるのは・・・

;末尾再帰（反復）バージョンのproduct手続き）
(define (product term a next b)
  (define (iter a result)
    (if (> a b)
        result
	;resultの計算を+でなく*に変更
        (iter (next a) (* result (term a)))))
  ;初期値を1に変更
  (iter a 1))

演算子とiterの初期値変えただけだけど。

で、これを使ってfactorial（階乗）を求める。

(define (factorial n)
  (product (lambda (x)
	     x)
	   1
	   (lambda (x)
	     (+ 1 x)) n))

実行してみると・・・



gosh> (factorial 1)

1

gosh> (factorial 2)

2

gosh> (factorial 3)

6

gosh> (factorial 4)

24

gosh> (factorial 5)

120

gosh> (factorial 6)

720

gosh> (factorial 7)

5040

gosh>
ちゃんと計算してますな。
さてつぎ。π/4の計算。(分子 分母)とみなすとこんな感じで変化していく。


n=0 2/3

n=1 4/3

n=2 4/5

n=3 6/5

n=4 6/7

n=5 8/7
これから推測するに、termに相当する手続きはどんな感じになるだろう。


・偶数の時は分母が大きい

・奇数の時は分子が大きい

・大きい方の数字はn+3になっている。

・小さい方の数字はn+2になっている。
まんま実装してみるとこんな感じ。

(define (term n)
  (if (even? n)
      (/ (+ n 2) (+ n 3))
      (/ (+ n 3) (+ n 2))))

で、次の項の元ネタになる値はこれで取れる。

(define (next n)
  (+ 1 n))

一つずつインクリメントしていくだけでＯＫ。
さて、これで与えられた式の積算を行う準備ができたのでやってみよう。

(define (pi-calc accuracy)
  ;理解しやすさの為に内部手続きとして定義
  (define (term n)
    (if (even? n)
	(/ (+ n 2) (+ n 3))
	(/ (+ n 3) (+ n 2))))
  ;理解しやすさの為に内部手続きとして定義
  (define (next n)
    (+ 1 n))
  ;上記で定義した手続きを渡す。わかりやすさの為、結果を4倍して小数値にしてみた。
  (exact->inexact (* 4 (product term 0 next accuracy))))

実行してみると



gosh> (pi-calc 1000)

3.140026946105016

gosh> (pi-calc 2000)

3.140808529664475

gosh>
精度を上げると近づいてるっぽいけど、なんだかすごく遅い。
全部マジメに計算してるからだろうけど、他にいいアルゴリズムがあるのかなぁ。


あ。あと、productの非末尾再帰なヤツを。

;非末尾再帰バージョンのproduct手続き）
(define (product term a next b)
  (if (> a b)
      1
      (* (term a)
	 (product term (next a) next b))))

結果は同じ。



gosh> (pi-calc 1000)

3.140026946105016

gosh> (pi-calc 2000)

3.140808529664475

gosh>