応用情報技術者 2018年春期午前2 問05

問題文

非負の整数

m

、

n

に対して次のとおりに定義された関数

A c k (m, n)

がある。

A c k (1, 3)

の値はどれか。　

Ack (m, n) = ⎩ ⎨ ⎧ Ack (m - 1, Ack (m, n - 1)) Ack (m - 1, 1) n + 1 (m > 0 かつ n > 0 のとき) (m > 0 かつ n = 0 のとき) (m = 0 のとき)

選択肢

ア：3

イ：4

ウ：5（正解）

エ：6

Ackermann関数の計算問題【午前2 解説】

要点まとめ

結論： $A c k (1, 3)$ の値は5である。
根拠：Ackermann関数は再帰的に定義され、 $m = 0$ のときは $n + 1$ 、それ以外は再帰呼び出しで計算される。
差がつくポイント：再帰の展開を正確に追い、 $m = 0$ の基本ケースに到達するまで計算を丁寧に行うことが重要。

正解の理由

Ackermann関数は

m

と

n

の値に応じて3つのケースに分かれます。

$m = 0$ のときは単純に $n + 1$ を返す。
$m > 0$ かつ $n = 0$ のときは $A c k (m - 1, 1)$ を返す。
$m > 0$ かつ $n > 0$ のときは $A c k (m - 1, A c k (m, n - 1))$ を返す。

今回の問題は

A c k (1, 3)

なので、

m = 1 > 0

かつ

n = 3 > 0

の3番目のケースを使います。
計算を展開すると、最終的に

A c k (0, 4)

となり、

0

の場合は

n + 1

なので

5

となります。
したがって、正解はウの5です。

よくある誤解

Ackermann関数は非常に急激に値が大きくなるため、単純に

n + 1

や

m + n

のように考えてしまいがちです。
また、再帰の展開を途中で止めてしまい誤った値を選ぶことも多いです。

解法ステップ

問題の関数定義を確認し、 $m$ と $n$ の値に応じたケースを特定する。
$A c k (1, 3)$ は $m > 0$ かつ $n > 0$ なので、 $A c k (1, 3) = A c k (0, A c k (1, 2))$ と展開。
$A c k (1, 2)$ も同様に展開し、 $A c k (1, 2) = A c k (0, A c k (1, 1))$ となる。
$A c k (1, 1) = A c k (0, A c k (1, 0))$ を計算。
$A c k (1, 0)$ は $m > 0$ かつ $n = 0$ なので $A c k (0, 1) = 2$ 。
これを元に $A c k (1, 1) = A c k (0, 2) = 3$ 。
$A c k (1, 2) = A c k (0, 3) = 4$ 。
最後に $A c k (1, 3) = A c k (0, 4) = 5$ 。

選択肢別の誤答解説

ア: 3
$A c k (1, 3)$ の計算を途中で止めてしまい、 $A c k (1, 1)$ の値を誤認した可能性があります。
イ: 4
$A c k (1, 2)$ の値を $4$ と正しく計算していますが、 $A c k (1, 3)$ の計算を誤って止めています。
ウ: 5
正解。再帰を正しく展開し、基本ケースまで計算しています。
エ: 6
$A c k (1, 3)$ の値を過大評価しており、再帰の展開を誤った結果です。

補足コラム

Ackermann関数は計算理論や計算複雑性の分野で重要な関数で、非常に急激に増加する非プリミティブ再帰関数の代表例です。
この関数は計算機科学の理論的な限界や再帰の深さを理解する上で役立ちます。

FAQ

Q: Ackermann関数はなぜ重要ですか？
A: 計算理論で再帰関数の複雑さを示す例として使われ、計算可能性の限界を理解するのに役立ちます。

m = 0

のときのAckermann関数の意味は？
A:

m = 0

のときは単純に

n + 1

を返す基本ケースで、再帰の終了条件となります。

関連キーワード: Ackermann関数、再帰関数、計算理論、非プリミティブ再帰、数学的帰納法

← 前の問題へ次の問題へ →

\ せっかくなら /

応用情報技術者を
クイズ形式で学習しませんか？

クイズ画面へ遷移する→

すぐに利用可能！

応用情報技術者 2018年 春期 午前2 問05

問題文

選択肢