情報処理安全確保支援士試験 情報処理安全確保支援士試験 平成30年度春期 午前Ⅰ 問2: 非負の整数m，nに対して次のとおりに定義された関数Ack(m，n)がある。Ack(1，3)の値はどれか。 Ack(m，n)＝Ack(m−1，Ack(m，n−1)

問題本文

非負の整数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

解説

アッカーマン関数は定義に従い再帰展開する典型問題。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)=2と最内側から計算する。順にAck(1,1)=3、Ack(1,2)=4、Ack(1,3)=5となり正解はウ。m=1ではAck(1,n)=n+2となる性質があり、再帰の停止条件と評価順序の理解を問う。

選択肢ごとの解説

• ア.3はAck(1,1)の値であり、引数nに対し展開が一段不足しているためAck(1,3)とはならず誤り。
• イ.4はAck(1,2)の値で、最内側からもう一段の再帰展開が足りておらず、Ack(1,3)には届かないため誤り。
• ウ.定義を最内から展開するとAck(1,n)=n+2の規則が成り立ち、Ack(1,3)=3+2=5となり正解。
• エ.6はAck(1,4)に相当する値で、与えられた引数より一段多く展開し過ぎているため誤り。