Hatena::Groupcsnagoya-sicp

toyoshiのSICP宿題帖

2008-11-08

1.10 Ackermann関数

| 03:18 | はてなブックマーク - 1.10 Ackermann関数 - toyoshiのSICP宿題帖

Ackermann関数を知らないので、たらいまわし関数みたいなもんだったらサドすぎるなと思いながら手計算した。

(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 1 6)))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 1 5))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 4)))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 3))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 2)))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 1))))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 2)))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 4))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 8)
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 16)
(A 0 (A 0 (A 0 (A 0 (A 0 32)
(A 0 (A 0 (A 0 (A 0 64)
(A 0 (A 0 (A 0 128)
(A 0 (A 0 256)
(A 0 512)
1024

たらいまわし系じゃねえか!

(A 1 y)

は2^yってことなんですね

(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)
65536

(A 1 16)は1個目のやつから2^16とわかっているので省略

これは(A x y)のとき

2^x^yかな、たぶん

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

これも途中で省略

つまり

f・・・2n

g・・・2^n

h・・・2^(2n)

ということかな

1.9 反復的プロセスと再帰的プロセス

| 02:39 | はてなブックマーク - 1.9 反復的プロセスと再帰的プロセス - toyoshiのSICP宿題帖

一個目のコードを置き換えモデルにすると

(+ 4 5)
(inc (+ 3 5))
(inc (inc (+ 2 5)))
(inc (inc (inc (+ 1 5))))
(inc (inc (inc (inc (+ 0 5)))))
(inc (inc (inc (inc (5))))
(inc (inc (inc (6))))
(inc (inc (7)))
(inc (8))
9

二個目を置き換えもデルにすると

(+ 4 5)
(+ 3 6)
(+ 2 7)
(+ 1 8)
(+ 0 9)
0

というわけで前者が再帰的プロセス、後者が反復的プロセス。

二個目のアルゴリズムは面白いなー