非負の整数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のときAck(0,n)=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となる。

選択肢ごとの解説

• ア3はAck(1,1)の値であり、Ack(1,3)ではない。
• イ4はAck(1,2)の値である。
• ウ正しい。Ack(1,3)＝Ack(0,4)＝5である。実際Ack(1,n)＝n+2という規則になっている。
• エ6はAck(1,4)の値であり、1つ先まで展開してしまった場合の値である。

同じ分野の他の問題

• 異なるn個のデータが昇順に整列された表がある。この表をm個のデータごとのブロックに分割し、各ブロックの最後尾のデータだけ…2025年度 秋期 問3
• A, B, Cの順序で入力されるデータがある。各データについてスタックへの挿入と取出しを1回ずつ行うことができる場合、デ…2021年度 春期 問2
• 自然数をキーとするデータを、ハッシュ表を用いて管理する。キーxのハッシュ関数h(x)を h(x) = x mod n と…2024年度 秋期 問3
• 各ノードがもつデータを出力する再帰処理f(ノード n)を定義した。この処理を、図の2分木の根(最上位のノード)から始めた…2024年度 春期 問3
• あるデータ列を整列したら状態0から順に状態1、2、・・・、Nへと推移した。整列に使ったアルゴリズムはどれか。 状態0 3…2023年度 秋期 問3