平成30年(H30)秋期 基本情報技術者試験 アルゴリズム問題 解き方解説

平成30年度秋期午後のアルゴリズム問題である問8の私の解き方・考え方について解説していきます。

問題

IPAの公式サイトで公開されています。このページでは問8についての解説を行います。

https://www.jitec.ipa.go.jp/1_04hanni_sukiru/mondai_kaitou_2018h30_2/2018h30a_fe_pm_qs.pdf

問題の概要

与えられた数式の計算結果を求めるプログラムに関する問題です。

このプログラムは二つの処理に分けられています。1つ目は解析処理、2つ目は計算処理です。

1つ目の解析処理では数式を分解し、数値をValue[ ]、演算子をOperator[ ]、その演算子の計算優先度をPriority[ ]にそれぞれ格納する処理を行っています。

Priority[ ]が高いほど計算優先度が高く、この優先度が高い演算子に対する計算処理が先に実行される作りとなっているようです。

例えば例1の時の解析処理結果が下記のようになっています。計算の実行順とPriority[ ]を色で対応づけています。

2つ目の計算処理では、解析処理によって得られた↑の情報に基づいて実際に計算を行っています。

この計算処理は細かく分けると3つの処理に別れており、まず優先度の一番高い演算子を探し出します。下の例だと Priority[2] の21が一番優先度が高いので、ip に 2が格納されます。

次にその演算子に対する計算処理を行います。下の例であれば ip が2なので Value[2]+Value[3] を計算し、結果を Value[2] に格納します。

さらに、Value[ ]Operator[ ]Priority[ ]それぞれの配列の整理を行います。

これを最後まで繰り返すことで計算処理が実行され、Value[0]に最終的な計算結果が格納されるプログラムになっています。

スポンサーリンク

設問1

設問1は解析処理におけるPriority[ ]の求め方に関する問題になっています。まずPriority[ ]をプログラムでどうやって求めているかを見てみましょう。

nestという変数を利用しており、このnestは初期値が0で、’ ( ‘が現れるたびに+10され、’ ) ‘が現れるたびに-10されています。さらに、演算子である + – に対してはnest+1を × ÷ に対してはnest+2Priority[ ]に設定しているようです。

数式では括弧内の計算を優先して先に実行する必要があります。さらにこの括弧は何重にも用いられることもあります。このnest変数はある演算子が括弧の何重目に存在しているか(括弧の深さ)を記憶するために用いられている変数のようです。

プログラムでのこのnestの動きとPriority[ ]を分かりやすくするために下の図を用意してみました。

nestの値が’ ( ‘や’ ) ‘が現れるたびに変化している様子が見て取れると思います。括弧の深さが大きくなるたびに10ずつnestの値が変化します。

÷に注目してみると、この÷はnestが10の時に現れる演算子となっています。ですので、この÷のPriority[ ]は10+2の12となります。

+に注目してみると、この+はnestが20の時に現れる演算子となっています。ですので、この+のPriority[ ]は20+1の21となります。

ここまでがnestPriority[ ]の求め方に関する説明になります。

ここまでのことを頭に置いて設問を実際に解いていきましょう。

まず[   a   ]ですが、nestの値を増減させる定数がどういう値の場合であれば常に正しい計算順序が保証されるか?という問いになっています。

実際にnestの値を増減させる定数に選択肢のものを用いてPriority[ ]の値がうまく求められるかを見てみましょう。先ほどと同様の図を定数を1としたときのものが下の図になります。

この場合、同じPriorityのものが現れます。例えば × と – が同じPriorityで2となります。同じ優先度の場合はより左側にある演算子から計算処理が行われます(これは設問2の説明に書いてある。計算処理のプログラムでもそうなっている)。

なので本当は括弧内にある – を先に計算しなければならないのに × が先に実行されることになり、計算順序が保証されません。したがってnestの値の増減に用いる定数は1ではダメです。

この時点で選択肢はイのみ残ることになります。なぜなら、アウエとも1が含まれる条件になっているためです。

実際にイのnestの値の増減に用いる定数を2とした時の図を見てみると括弧の深さが大きい演算子ほどPriorityの値も大きくなっており、計算順序が保証されていることがわかると思います。

なので、[   a   ]の答えは2以上となります。

続いて[   b   ]を解きましょう。[   b   ]は行①と行②(nestの値を増減させている部分)を下のように変更した場合に、nestの値を増減させる定数がどんな場合に計算順序が保たれるかを問う問題になっています。

選択肢はアイウエの4つがありますが、[   a   ]を解いた時点で選択肢の2つが間違いであることは分かっているはずです。間違っていると分かっているのは選択肢イと選択肢ウです。

選択肢イの「priHigh + 1以上」に関しては、[   a   ]の回答を求める際に、「priHigh以上」も成立することが分かっているため間違いと分かります。この時点で計算順序が保たれるのは「priHigh + 1以上」の場合に限られない、ということになります。

また、[   a   ]の回答を考慮する際に、priHighが1、priLowが2である時、nestの値を増減させる定数を1とすると計算順序が保たれないことをすでに確認しています。これはまさに選択肢ウの「priHighpriLow以上」にあてはまるケースであり、選択肢ウも間違いということになります。

