Aizu SICP 第5回 - やろーじだい

2016/7/11 追記: 数式のサイズを見易いように修正

今日は参加できる人が少なめだったので練習問題 1.9 ~ 1.13 を解く時間にしてみたが、参加者全員で頭をひねって解く時間はなかなか良かったのでこの形式でまたやりたい。

今回の内容

注意: 以下では私達の練習問題の解答を載せています。まだ問題を解いていない人は一度取り組んでみてください。すでに解き終わっている人で何か解答におかしいところを見つけた人は教えてください。

練習問題 1.9

　実際に動かすために inc と dec を以下の様に実装した。

(define (inc x)
  (+ x 1))

(define (dec x)
  (- x 1))

また、+ で実装すると Scheme 上で実装されている + を上書きしてしまい面倒なのでそれぞれの関数を plus1、plus2 とした。

(define (plus1 a b)
  (if (= a 0)
      b
      (inc (plus1 (dec a) b))))

(define (plus2 a b)
  (if (= a 0)
      b
      (plus2 (dec a) (inc b))))

plus1 は「a plus1 b は a = 0 の時 b であり、それ以外の場合、a から 1 引いたものに b を plus1 した結果に更に 1 足したものに等しい」であり plus2 は「a plus2 b は a = 0 の時 b であり、それ以外の場合、a から 1 引いたものに、b に 1 を加えた結果を plus2 したものに等しい」という意味を持つ。この時、 plus1 では明らかに inc による遅延演算の連鎖がおこるため再帰プロセスであり、 plus2 では毎回の演算が独立しているため反復プロセスであることがわかる。以下に (+ 4 5) を plus1、plus2 それぞれを適応した展開の流れを記述する。

;; plus1
(plus1 4 5)
;; ↓
(inc (plus1 3 5))
;; ↓
(inc (inc (plus1 2 5)))
;; ↓
(inc (inc (inc (plus1 1 5))))
;; ↓
(inc (inc (inc (inc (plus1 0 5)))))
;; ↓
(inc (inc (inc (inc 5))))
;; ↓
(inc (inc (inc 6)))
;; ↓
(inc (inc 7))
;; ↓
(inc 8)
;; ↓
9

;; plus2
(plus2 4 5)
;; ↓
(plus2 3 6)
;; ↓
(plus2 2 7)
;; ↓
(plus2 1 8)
;; ↓
(plus2 0 9)
;; ↓
9

練習問題 1.10

(define (A x y)
  (cond ((= y 0) 0)
        ((= x 0) (* 2 y))
        ((= y 1) 2)
        (else (A (- x 1) (A x (- y 1))))))

以下は何も考えず実行した結果を貼った。

(A 1 10)
;;=> 1024
(A 2 4)
;;=> 65536
(A 3 3)
65536

以下は数学的定義を与える問題について。

f

(define (f n) (A 0 n))

これは A の定義から、 n = 0 の時 (f n) は 0, それ以外の場合は全て cond 式の第2式に入るため (* 2 n) が実行される。よって

${ \displaystyle f(n) = 2n }$

g

(define (g n) (A 1 n))

n = 0, 1, 2, 3 の場合を展開すると、

(A 1 0)
;; ↓
0
;; ↓

(A 1 1)
;; ↓ (A の定義より)
2

(A 1 2)
;; ↓
(A 0 (A 1 1))
;; ↓
(A 0 2)
;; ↓ (f の定義より)
4

(A 1 3)
;; ↓
(A 0 (A 1 2))
;; ↓
(A 0 (A 0 (A 1 1))
;; ↓ 
(A 0 (A 0 2))
;; ↓ (f の定義より)
8

一般化すると、

(A 1 n)
;; ↓
(A 0 (A 1 (- n 1)))
;; ↓
(A 0 (A 0 (A 1 (- n 2))))
...
;; ↓
(A 0 (A 0 (A 0 ... (A 1 1))))

このように n-1 の数だけ 2 に $f(n)$ が適応される。(ただし n = 0 の場合は A の定義より 0 になる。また 0 未満の場合は未定義 (無限ループ)) よって、

f:id:lhcpr:20160710204153p:plain:w200

h

(define (h n) (A 2 n))

n = 0, 1, 2, 3 の場合を展開すると、

(A 2 0)
;; ↓
0

(A 2 1)
;; ↓
2

(A 2 2)
;; ↓
(A 1 (A 2 1))
;; ↓
(A 1 2)
;; ↓ (g の定義より)
4

(A 2 3)
;; ↓
(A 1 (A 2 2))
;; ↓ (上の定義より)
(A 1 4)
;; ↓
16

という様に、

(h n)
;; ↓
(A 2 n)
;; ↓
(A 1 (A 2 (- n 1)))
;; ↓
(A 1 (h (- n 1)))

というような漸化式の形をしている。例えば n = 3 の場合は ${ 2^{2^{2^{1}}} }$ という様に展開される。数式として表わすと、

f:id:lhcpr:20160710214755p:plain:w250

練習問題 1.11

再帰プロセスは数式をそのままプログラムにできる。反復プロセスは P40 フィボナッチの関数とほぼ同様にできる。

(define (f n)
  (f-rec 2 1 0 n))

(define (f-rec a b c n)
  (cond ((= 0 n) c)
        (else (f-rec (+ a (* 2 b) (* 3 c))
                     a
                     b
                     (- n 1)))))

同様な形の漸化式の場合、項の数がいくつ増えてもその分だけ引数の数を増やしていけば同様に反復プロセスに落とすことができることがわかる。

練習問題 1.12

いまいち問題の意味がわからなかったが、多分こういう意味だろうということで実装した。

(define (pascal-triangle row col)
  (cond ((= col 1) 1)
        ((= row col) 1)
        (else (+ (pascal-triangle (- row 1) col)
                 (pascal-triangle (- row 1) (- col 1))))))