- ベストアンサー
（ソフ開）（平成１９年秋午前問題）問９の質問
こんにちは。 表題の問題、教えていただきたいです。 問題のテキストをコピーできないので、リンクを書きます。 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を出力するから、３回。 ですから、全部で１＋２＋３＝６回と思いますが、 なぜ答えが５回でしょうか。 そもそもこの問題の題意を理解を理解できていないのかな。 お分かりになる方がいらっしゃいましたら、ぜひご教授ください。 よろしくお願いいたします。
- みんなの回答 （3）
- 専門家の回答
質問者が選んだベストアンサー
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は１つのスタックだけでは出力できません。
その他の回答 (2)
- soratabi79
- ベストアンサー率69% (32/46)
さらに蛇足を。 この条件下だと「ＣＡＢ」はなぜ出力不可能なのか？についてです。 スタック問題を解くためには、「入力したデータは底にたまる」「１回の出力で取り出せるデータは、一番上にたまっているデータのみ」ということを知っていることが前提となります。 ゆえに、「Ａを、Ｂよりも先に出力させる」ためには「Ａが出力候補になっている、という条件のもとで、Ｂが入ってくる前にＡを出力させる」以外の方法はありません。 ANo.2番さんが指摘しておられる「ＡＢＣ、ＡＣＢ」の２つが、これに該当します。 ----- という前提はおいておいて、「ＣＡＢはなぜ出せないの？」という話の本編です。 この問題の設定では、「Ａ，Ｂ，Ｃの順番で入力する」とあります。「ＢよりもＡを先に出力する」ためには、少なくとも「Ｂが入力される前に」Ａの出力処理をしなけれならないのは、前述の通りです。とりあえず、「ＣＡＢ」になりそうなデータ処理を追いかけてみます。 「ＣＡＢ」を実現しようと思ったら、まずは、「Ｃを最初に出力」する必要があります。なので、とりあえず「Ａ、Ｂのデータをスタックに入力し、Ｃの入力を待つ」方法をとらないと、Ｃを最初に出力することはできません。 で、Ｃを取り出したあとのＡとＢのデータは、スタック内ではこのようになっています。 ｜からっぽ｜ ｜データＢ｜ ｜データＡ｜ －－－－－－ 「ＣＡＢ」を完成させるには、次にＡを出力するしかありません。しかし、上の図、および「取り出しのルール」上、次に取り出せるデータはＢのみです。なので、どうしても次に「Ａを出力すること」は不可能なのです。 ゆえに、「ＣＡＢ」はこの問題においては不可能、と結論づけられます。
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) の５通りでよいのではないかと思います
お礼
なるほど、よく理解できました。 皆さんのご回答、ありがとうございました。 今後とも、よろしくお願いします。