平成３０年（H３０）秋期 基本情報技術者試験 アルゴリズム問題 解き方解説

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

問題

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

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

問題の概要

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

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

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

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

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

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

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

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

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

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

スポンサーリンク

設問１

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

問われているのが、「正しい計算順序が保証される」場合の nest の値を増減させる定数の条件ですので、１つのパターンでも正しい計算順序が保証されない場合、その条件の選択肢は [  b  ] の答えとしては相応しくないということになります。なので、各選択肢で示される条件で、計算順序が保証されないケースを見つけ出してやれば、その選択肢は消すことができます。

ここで、問題で取り扱われているプログラムを思い出すと、このプログラムでは括弧内の演算子の計算優先度を括弧外の演算子の計算優先度よりも高く設定することで、括弧内の演算子による計算を早く実行することを実現しています。

そして、この括弧内の演算子の計算優先度を高く設定するために nest という変数を用意し、左括弧が見つかった際には、nest の値を定数分だけ増加させ、さらに右括弧が見つかった際には nest の値を定数分だけ減少させるような処理を行なっています。

これにより、定数が選択肢アイウエのいずれかを満たす場合、必ず括弧内の演算子が括弧外の演算子よりも計算優先度が高くなることになります。

で、ここで明らかなのは、括弧外の演算子よりも括弧内の演算子の方の計算優先度を高くするためには、その定数は 1 以上でなければならないという点になります。

もし定数が負の値である場合、左括弧が現れるたびに nest の値が小さくなるので、括弧内の計算優先度は括弧外の計算優先度よりも低くなります。

また、定数が 0 である場合、括弧の有無に関わらず nest の値は変わりませんので、括弧内の計算優先度は括弧外の計算優先度と同じということになります。そのため、括弧内の演算子の計算が先に行われることは保証されません。

ですので、定数が負の値や 0 となり得る条件は、「正しい計算順序が保証される定数」の条件には当てはまらないことになります。

したがって、アとイに関しては、この時点で選択肢から消すことができます。なぜなら、アに関しては priHigh が 0 以下の場合、定数の値が 0 になり得るからです。また、イに関しては priHigh が -1 以下の場合、定数の値が 0 になり得ます。

なので、選択肢として残るのはウとエのみになります。これらは、priHigh > priLow という条件があるため、定数の値が 0 にはなることはありません。

ですが、ウに関しても選択肢から消すことができます。なぜなら、priHigh が 2 かつ priLow が 1 の場合、ウの選択肢は「1以上」と捉えることができます。

しかし、[  a  ] の答えを導く際に、定数が 1 の場合は成立しないことを既に確認しています。そのため、ウの条件においても正しい計算順序とならないことがあるため、選択肢ウも消すことができます。

したがって、[  b  ] の答えは残った選択肢エの「priHigh – priLow + 1以上」となります。

特に、選択肢アイエに関しては priHigh=0・priLow=-1 とし、例で示された計算式を用いてプログラムの動きを追ってみると、アとイの場合は正しい順序で計算されないこと、さらにエの場合は正しい順序で計算されることが確認できると思いまし。

この辺りの解説や実例に関しては I さんのコメント を参考にさせていただきました。ご指摘大変ありがとうございました。

設問２

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

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

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

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

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

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

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

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

設問３

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

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

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

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

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

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

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

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

スポンサーリンク

解いてみた感想

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

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

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

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

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

★オススメページ★
下記ページから他の回の解説もたどれます。他の回のアルゴリズム問題の解き方がわからない場合は是非読んでみてください！

基本情報技術者試験 午後問題「アルゴリズム」過去問の解き方 解説 まとめ

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

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

出典：平成３０年度 秋期 基本情報技術者試験（FE）試験区分 午後 問８

アルゴリズム問題の対策（PR）

過去問を解いてみて感触はいかがだったでしょうか？

全く分からなかった...という方もいらっしゃるかもしれません。はっきりいってアルゴリズム問題は、特に慣れないと難易度は高いです。

なので、こういった方にはもっと "簡単なアルゴリズム問題を解いて慣れていく" ことをオススメします。で、この簡単なアルゴリズム問題を解くのにオススメの本が下記の うかる！ 基本情報技術者　[午後・アルゴリズム編] です。

うかる！ 基本情報技術者　[午後・アルゴリズム編]　2022年版

posted with ヨメレバ

福嶋 宏訓 日経BP 日本経済新聞出版本部 2021年11月25日頃

楽天ブックス

Amazon

Kindle

 

オススメする理由は、特に本の前半部分で難易度の低いアルゴリズムの紹介や解説が行われているところです。こういったアルゴリズムの動作などを実際にトレースして追ってみたりすることで簡単な問題からアルゴリズム問題に慣れていくことができます。

また、「アルゴリズムとは？」といったアルゴリズム入門から解説してくれているので、プログラミングをやったことない方にも親切な内容になっています。

アルゴリズム問題に全く手がつかないというような方は、まずは上記のような本でアルゴリズムに慣れるのがオススメです。

慣れてきたら、あとは実際の過去問を解いて "さらに考える力を養う" ＆ "実際のアルゴリズム問題に慣れる" のが良いと思います。

私のサイトでも過去問の解説をしていますので是非参考にしてください。私の解説だけでなく、他の人の解説も参考にしたいような場合には、下記のような過去問の参考書もオススメです（アルゴリズム問題だけでなく、全問題の解説も充実しています）。

令和04年【上期】基本情報技術者 パーフェクトラーニング過去問題集

posted with ヨメレバ

山本三雄 技術評論社 2021年11月26日頃

楽天ブックス

Amazon

Kindle