[SICP] 問題 1.17 : 対数的ステップ数の乗算手続き（再帰的プロセス）

本節のべき乗アルゴリズムは, 乗算の繰返しによるべき乗の実行に基づいていた. 同様に整数の乗算を加算の繰返しで実行出来る. 次の乗算手続きは(この言語には加算はあるが, 乗算はないと仮定する)expt手続きに似たものである:

(define (* a b)
  (if (= b 0)
      0
      (+ a (* a (- b 1)))))

このアルゴリズムはbに線形のステップ数をとる. 加算の他に整数を二倍するdouble演算と(偶数の)整数を2で割るhalve演算もあるとしよう. これらを使い, fast-exptと類似の対数的ステップ数の乗算手続きを設計せよ.

p.25のfast-exptを参考に手続きを定義します.

(require (lib "racket/trace.ss"))

(define (double x) (* x 2))

(define (halve x) (/ x 2))

(define (fast-mult a b)
  (cond ((< b 0) (* -1 (fast-mult a (abs b))))
        ((= b 0) 0)
        ((= b 1) a)
        ((even? b) (double (fast-mult a (halve b))))
        (else (+ a (fast-mult a (- b 1))))))

(trace fast-mult)

fast-exptと同じような構造をしています. 負の数をかけた場合と０をかけた場合の扱いを追加しています.

a×bの計算について, 奇数と偶数の場合に分けて, 計算をどのように進めるかを考えます.

1) bが奇数の場合, b = m+1とする. 次の式が成立する.

a×(m+1) = a + (a×m)

2) nが偶数の場合, b = 2mとする. 次の式が成立する.

a×(2m) = double(a×m)

実行結果は次のとおりです.

ようこそ DrRacket, バージョン 6.1 [3m].
言語: Pretty Big; memory limit: 2048 MB.
> (fast-mult 3 45)
>(fast-mult 3 45)
> (fast-mult 3 44)
> >(fast-mult 3 22)
> > (fast-mult 3 11)
> > >(fast-mult 3 10)
> > > (fast-mult 3 5)
> > > >(fast-mult 3 4)
> > > > (fast-mult 3 2)
> > > > >(fast-mult 3 1)
< < < < <3
< < < < 6
< < < <12
< < < 15
< < <30
< < 33
< <66
< 132
<135
135
> (fast-mult 4 0)
>(fast-mult 4 0)
<0
0
> (fast-mult 5 -8)
>(fast-mult 5 -8)
> (fast-mult 5 8)
> >(fast-mult 5 4)
> > (fast-mult 5 2)
> > >(fast-mult 5 1)
< < <5
< < 10
< <20
< 40
<-40
-40
> 

トレースの結果から、対数的ステップ数で計算していることが分かります.

[SICP] 問題 1.16 : べき乗を求める反復的アルゴリズム

fast-exptのように, 逐次平方を使い, 対数的ステップ数の反復的べき乗プロセスを生成する手続きを設計せよ.

(ヒント: (b^n/2)² = (b²)^n/2に注意し, 指数nと底bの他にもう一つの状態変数aを用意する.
状態の移変りで積abⁿが不変であるように状態遷移を定義する.
プロセス開始時にaを1とし, プロセス終了時にaが結果になるようにする.
一般に, 状態の移変りに不変のままの不変量(invariant quantity)を定義する技法は, 反復的アルゴリズムの設計に有用である.)

問題文のヒントを参考に手続きを定義します.

(require (lib "racket/trace.ss"))

(define (square x) (* x x))

(define (fast-expt-iter b n p)
  (cond ((= n 0) p)
        ((even? n) (fast-expt-iter (square b) (/ n 2) p))
        (else (fast-expt-iter b (- n 1) (* b p)))))

(define (fast-expt b n)
  (fast-expt-iter b n 1))

(trace fast-expt-iter)

p×bⁿを考え, pに結果をため込むようにします. 奇数と偶数の場合に分けて, pとbがどのように変化するかを考えます.

