令和7年度 春期 応用情報技術者 午前 問5

まず、Aを挿入し、その後すぐにAを取り出すと、出力はAとなります。

次に、Aを挿入し、Bを挿入し、Aを取り出し、Bを取り出すと、出力はABとなります。

Aを挿入し、Bを挿入し、Bを取り出し、Aを取り出すと、出力はBAとなります。

A, B, C と順番に挿入し、それらを順番に取り出すと、出力はABCとなります。

A, B, C と挿入し、Cを取り出し、Bを取り出し、Aを取り出すと、出力はCBAとなります。

A, B, C と挿入し、Cを取り出し、Aを取り出し、Bを取り出すと、出力はCABとなります。

A, B, C と挿入し、Bを取り出し、Cを取り出し、Aを取り出すと、出力はBCAとなります。

A, B, C と挿入し、Bを取り出し、Aを取り出し、Cを取り出すと、出力はBACとなります。

これらの組合せを考えると、可能な出力順序はABC, ACB, BAC, BCA, CAB, CBA の6通りです。しかし、問題文では「A, B, C の順序で入力されるデータ」とあり、挿入順序は固定されています。また、「各データについてスタックへの挿入と取出しを1回ずつ行う」という制約があります。

この制約を考慮すると、出力順序は以下の5通りに絞られます。

1. Aを挿入し、取り出す。その後Bを挿入し、取り出す。その後Cを挿入し、取り出す。 → ABC

2. Aを挿入し、Bを挿入し、Aを取り出し、Bを取り出す。その後Cを挿入し、取り出す。 → ABA, BC → ABC (これは誤り、Bが取れない)

3. Aを挿入し、Bを挿入し、Bを取り出し、Aを取り出す。その後Cを挿入し、取り出す。 → BA, C → BAC

4. Aを挿入し、Bを挿入し、Cを挿入し、Cを取り出し、Bを取り出し、Aを取り出す。 → CBA

5. Aを挿入し、Bを挿入し、Cを挿入し、Cを取り出し、Aを取り出し、Bを取り出す。 → CAB

6. Aを挿入し、Bを挿入し、Cを挿入し、Bを取り出し、Cを取り出し、Aを取り出す。 → BCA

この問題は、スタック操作における「カタルーニャ数」という概念に関連しています。カタルーニャ数は、特定の組合せ問題の解となる数列であり、n個の要素に対するスタック操作での可能な出力順序の数は、(2n)! / ((n+1)! * n!) で計算されます。この問題ではn=3なので、(2*3)! / ((3+1)! * 3!) = 6! / (4! * 3!) = 720 / (24 * 6) = 720 / 144 = 5 となります。

アの3は、入力順序通りABCしか考えられないと誤解している場合に該当します。イの4は、スタックの操作回数や順序を誤って数えている場合に考えられます。エの6は、カタルーニャ数の計算で分母を間違えるなど、計算ミスによるものです。