アルゴリズム基礎解説（平成17年秋期問4）
| 解説 |
|---|
|
後置表記法＝逆ポーランド記法 ということに注意してプログラムをトレースする。 逆ポーランドが苦手な人も多いかもしれないが、試験では午前での出題率が高いので 必ず覚えておかなくてはならない。 どの問題でも同じですが、プログラムの説明がプログラム言語に近い書き方で記述されているのでそれを要約し、何をするプログラムなのかを理解する力が必要となります。ほとんど日本語ではない。といっても過言ではないので、自力で日本語に戻します。 一番簡単な方法としては、「、」で説明が冗長的なので、全部短く区切る。というやり方 内容自体も難しいが、その前にわざと変な日本語で難解にしてある。 もう一つは、変数名などで記述されている部分を、日本語の説明文に置き換える。 というやり方。意外と日本語に変えるだけで内容がわかることがある。 ⑤、⑥をみてもらえれば、プログラムの内容がすぐ理解できるかと思います。 設問１ まずは説明文からプログラム内容を要約しよう。 (4)の②だけが、スタックに入れる処理を説明しているので これを見逃すとプログラムが何をしているか理解できなくなるので注意すること。 ①：スタックは最初に初期化される。 ②：初期化後、優先度の一番低いEOS(-1)が格納する。 ③：対象となる文字列は、配列[Exptext]に１要素ずつ格納している。 ④：出力結果は、配列[Postfix]に１要素ずつ格納する。 ⑤：入れようとする要素と入っている要素の優先度を比較し 入れようとしている要素のほうが高くなるまでスタックから取り出す。 しかし"("であれば、取り出さない。 ⑥：入れようとする要素のほうが高ければスタックに格納する。 しかし")"であれば、格納せず１つだけスタックから取り出し、格納もしない。 ⑦：スタックに残っている要素を取り出す。 プログラムをトレースしながら[a][b][c][d]の中に答えを埋めていく。 この手の問題は、先に解答群を見たほうがわかりやすい。ということもあるので 説明文で理解が難しければ先に解答群をみて、説明文と照らし合わせて行く。 という方法もある。 答えを見つけるためではなく、プログラムの内容を理解するのに時間をかける。 [a]について [a]は繰返し文の条件である。全ての解答は「i」に初期値をいれ「Textlen」と比較 している。 「Textlen」は説明文より「中置表記法による数式の要素数」である。 同じような解答群から答えを瞬時に判断するのは、難しい。まずは「i」について考 える 条件文の次の行に getPriority(Exptext[i]) ≦ getPriority(top()) とある。 [a]では内容よりも、Exptext[]が配列であることに目を向けよう。 配列であるならば、Exptext[0]から比較しなければならないのがわかる つまり「i」の初期値は「0」である。 ここから悩むと思うのだが ＜ か ≦ であるか。 プログラムをトレースしてみよう。 「Textlen」に適当な数、例えば５を入れて考えると、「i」は「0」から比較し、 [4]まで処理を実行する（要素数が５であるため） アの条件では i ＝ 5 になったときに処理を抜け（処理はiが4まで実行） イの条件だと i ＝ 6 になったときに処理を抜けている（処理はiが5まで実行） このことがわかれば答えは「ア i:0, i ＜ Textlen, 1」であることがわかる。 [b]について これも解答群から見て欲しいのだが、「i」か「k」の値を加算・減算していき 処理を繰り返している。 ⑤の内容から判断するに、入れようとする要素の優先度が 入れてある要素の優先度より高くなるまで、スタックから要素を取り出し、 配列Postfix[]に格納している。 そのことから、取り出した要素を格納する配列番号「k」についてであることがわか る。 格納する配列の要素数なのであるから、０から１ずつ加算することがわかる。 よって解答は「ウ k ← k ＋ 1 」である。 [c]について プログラム内容を見てみると sflag が false になるまで処理は繰り返される。 そして中の処理で work に値を格納している。 [c]はその判定となっている。 [c]が負であれば、falseが入り、そのまま処理が終わる。 そのことを考えれば、スタックの最後を表すものだろうと推測できる。 よって正解は「ウ work ＝ EOS 」である。 これは簡単にわかるだろう。 [d]について 最後にPostfixlenに何かを格納している。 この何かとは、説明文の「後置表記法に変換後の数式の要素数」より 「要素数」であることがわかる。決して格納した文字列の総数ではないことに注意。 似た選択肢がいっぱいあるので、悩むかもしれないが 悩む必要は無い。 変換後の～とあるので、返還前の要素数である「i」はありえない。 ここで、＋１や－１があるので、どれにしようかと思うかもしれないが ひっかけである。 もう一度プログラムを見てみよう。 まず「k」は０から始まっており、スタックから取り出すときにだけ加算されてい る。 つまり「k」の数はそのまま出力した配列の要素番号そのままである。 ここで＋１かもしれない。と思った方へ。 配列番号は０から始まっているので、全体の数はそれに＋１を加えたものだから・・ ・ と思われたかもしれないが、 格納するのは、配列の要素番号である。 ひっかけなので、注意してください。 よって答えは「エ k」である。 設問２ プログラム中の「α」の時に「Postfix 」がどういう状態になっているかを問われて いる 対象の計算式は 「(2 ＋ 4) × 3 ＋ 5 × 6」である。 注意して欲しいのは、「α」の時点では、まだ変換が終わりきってないことである。 問われた瞬間に「エ 2 4 ＋ 3 × 5 6 × ＋ 」を選ばないようにしましょう。 プログラムが全て終わったときは、このようになっているのですが・・・ プログラムの理解ができていれば簡単な問題です。 丁寧にプログラムをトレースしていきましょう。 まず"("がスタックに入ります。優先度が４です。 スッタクは「"(", EOS」 次に２、優先度は３、入れる２のほうが優先度が低いですが、入れてあるのは"("な のでそのまま２を入れる。「"2","(", EOS」 次に＋、優先度は１、"2"を取り出してからスタックへ「"+","(", EOS」 Postfix[]は「"2"」 次に"4"、優先度が３なのでそのままスタックに。「"4","+","(", EOS」 次に")"、優先度が４なので、２個取り出す。Postfix[]は「"2","4","+"」 ")"なのでさらに１つ取り出すが使用しない。スタックは空となる「EOS」 次は×、優先度は２、そのままスタックへ「"×",EOS」 次は３、優先度は３、そのままスタックへ「"３","×",EOS」 次は＋、優先度は１、全て取り出してからスタックへ「"+",EOS」 Postfix[]は「"2","4","+","3","×"」 次は５、優先度は３、そのままスタックへ「"５","+",EOS」 次は×、優先度は２、１つ取り出し、スタックへ「"×","+",EOS」 Postfix[]は「"2","4","+","3","×","5"」 最後の６、優先度は３、そのままスタックへ「"6","×","+",EOS」 よってPostfix[]は「"2","4","+","3","×","5"」であるから 答えは「イ 2 4 ＋ 3 × 5 」である。 プログラムの内容が理解できていれば易しい問題である。 設問３ 優先度を返す関数 getPriority についてである。 内容が簡単なので、すぐに解答をしようとするとワナにはまります。 消去法で考えます。 条件式の内容は、elementと同じものがあるかどうかを 探していることはわかると思います。 処理の内容は「i」を加算しています。 なのでウはありえないのがわかります。 優先度を返すためには、elementがどの優先度の文字列であるかを調べなくてはなり ません。 そして、文字列に合った優先度を返すわけです。 記述されている文章より、priority[i]が優先度を返すことがわかります。 つまり、条件は、elem[]からelementと同じものを探しているので ア、イ、カ、キの４つにしぼることができます。 また、「i」が０から始まり、配列の要素数であることから、 減算する必要がないことがわかります。 よってアとカが残りました。 ここまではすぐわかると思いますが、あせるとワナにかかります。 もう少しプログラムを見てみましょう。 条件が正である限り「i」を加算しています。 elementと同じものが見つかるまで「i」を加算する。ということは 見つからない間、「i」を加算すること。なので 答えは「カ element ≠ elem[i] 」になります。 急ぎすぎてワナにはまらないようにしましょう。 |
まっち～様 ご投稿
メニューへ戻る