1) nが奇数の場合, n = m+1とする. 次の式が成立する.

p×b^m+1 = (p×b)×b^m

右辺のカッコ内の(p×b)が次のステップのpとなる.

2) nが偶数の場合, n = 2mとする. 次の式が成立する.

p×b^2m = p×(b²)^m

右辺のカッコ内の(b²)が次のステップのbとなる.

実行結果は次のとおりです.

ようこそ DrRacket, バージョン 6.1 [3m].
言語: Pretty Big; memory limit: 2048 MB.
> (fast-expt 2 8)
>(fast-expt-iter 2 8 1)
>(fast-expt-iter 4 4 1)
>(fast-expt-iter 16 2 1)
>(fast-expt-iter 256 1 1)
>(fast-expt-iter 256 0 256)
<256
256
> 

トレースの結果から, 反復的プロセスを生成しており, 対数的ステップ数で計算していることが分かります.

[SICP] 問題 1.15 : 正弦の計算

(ラジアンで表す)角度の正弦は, xが十分小さい時, sin x ≒ xの近似と, 正弦の引数の値を小さくするための三角関係式

sin(x) = 3sin(x/3) - 4sin³(x/3)

を使って計算出来る. (この問題のためには, 角度の大きさが0.1ラジアンより大きくなければ「十分小さい」と考える.) この方法は次の手続きに採用してある:

(define (cube x) (* x x x))

(define (p x) (- (* 3 x) (* 4 (cube x))))

(define (sine angle)
   (if (not (> (abs angle) 0.1))
       angle
       (p (sine (/ angle 3.0)))))

a. (sine 12.15)の評価で, 手続きpは何回作用させられたか.

b. (sine a)の評価で, 手続きsineの生成するプロセスが使うスペースとステップ数の増加の程度は(aの関数として)何か.

問題文の手続きを定義します. 手続きpを作用させた回数を調べるためにトレースを使います.

(require (lib "racket/trace.ss"))

(define (cube x) (* x x x))

(define (p x) (- (* 3 x) (* 4 (cube x))))

(define (sine angle)
  (if (not (> (abs angle) 0.1))
      angle
      (p (sine (/ angle 3.0)))))

(trace p)

計算結果は次のとおりです.

ようこそ DrRacket, バージョン 6.1 [3m].
言語: Pretty Big; memory limit: 2048 MB.
> (sin 12.5)
-0.06632189735120068
> (sine 12.5)
>(p 0.051440329218107005)
<0.153776521096694
>(p 0.153776521096694)
<0.4467840153484446
>(p 0.4467840153484446)
<0.9836111719853284
>(p 0.9836111719853284)
<-0.8557060643295382
>(p -0.8557060643295382)
<-0.060813768577286265
-0.060813768577286265
> 

トレースの結果から, pを作用させた回数は５回です.

手続きの定義から, aの値が0.1より大きい時は手続きを再帰的に呼び出し, 次のaの値は1/3になっています. 「十分小さい」と判断する値をe, ステップ数をnとすると次の関係が成り立ちます.

(a/3)n	<	e
a/e	<	3n
log3(a/e)	<	n

このことから, ステップ数の増加の程度はlog aであるといえます. また, 手続きは末尾再帰になっていないため, スペースの増加の程度もステップの増加の程度と同じです.

[SICP] 問題 1.14 : 両替の計算が生成するプロセス

1.2.2節のcount-change手続きが11セントの両替の場合に生成するプロセスを示す木構造を描け. 両替の金額の増加につれ, このプロセスが使うスペースとステップ数の増加の程度は何か.

図を書きます. 木の節点に金額と両替に使えるコインを括弧付きで描いています.

 11 -----------------  -39
(50, 25, 10, 5, 1)     (50, 25, 10, 5, 1)
  |
  |
 11 -----------------  -14
(25, 10, 5, 1)         (25, 10, 5, 1)
  |
  |
 11 --------- 1 ------  -9
