応用情報技術者試験 応用情報技術者試験 平成30年度春期 午前 問5: 非負の整数 m，n に対して次のとおりに定義された関数 Ack（m，n）がある。Ack（1，3）の値はどれか。 Ack（m，n）＝Ack（m−1，Ack（m，n

問題本文

非負の整数 m，n に対して次のとおりに定義された関数 Ack（m，n）がある。Ack（1，3）の値はどれか。 Ack（m，n）＝Ack（m−1，Ack（m，n−1）） （m＞0かつn＞0のとき） Ack（m，n）＝Ack（m−1，1） （m＞0かつn＝0のとき） Ack（m，n）＝n+1 （m＝0のとき）

選択肢

• ア.3
• イ.4
• ウ.5
• エ.6

正解

ウ. 5

解説

再帰的に定義された関数(アッカーマン関数)を、定義の3つの規則に従って展開して値を求める問題。終了条件は「m=0のとき n+1」なので、これに行き着くまで丁寧に置き換えていく。Ack(1,3)=Ack(0,Ack(1,2))、Ack(1,2)=Ack(0,Ack(1,1))、Ack(1,1)=Ack(0,Ack(1,0))。ここで Ack(1,0)=Ack(0,1)=1+1=2。よって Ack(1,1)=Ack(0,2)=3、Ack(1,2)=Ack(0,3)=4、Ack(1,3)=Ack(0,4)=4+1=5 となり、ウが正解。内側の呼び出しから順に値を確定させていくのがコツ。