令和3年度 春期 午前 問5

✓ これが正解ウ5

解説

後入れ先出しの制約を守る並びは 5 通りです。

設問は、三つのデータを決まった順序で入力しながらスタックへの挿入と取出しを行うとき、出力順序が何通り作れるかを数えさせています。ですから数え上げの軸は、後から入れたものが先に出るという制約を守る並びだけを拾う、という一点だけです。入力の順序は決まっていますから、各段階でできることは、次のデータを挿入するか、いま一番上にあるものを取り出すかの二つに限られます。この二択を最後まで枝分かれさせて数えると、成り立つ出力順序は 5 通りになります。並べてみると、入れた順にそのまま出す形、二つ目と三つ目を入れ替える形、二つ目を最初に出す形が二通り、そして三つ入れきってから逆の順に出す形です。

ほかの選択肢はなぜ違うのか

• ア3：枝分かれを最後までたどると、この数では数え落ちが出ます。三つとも入れきってから出す形だけでなく、途中で取り出してから次を入れる形も成り立つので、数はこれより多くなります。
• イ4：成り立つ並びを一つ数え落とすとこの数になります。実際に枝をすべてたどると、最後に入れたものから順に取り出す形まで含めて 5 通りが残りますから、この数では足りません。
• エ6：三つの記号の並べ方をすべて許した場合の総数 3 × 2 × 1 の値です。しかし三つ目を最初に取り出した後は、その下に一つ目より二つ目が積まれているため、次に一つ目を取り出す並びは作れません。