(10, 5, 1)  (10, 5, 1) (10, 5, 1)
  |           |
  |           |
  |           1 ------  -4
  |          (5, 1)     (5, 1)
  |           |
  |           |
  |           1  ------  0
  |          (1)        (1)
  |
 11 --------  6 -------  1 ----  -4
 (5, 1)      (5, 1)     (5, 1)   (5, 1)
  |           |          |
  |           |          |
  |           |          1 -----  0
  |           |         (1)      (1)
  |           |          |
  |           |          |
  |           |          1
  |           |         ( )
  |           |
  |           6 -- 5 -- 4 -- 3 -- 2 -- 1 -- 0
  |          (1)  (1)  (1)  (1)  (1)  (1)  (1)
  |           |    |    |    |    |    |
  |           |    |    |    |    |    |
  |           6    5    4    3    2    1
  |          ( )  ( )  ( )  ( )  ( )  ( )
  | 
 11 -- 10 -- 9 -- 8 -- 7 -- 6 -- 5 -- 4 -- 3 -- 2 -- 1 -- 0
 (1)   (1)  (1)  (1)  (1)  (1)  (1)  (1)  (1)  (1)  (1)  (1)
  |     |    |    |    |    |    |    |    |    |    |
  |     |    |    |    |    |    |    |    |    |    |
 11    10    9    8    7    6    5    4    3    2    1
 ( )   ( )  ( )  ( )  ( )  ( )  ( )  ( )  ( )  ( )  ( )

このプロセスが使うスペースとステップ数の増加の程度については後で考えます.

[SICP] 問題 1.13 : フィボナッチ数を求める代数方程式

Φ= (1+√5)/2としてFib(n)がΦⁿ/√5に最も近い整数であることを証明せよ. ヒント: Ψ= (1-√5)/2とする. 帰納法とFibonacci数の定義(1.2.2節参照)を用い, Fib(n)=(Φⁿ-Ψⁿ)/√5を証明せよ.

まず, Fib(n)=(Φⁿ-Ψⁿ)/√5を証明する.

(1) n=1のとき

Fib(1)	=	{Φ1-Ψ1} / √5
	=	{(1+√5)/2 - (1-√5)/2} / √5
	=	2√5 / √5
	=	1

(2) n=2のとき

Φ2	=	{(1+√5)/2}2
	=	{1 + 2√5 + 5} / 4
	=	{2 + 2√5 + 4} / 4
	=	{1 + √5} / 2 + 1
	=	Φ + 1

Ψ2	=	{(1-√5)/2}2
	=	{1 - 2√5 + 5} / 4
	=	{2 - 2√5 + 4} / 4
	=	{1 - √5} / 2 + 1
	=	Ψ + 1

Fib(2)	=	{Φ2-Ψ2} / √5
	=	{(Φ + 1) - (Ψ + 1)} / √5
	=	{Φ - Ψ} / √5
	=	1

(3) n=k, k+1のときFib(n)=(Φⁿ-Ψⁿ)/√5が成立すると仮定する. n=k+2のとき

Fib(k+2)	=	Fib(k+1) + Fib(k)
	=	(Φk+1-Ψk+1)/√5 + (Φk-Ψk)/√5
	=	{(Φk+1+Φk) - (Ψk+1+Ψk)} / √5
	=	{Φk(Φ+1) - Ψk(Ψ+1)} / √5
	=	{ΦkΦ2 - ΨkΨ2} / √5
	=	{Φk+2 - Ψk+2} / √5

(4) 以上より, 1以上の整数nについて, Fib(n)=(Φⁿ-Ψⁿ)/√5が成立する.

次に, Ψ/√5の値を計算する.

Ψ/√5 = (1-√5)/2 ≒ -0.2764

Ψ/√5 < 1/2 であるから, 1以上の整数nについて, Ψⁿ/√5 < 1/2 である.
よって、Fib(n)がΦⁿ/√5に最も近い整数であるといえる.

[SICP] 問題 1.12 : Pascal三角形

