平成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の値を増減させる定数がどんな条件の場合に「正しい計算順序が保証されるか」を問う問題になっています。

問われているのが、「正しい計算順序が保証される」場合の nest の値を増減させる定数の条件ですので、1つのパターンでも正しい計算順序が保証されない場合、その条件の選択肢は [  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 さんのコメント を参考にさせていただきました。ご指摘大変ありがとうございました。

設問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

アルゴリズム問題の対策(PR)

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

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

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

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

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

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

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

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

同じカテゴリのページ一覧を表示

10 COMMENTS

桂田

なぜpriority[]の2番目は11なのですか?2+10+1で13だと思うのですが。

返信する
daeu

桂田さん

コメントありがとうございます!

ご指摘の箇所は設問3の表内の 11 の部分(’-‘ の priority)ですよね?

おそらくこれは 11 で合っていると思います。問題集や他のサイトも確認しましたが同じく 11 でした。

ポイントは①②の処理の部分で、ある演算子に対する priority の値はあくまでも nest に対して +1 もしくは +2 することで計算されます。

具体的には、演算子が +- の場合は +1 で、×÷ の場合は +2 されます。

また nest は、その演算までの ‘(‘ と ‘)‘ の数で決まります。

つまり、ある演算子の priority の値が影響するのは、その演算子の種類と、その演算子までの ‘(‘ と ‘)‘ の個数のみです。式にどれだけ他の演算子があったとしても、priority の値には影響しません。

ですので、ご指摘の式の場合は ‘-‘ の演算子までに ‘ב がありますが、priority を計算する上ではこの演算子は関係ありません。

単純に、’-‘ の priority は、’-‘ までに存在する ‘(‘ と ‘)‘ の数によって決まる nest(’(‘ のみ存在するので 10)と、演算子の種類によって決まる値(’-‘ なので 1)を足した値、つまり 10+111 になります。

返信する
ナス

丁寧にまとめていただいていて大変勉強になりました。
上でコメントした方と同じく誤った認識をしていたためドツボにはまっていました。
演算子のif文でもnestに代入されている値が変わってしまうと思っていました。。。

返信する
daeu

ナスさん

コメントありがとうございます!(返信遅れてすみません…)。
もし参考になったようであれば嬉しいです!

確かに数学的に考えると演算子を考慮して nest も変更した方がよさそうな気もするんですよね…。ちょっと引っ掛け的な問題になっているのかもしれません…。

アルゴリズム問題のプログラムの動作を追うような場合は、問題文とプログラム以外の前提知識や先入観は捨て、無心になってとにかくプログラムに書いてあることだけを処理するように考えたほうが正解しやすいのかなぁという気もします。
#的外れなアドバイスになってたらごめんなさい…

返信する
gg

さらに、演算子である + – に対してはnest+1を × ÷ に対してはnest+2をPriority[ ]に設定しているようです。

この部分で、私の解釈になってしまいますが nest+1 は +  nest+2 は -
という解釈になってしまって混乱しております

なぜそう考えられるのでしょうか

返信する
daeu

gg さん

コメントありがとうございます!

>さらに、演算子である + – に対してはnest+1を × ÷ に対してはnest+2をPriority[ ]に設定しているようです。

上記は、問題の [プログラム(解析処理の部分)] における下記部分から判断して記述しています。

①の部分が、nest + 1 を Priority[OpCnt] に格納する処理であり、この①の部分は下の図で説明されている矢印の意味を考えると、chr が ‘+’ もしくは ‘-‘ の場合に実行されることになります。

また、上記以外の場合は②の部分の処理が実行されて、nest + 2 が Priority[OpCnt] に格納されることになります。

なので、下記のことが言えると思っています。
>さらに、演算子である + – に対してはnest+1を × ÷ に対してはnest+2をPriority[ ]に設定しているようです。

質問の意図にあった回答になっていますでしょうか?

返信する
gg

返信ありがとうございます
疑似言語をまだ勉強していないので、わかっておりませんでした。
こちらの、調べ不足でした。すみません。
解説は、理解できましたのでとてもすっきりしました

返信する
daeu

gg さん

ご返信ありがとうございます。
疑問が解決したようで私としても嬉しいです!

疑似言語で使われている各記号については問題用紙中にも記載されていますので(H30秋の場合はP.3とP.4)、
ここは頭に入れておくと良いと思います(この記号は毎年固定なはず)。

返信する
I

設問1の[ b ]の解法に誤りがあるのではないでしょうか。

> nest の値を増減する定数がbのときに限り正しい演算順序が保証される

とあるので、確実に選択肢エのパターンでしか演算順序が保証されないはずです。
それを踏まえた、正しい解法は以下の通りだと思われます。

priHigh = 0, priLow = -1 のようにpriHighが0以下のケースを考えたときに、

ア.nestが0となり、nest + priLow をしても priHighを上回ることができない
イ.nestが1となり、nest + priLow をしても priHighを上回ることができない
ウ.記事の解説通りのパターンに対応できない
エ.nestが2となり、nest + priLowが1となる。そのためpriHighを上回り、演算順序が保証される

ご参考になれば幸いです。

返信する
daeu

I さん

コメントありがとうございます!

提示された解法の方が、確かに適切だと思います…。
まずは内容を精査し、本日中にでも記事の修正をさせていただきたいと思います。
その際は、本コメントを参考にさせてください。
ご指摘大変ありがとうございました。

返信する

daeu へ返信する コメントをキャンセル

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