（ソフ開）（平成１９年秋午前問題）問９の質問

質問

こんにちは。
表題の問題、教えていただきたいです。

問題のテキストをコピーできないので、リンクを書きます。
http://www.jitec.jp/1_04hanni_sukiru/mondai_kaitou_2007h19_2/2007h19a_sw_am_qs.pdf

私の理解としては、A、B、Cの順序で入力するとしたら、Cを取り出すために、
１回でできる。Bを取り出すために、C,Bを出力するから、２回。
Aを取り出すために、C,B,Aを出力するから、３回。
ですから、全部で１＋２＋３＝６回と思いますが、
なぜ答えが５回でしょうか。
そもそもこの問題の題意を理解を理解できていないのかな。

お分かりになる方がいらっしゃいましたら、ぜひご教授ください。

よろしくお願いいたします。

回答No.2

jjon-com · ベストアンサー

ANo.1が正解。（それが言いたかっただけです，すみません。「自信あり」じゃなく「参考意見」になってたもので）
以下，蛇足です。(I)がpushで (O)がpop，左から右へとスタック操作を示しているので，

(I)(I)(I)(O)(O)(O)…出力順序はCBA
(I)(I)(O)(I)(O)(O)…出力順序はBCA
(I)(I)(O)(O)(I)(O)…出力順序はBAC
(I)(O)(I)(O)(I)(O)…出力順序はABC
(I)(O)(I)(I)(O)(O)…出力順序はACB

ということで，残ったCABは１つのスタックだけでは出力できません。

回答No.3

soratabi79

さらに蛇足を。
この条件下だと「ＣＡＢ」はなぜ出力不可能なのか？についてです。

スタック問題を解くためには、「入力したデータは底にたまる」「１回の出力で取り出せるデータは、一番上にたまっているデータのみ」ということを知っていることが前提となります。

ゆえに、「Ａを、Ｂよりも先に出力させる」ためには「Ａが出力候補になっている、という条件のもとで、Ｂが入ってくる前にＡを出力させる」以外の方法はありません。

ANo.2番さんが指摘しておられる「ＡＢＣ、ＡＣＢ」の２つが、これに該当します。
-----
という前提はおいておいて、「ＣＡＢはなぜ出せないの？」という話の本編です。

この問題の設定では、「Ａ，Ｂ，Ｃの順番で入力する」とあります。「ＢよりもＡを先に出力する」ためには、少なくとも「Ｂが入力される前に」Ａの出力処理をしなけれならないのは、前述の通りです。とりあえず、「ＣＡＢ」になりそうなデータ処理を追いかけてみます。

「ＣＡＢ」を実現しようと思ったら、まずは、「Ｃを最初に出力」する必要があります。なので、とりあえず「Ａ、Ｂのデータをスタックに入力し、Ｃの入力を待つ」方法をとらないと、Ｃを最初に出力することはできません。

で、Ｃを取り出したあとのＡとＢのデータは、スタック内ではこのようになっています。

｜からっぽ｜
｜データＢ｜
｜データＡ｜
－－－－－－

「ＣＡＢ」を完成させるには、次にＡを出力するしかありません。しかし、上の図、および「取り出しのルール」上、次に取り出せるデータはＢのみです。なので、どうしても次に「Ａを出力すること」は不可能なのです。

ゆえに、「ＣＡＢ」はこの問題においては不可能、と結論づけられます。

お礼

なるほど、よく理解できました。
皆さんのご回答、ありがとうございました。
今後とも、よろしくお願いします。

回答No.1

noname#63784

ABCの並び方なら３＊２＊１＝６通りですが

挿入３回、取り出し３回の組み合わせですから
また最初は(I)、最後は（O)と決まり
さらに(I)していないのに（O)はできませんから
(I)(I)(I)(O)(O)(O)
(I)(I)(O)(I)(O)(O)
(I)(I)(O)(O)(I)(O)
(I)(O)(I)(O)(I)(O)
(I)(O)(I)(I)(O)(O)
の５通りでよいのではないかと思います