次の数のパターンをPascal三角形(Pascal's triangle)という.

       1
      1 1
     1 2 1
    1 3 3 1
   1 4 6 4 1
      ...

三角形の辺上の数はすべて1, 三角形の内部の数はその上の二つの数の和である. 再帰的プロセスの方法でPascal三角形の要素を計算する手続きを書け.

Pascal三角形を計算する手続きを定義します. 結果の確認を容易にするための手続きも定義します.

(define (pascal x y)
  (cond ((= x 0) 1)
        ((= y 0) 1)
        ((= x y) 1)
        (else (+ (pascal (- x 1) (- y 1))
                 (pascal (- x 1) y)))))

;; 1からnまでの整数のリストを求める.
(define (int-list n)
  (define (loop result counter)
    (if (< counter 0)
        result
        (loop (cons counter result) (- counter 1))))
  (loop '() n))

;; 9行分のPascal三角形を求める.
(map (lambda (x)
       (map (lambda (y) (pascal x y)) (int-list x)))
     (int-list 8))

実行した結果は次のとおりです.

ようこそ DrRacket, バージョン 6.1 [3m].
言語: Pretty Big; memory limit: 2048 MB.
((1)
 (1 1)
 (1 2 1)
 (1 3 3 1)
 (1 4 6 4 1)
 (1 5 10 10 5 1)
 (1 6 15 20 15 6 1)
 (1 7 21 35 35 21 7 1)
 (1 8 28 56 70 56 28 8 1))
> 

Pascal三角形を計算できていることを確認できます.

[SICP] 問題 1.11 : f(n)=f(n-1)+2f(n-2)+3f(n-3)

n<3に対して

  f(n)=n, n ≥ 3に対してf(n)=f(n - 1) + 2f(n - 2) + 3f(n - 3)

なる規則で定義する関数fがある. 再帰的プロセスの方法でfを計算する手続きを書け. 反復的プロセスの方法でfを計算する手続きを書け.

Fibonacci数を計算する手続きを参考にして問題文の関数fを定義します.

(require (lib "racket/trace.ss"))

(define (f-r n)
  (if (< n 3)
      n
      (+ (* 1 (f-r (- n 1)))
         (* 2 (f-r (- n 2)))
         (* 3 (f-r (- n 3))))))

(define (f-iter counter x y z)
  (if (= 0 counter)
      z
      (f-iter (- counter 1)
              (+ x (* 2 y) (* 3 z))
              x 
              y)))

(define (f-i n)
  (f-iter n 2 1 0))

;;(trace f-r f-iter)

実行して, 結果を確認します.

ようこそ DrRacket, バージョン 6.1 [3m].
言語: Pretty Big; memory limit: 2048 MB.
> (map f-r '(0 1 2 3 4 5 6 7))
(0 1 2 4 11 25 59 142)
> (map f-i '(0 1 2 3 4 5 6 7))
(0 1 2 4 11 25 59 142)
> 

手続きf-rとf-iterをトレースして, 手続きが生成するプロセスを確認します.

ようこそ DrRacket, バージョン 6.1 [3m].
言語: Pretty Big; memory limit: 2048 MB.
> (f-r 5)
>(f-r 5)
> (f-r 4)
> >(f-r 3)
> > (f-r 2)
< < 2
> > (f-r 1)
< < 1
> > (f-r 0)
< < 0
< <4
> >(f-r 2)
< <2
> >(f-r 1)
< <1
< 11
> (f-r 3)
> >(f-r 2)
< <2
> >(f-r 1)
< <1
> >(f-r 0)
< <0
< 4
> (f-r 2)
< 2
<25
25
> (f-i 5)
>(f-iter 5 2 1 0)
>(f-iter 4 4 2 1)
>(f-iter 3 11 4 2)
>(f-iter 2 25 11 4)
>(f-iter 1 59 25 11)
>(f-iter 0 142 59 25)
<25
25
> 

トレースの結果から, f-rが再帰的プロセスを生成し, f-iが反復的プロセスを生成していることが分かります.