SICP 問題 1.10

2017/08/12

#sicp

今まで問題はgithubにpushしてたのだけど、なんとなくブログに書いてみる。飽きたら辞める。

問題 1.10

次の手続きはAckermann関数という数学関数を計算する.

(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)
(A 2 4)
(A 3 3)

Aを上で定義した手続きとして, 次の手続きを考える.

(define (f n) (A 0 n))
(define (g n) (A 1 n))
(define (h n) (A 2 n))
(define (k n) (* 5 n n))

正の整数nに対して手続きf, gおよびhが計算する関数の簡潔な数学的定義を述べよ.
例えば(k n)は5n2を計算する.

(A 1 10)の値は何か.

(A 1 10) は下記のように展開されていき

(A 1 10)

(A 0
  (A 1 9))

(A 0
  (A 0
    (A 1 8)))

(A 0
  (A 0
    (A 0
      (A 1 7))))
...

こうなる。

(A 0
  (A 0
    (A 0
      (A 0
        (A 0
          (A 0
            (A 0
              (A 0
                (A 0
                  (A 1 1))))))))))

(A 1 1) は 2 になり、x=0 でAを呼んだ回数分2倍していくので、答えは1024となる。

(A 2 4)の値は何か.

同じようにどのように展開されるか考えてみる。

(A 2 4)

(A 1
  (A 2 3))

(A 1
  (A 1
    (A 2 2)))

(A 1
  (A 1
    (A 1
      (A 2 1))))

(A 1
  (A 1
    (A 1 2))

(A 1
  (A 1
    (A 0
      (A 1 1)))

(A 1
  (A 1
    (A 0 2)))

(A 1
  (A 1 4))

(A 1
  (A 0
    (A 1 3)))

(A 1
  (A 0
    (A 0
      (A 1 2))))

(A 1
  (A 0
    (A 0
      (A 0
        (A 1 1)))))

(A 1
  (A 0
    (A 0
      (A 0 2))))

(A 1
  (A 0
    (A 0 4)))

(A 1
  (A 0 8))

(A 1 16)

になり、上の問で (A 1 10) が 2**10 になっているので、(A 1 16) は 2**16 になり、答えは65536となる。

(A 3 3)の値は何か.

同じようにどのように展開されるか考えてみる。

(A 3 3)

(A 2
  (A 3 2))

(A 2
  (A 2
    (A 3 1)))

(A 2
  (A 2 2)))

(A 2
  (A 1
    (A 2 1))))

(A 2
  (A 1 2))

(A 1 2) は上の問より、 2**2 なので4となり、前の問と同じ (A 2 4) になるので、答えは65536。

正の整数nに対して手続きf, gおよびhが計算する関数の簡潔な数学的定義を述べよ.

(f n) => 2n
(g n) => 2**n
(h n) => 2**(h (n-1))

最後はちょっとわからなくて、上記のような答えになってない答えになってしまった。
諦めて答えみてもよくわからなかった。。。足りなくない？と思ってしまう

そのうちまた考えてみよう。