なので残る選択肢はアとエのみになります。アの選択肢は「priHigh以上」で、エの選択肢は「priHighpriLow + 1以上」なので、nestの値を増減する定数が「priHighpriLow + 1以上」かつ「priHigh未満」であるケースを実際に見てみると回答は1つに絞れそうです。このケースで成立するのであれば、priHigh以上」以外でも成立してしまうということになりますのでアの選択肢は消えます。

priLowを10、priHighを20とし、nestの値を増減する定数を11とした時のnestPriority[ ]の関係は下の図のようになります。

括弧の深さが高いほどPriority[ ]の値は高くなりますので、計算順序が保たれているということになります。これはnestの値を増減する定数は「priHigh以上」ではない時でも成立することの証明ですので、選択肢アを消すことができます。したがって[   b   ]の答えは「priHigh – priLow + 1以上」となります。

設問2

設問2は同じ優先度の演算を左側から行うのではなく右側から行う場合の処理に関する問題です。

[   c   ]は同じ優先度の演算を右側から行うためにどのようにプログラムを変更するかの問題です。

実際に演算が同じ優先度になる場合のプログラムの動きを追ってみると正解にたどり着きやすいと思います。

プログラムがそのままだと下記のようにプログラムは動作します。

ip は次に演算を行う演算子を指す添字です。プログラムを追ってみると、Priority[ ]の比較の時に同じ優先度の場合はipの値が更新されません。なので同じ優先度の場合、先に現れた(つまりより左側にある)演算子に対する i が優先されてipに格納され、その演算子に対する計算処理が先に実行されることになります。

次にPriority[ ]の比較の時に同じ優先度の場合にもipの値を更新するようにプログラムを変更(選択肢エのように変更)し、その時の処理の動きを追って見ましょう。 

このようにプログラムを変更すると、同じ優先度でも右側の演算子が優先して先に実行されます。ですので、[   c   ]の答えは選択肢エとなります。

選択肢ウも正解っぽい選択肢ですが、実際に見てみるとipが0で初期化されているため下記のようにプログラムが動き、左側の演算子が優先される場合がありますので、間違いとなります。

[   d   ]に関しては実際に各ケースをプログラムに入力した時の動きを追ってみるのが確実だと思います。が、これは通常の四則演算で交換法則が成り立つのは + と × の時のみということを知っていればすぐに解ける問題ですね。逆に – と ÷ の場合は交換法則が成り立ちません。

– と ÷ が含まれないのはケース1のみですので、[   d   ]の答えは選択肢アとなります。

設問3

符号付き整数を含んだ整数式を入力した時のプログラムの動きを問われている問題になります。

早速、実際に2 × ( -1 )が入力された時の解析処理結果を見てみましょう。プログラムを追って考えてみると解析処理結果は下記のようになります。

Operator[ ] が ” – ” の時のValue[ ]が” 0 “になるところがポイントですね。この結果からもわかるように、[   f   ]の答えは0[   g   ]の答えは2となります。

計算処理は下記の流れで行われていきます。ちゃんと2 × ( -1 )の計算結果である” -2 “がValue[0]に格納されるところに注目です。

続いて[   e   ]の答えを考えてみます。

まず選択肢イはないですね。上の例でも分かるように – の付いた符号付き整定数が含まれる整数式が入力されてもこのプログラムは正常に動作可能です。続いて選択肢アとウが正しいかどうかを、-2 × ( -1 )を入力した時の計算処理の動きをみてみましょう。

計算処理3回目実行後の結果は図のスペース上省いてしまっていますが、3回目では0 – ( -2)の計算結果がValue[0]に格納されることになりますので、最終的にValue[0]には2が格納され、-2 × ( -1 )の計算結果として正しい値が格納されます。

つまり、整数式が符号付き整数で始まったとしても、整数式に符号付き整数が2つ以上あったとしても正しい計算が実行可能なプログラムであるということです。従って選択肢アとウも間違いであり、[   e   ]の答えは選択肢エとなります。

スポンサーリンク

解いてみた感想

問題見てビックリしました。まず問題の傾向が今までとちょっと違っています。最近の問題ではプログラムの穴埋め問題が何問かはあったのですが今回はなしです。

さらに問題が難しかったです。

例えば[   b   ]をア、[   c   ]をウと回答した人多いのではないでしょうか?今回の問題は引っ掛け要素も多く、深くじっくり考えないと正解に辿り着けないものが多いという印象です。

とりあえず私が解いた中では最難関レベルでした。今回受験した方は運が悪かったと思っても良いと思います。その分合格ラインが下がるかもしれませんが・・・。

また問題のテーマが簡単でわかりやすい程、設問の難易度は上がる傾向があると思います。今回は問題のテーマが分かりやすくてとっつきやすかったのですが、プログラムの説明や変数の説明も少なく、実際に解いてみると苦労する問題になっていました。

本ページの図・プログラム・問題文について

図やプログラム、問題文はIPA公開の過去問題から引用しています。また図やプログラムに関しては説明に必要な部分に関してのみ加工して使用させていただいております。

出典:平成30年度 秋期 基本情報技術者試験(FE)試験区分 午後 問8

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です