問5応用情報技術者 平成30年度 春期

解説

正解は3。図の定義は、m＝0ならn＋1、m＞0かつn＝0ならAck(m−1, 1)、m＞0かつn＞0ならAck(m−1, Ack(m, n−1))である。内側から順に展開する。
Ack(1, 0)＝Ack(0, 1)＝2
Ack(1, 1)＝Ack(0, Ack(1, 0))＝Ack(0, 2)＝3
Ack(1, 2)＝Ack(0, Ack(1, 1))＝Ack(0, 3)＝4
Ack(1, 3)＝Ack(0, Ack(1, 2))＝Ack(0, 4)＝5
m＝1のときはAck(1, n)＝n＋2になっていることも分かる。

• 1の3はAck(1, 1)の値、2の4はAck(1, 2)の値で、展開を途中で止めている。
• 4の6は、展開を1段多く進めた値で、Ack(1, 4)にあたる。

根拠：再帰関数の定義に従った展開（アッカーマン関数）。