計算機プログラムの構造と解釈(問題1.9、1.10、1.11)

読書 プログラミング

ノートに殴り書いてると良くない気がするのでこっちに記載する。

問題1.9

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

(+ 4 5)
→(inc (+ 3 5))
→(inc (inc (+ 2 5)))
→(inc (inc (inc (+ 1 5))))
→(inc (inc (inc (inc 5))))
→9　再帰的

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

(+ 4 5)
→(+ 3 6)
→(+ 2 7)
→(+ 1 8)
→9　反復的

問題1.10

関数Aは多分アッカーマン関数なんだよな。
用途、意義などはよく知らない。
Wikipediaによると「与える数が大きくなると爆発的に計算量が大きくなるという特徴があり、性能測定などに用いられることもある。また、数学的な意味として、原始再帰関数でないμ再帰関数の実例として有名である」だとか。
アッカーマン関数 - Wikipedia

(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(n),g(n),h(n)の数学的な記述について

基本的にはf(0),f(1),f(2),...と地道に展開してみる。

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

簡単なので省略。$f(n)=2n$。

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

\begin{split}
g(0)&=0\\
g(1)&=2\\
g(2)&=f(g(1))\\
&=2\times g(1)=2^2\\
g(3)&=f(g(2))\\
&=2\times 2^2=2^3\\
g(4)&=f(g(3))=2^4
\end{split}
ということで $n>0$の範囲で$g(n)=2^n$、$n=0$の場合は$g(n)=0$。
ちなみに$f(n)$は$n<0$の範囲でも規定出来るけど、$g(n)$は規定出来ない。
実際やってみるとプログラムは止まらない(番人がいない)。

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

展開自体はそれほど難しくない…けどちょっと頭がこんがらがってくる。
\begin{split}
h(0)&=0\\
h(1)&=2\\
h(2)&=g(h(1))\\
&=g(2)\\
&=2^2\\
h(3)&=g(h(2))\\
&=2^{2^2}\\
h(4)&=g(h(3))\\
&=2^{2^4}\\
\end{split}
ということで、$n>0$の範囲で$h(n)=2^{2^(n-1)}$。$n=0$の場合は$h(n)=0$。
なんだか数式が上手く表示されていない気配なので書き直すと。
\[
h(n)=pow(2,pow(2,n-1))
\]
ただし、$n>0$。

追記

$h(n)$の問題は間違ってた・・・。
$h(n)=2^{h(n-1)}$。ただし、$n>0$。$h(0)=0$。

問題1.11

  • 再起プロセス版

これはそのまんま。

(define (fn n)
  (cond ((< n 3) n)
	((> n 2) (+ (fn (- n 1)) (* 2(fn (- n 2))) (* 3  (fn (- n 3)))))))
  • 反復プロセス版

結構迷った(あと、考え方がそもそも間違ってた所もあった)。基本的に反復プロセスにするためには再度呼び出す際に自分自身の関数を入れ子にせずに呼び出すこと、状態の変数を持たせることを意識して考えた。
あとは、f(2),f(1),f(0)をそのまま状態変数として渡せばOKのはず。

(define (fn n)
  (define (fn-iter f3 f2 f1 count)
    (cond ((< count 3) f3)
	  (else (fn-iter (+ f3 (* 2 f2) (* f1 3)) f3 f2 (- count 1)))))
  (fn-iter 2 1 0 n))

問題1.12

Pascal三角形の(row行、column列)の要素の値を計算するプログラムを求める(という問題でok?)。
検証でのミスをなくすため、row行目のcolumnはrowより大きい場合は0を返す。

(define (pascal-triangle row column )
  (if (< row column)
      0
      (cond ((= column 1) 1)
	    ((= row column) 1)
	    (else (+ (pascal-triangle (- row 1) (- column 1))
		     (pascal-triangle (- row 1) column))))))