令和3年度春期 情報処理安全確保支援士 午前Ⅰ 問2

午前I 問02：スタックで作れる並びを考えよう

3つのデータをスタックに入れて取り出すと、作れる並びは全部で5通りだよ。スタックは「最後に入れたものが先に出る箱」みたいなものなので、そのルールのせいで1つだけ作れない並びがあるんだ。

この問題で問われていること

スタックの「後入れ先出し」という制約を意識して、どの順列が作れて、何通り作れるかを数えられるかがポイントだよ。

Stack Permutation Count

3-element stack permutations correspond to the 3rd Catalan number

Catalan(3) = 5

確認ポイント

• 3! = 6 をそのまま選ばない。
• LIFO 制約を考える。
• 5 通りを押さえる。

正解

ウ

出典

問題文と解答は IPA 公開の過去問題冊子・解答例を基にしています。

選択肢ア

これは不正解だよ。3通りだけだと少なすぎるよ。例えば、お皿を入れてすぐ出せばABC、Aを出してからBとCを重ねればACB、AとBを重ねてBから出せばBAC、というように3通りより多く作れるんだ。

選択肢イ

これは不正解だよ。4通りだと1つ足りないよ。ABC、ACB、BAC、BCA、CBAの5通りは、入れるタイミングと取り出すタイミングを工夫すれば作れるんだ。作れないのはCABだけだから、答えは4ではなく5だよ。

選択肢ウ（正解）

これは正解だよ。スタックは、お皿を上に重ねていく棚みたいに「後から入れたものを先に取り出す」仕組みだよ。A、B、Cを順に入れながら出すと、ABC、ACB、BAC、BCA、CBAの5通りは作れるけど、CABだけは作れない。だから出力順序は5通りになるよ。

選択肢エ

これは不正解だよ。A、B、Cの並べ方だけを見ると全部で6通りありそうだけど、スタックは上のお皿からしか取れない棚みたいなものだよ。Cを先に出したあと、Bを飛ばしてAを先に出すCABはできないので、6通り全部は無理だよ。