基本情報技術者試験の最大の難関はアルゴリズム問題です。
アルゴリズムの解説や勉強法、コツを検索すると「トレースしましょう」と言われます。
たしかに、問題文の意味を理解し、プログラムの動き通りに考え、丁寧にトレースすれば全問正解も容易でしょう。
しかし、問題文の解釈が難しい！プログラムの動きが分からない！穴埋めが分からない！丁寧にトレースする時間がない！と多くの人がなるはずです。
私もそうでした。解説を読めば何となく分かるけど解き方が分からない！という状態で、どうやって読めば本番で合格できるのだろう..と悩んでいました。
そこで、基本情報技術者試験の一合格者として、実際に解く際に「どこに着目して、どういうメモを取って、どういう風にトレースしているのか」を解説してみようと思いました。
本記事では平成30年秋期の過去問を使います。
参考書や各種サイトの丁寧で完璧な解説ではなく、合格者のノートや手元を覗き見る気持ちで読んでください。
導入部分を読む
今回の問題は数式を解くプログラムみたいです。答えが予測できそうなのはよいですね。
例があるので使っていきます。
(3)と(4)によると、この問題は「解析処理」と「計算処理」に大きく分けることができるみたいです。
変数がたくさん出てきていますね。
この後詳しい説明が続くのでこの時点では一つ一つ確認する必要はないです。
順番に解いていきたくなる気もわかりますが、ここで丁寧に変数と意味をメモしていると時間がかかりすぎてしまいます。
最初の説明にもあったとおり、Expression[]には元の数式が入っています。
Value[]には数式のうち、数字だけが入っています。二桁の数字は二桁の数字として入っていますね。
Operator[]には演算子が入っています。OpCuntは演算子の数でしょうか？
Priority[]はこの情報だけだとよく分からないですね。。。
※Priorityは優先順位という意味なので優先度を表しているのかな？と予測は可能です。
IT系では頻出の単語なので知らなかったらこれを機に覚えちゃいましょう！
今回の問題はプログラムの穴埋めはないみたいです。
ちょっと分岐が多くてごちゃごちゃしちゃいそうなので簡単にフローチャートを書いてトレースも良いと思います。
あとは如何にも設問にありそうな①～④があります。こちらは先に設問を確認したほうが良いです。
設問の箇所はしっかり、他はざっくり理解で進めると時間をかけずに解くことができます。
設問1を読む
まずは順番に空欄aについて考えてみましょう。
設問で「定数」と言っているのは変数nestに加算している10のことを指しています。
設問から、変数nestとこの定数の値によって演算順序を決めているのだと分かります。
変数nestに関連する処理は①～④のプログラムなので、まずは①～④の箇所だけ処理を日本語で考えてみます。
- ①：＋かー ⇒変数nestに+1したものをPriority[]に格納
- ②：×か÷ ⇒変数nestに+2したものをPriority[]に格納
- ③：（ ⇒変数nestを+10する
- ④：） ⇒変数nestを-10する
どうやらnestは優先度の値を作るベースとなる変数のようです。
四則演算のルールとして、足し算引き算よりも掛け算割り算を優先します。
そして（）の中は（）の外よりも優先するルールもありますね。
これらのルールを優先順位の数字を使ってプログラムは判断しているようです。
①～④の箇所をまとめてみます。
（）の外の足し算引き算は「１」、掛け算割り算は「２」が当てられ、（）の中の足し算引き算は「１１」、掛け算割り算は「１２」が当てられます。さらに（）の内側は「２１」「２２」ですね。
つまりPriorityの数字が高い順に優先的に処理を行います。
優先順位が高い順に数字が大きくなれば良いので、例えば（）の中の足し算引き算を「３」、掛け算割り算を「４」。さらにその中は「５」「６」となっていてもOK（プログラムが解析できる）になります。
選択肢一つ一つ当てはめてみて破綻しないかどうかを確認していきます。
空欄aをトレースして解く
定数を「1」、「2」、「13」とした場合、演算ルールの順位と同じになるかをチェックします。
（）と書いているのは（）の中身という意味です。※メモするときはなるべく簡潔に書きましょう。
定数の候補として、選択肢アとイの境目である１と２。そして選択肢ウとエを同時にチェックする目的で13を選びました。
選択肢アの定数１は、（）の外の掛け算割り算と、（）の中の足し算引き算が同じ優先度になってしまったのでNGです。
選択肢イは区別できるのでOKで、定数の値が大きくなるほど（）の外と中の優先度の数値の差が広がっていくことが分かります。
選択肢ウとエは定数13がOKな時点で不正解になりますが、さらに定数１やそれ以下の数字も含まれてしまうのでNGです。
以上より空欄aに当てはまるのはイになります。
空欄bをトレースして解く
空欄aと同じくnestに加算する定数に関する設問ですが、基準となる条件が異なるようです。
設問の内容を元の整数（priLow = 1, priHigh = 2）で書き直してみます。
- ア：priHigh以上 ＝ 2以上
- イ：priHigh+1以上 = 3以上
- ウ：priHigh-priLow以上 = 1以上
- エ：priHigh-priLow+1以上 = 2以上
元の整数の場合、選択肢アとエの区別ができません。
この設問を解くには選択肢アとエの区別ができる例でトレースする必要があります。
例えば、priLow = 2, priHigh = 3 とすれば各選択肢は下記のようになります。
- ア：priHigh以上 ＝ 3以上
- イ：priHigh+1以上 = 4以上
- ウ：priHigh-priLow以上 = 1以上
- エ：priHigh-priLow+1以上 = 2以上
この例なら大丈夫そうですね。これを使って空欄aを解いた時のように優先順位が正しくなるか検証してみましょう。
このように1はNG、2以上ならOKになるので空欄ｂの答えはエになります。
設問１に関してはプログラムをすべて読まなくても解ける問題になっていました。
事前知識として必要なものも四則演算のルールだけなので「頑張れば誰にでも解ける」という位置づけです。
設問2を読む
続いて設問2を読み進めていきます。
ここでもまずは設問を読んでみて、必要に応じてプログラムを見るようにしましょう。
どうやらこのプログラムは優先順位が等しいときは左から順に計算するようです。私たちもそうですね。
そして左から実行するのか、右から実行するのかは空欄cの部分が決めているようです。
空欄cに関してはプログラムを読まないと解けなさそうです。
プログラムを確認します。
説明に具体例があるので活用していきます。
一番初めのループ条件は「OpCnt>0」で、ループの最後にOpCntの値を-1している記述があります。
プログラムの全体像として「OpCntが0になるまで処理を繰り返す＝OpCntの数だけ処理を行う」というのが見えてきます。
次にこのプログラム自体が大きく3分割できそうです。分かりますか？
私にはこんな感じ見えます。
一番初めの部分は変数ipの値を決める処理、二番目の部分はOperator[ip]の演算子に従って実際に計算する処理、最後の部分は次のループに備える準備をする処理です。
設問は変数ipの値を決める処理に関わる部分なので、とりあえずこの部分だけ真剣に考えてみます。
書き換え前の処理内容が分かれば、どこを書き換えればよいか分かるはずです。
よく解き方のコツとして設問を最初にみましょうとあると思います。
私も大いに賛成なのですが、今回の場合は設問に引っ張られ過ぎると逆に遠回りになってしまうかもしれません。
書き換え問題は書き換え前も重要と覚えておいてください。
さて、該当プログラムの初期値を見てみましょう。
⑤および⑥の箇所から今回重要になる 変数ip と 変数i の初期値が分かります。
それぞれ「 ip = 0, i = 1 」ですね。
これをふまえて⑦の行をみると、Priority[0] ＜ Priority[1] なら変数ipの値を更新すると解釈することができます。
少し戻って図1から考えると、「2＜11」なら変数ipの値を1にすると解釈できます。
今回は当てはまるので更新です。
ループの2回目はどうでしょう。変数iも更新されて⑦行の条件はPriority[1] ＜ Priority[2] なら変数ipの値を更新するになります。
これも条件を満たすので変数ipは更新されます。
ループの3回目はPriority[2] ＜ Priority[3]を満たさないため更新はせず、OpCntまで変数iが到達したためループ終了です。
プログラムの意味は解釈できましたか？
この例では優先度が同じ、つまりPriority[]の値が同じケースがないので別の例で考えます。
時間節約のためには初めからこのケースで考えた方が吉です。
例えばこのような時、今のプログラムでは行⑦の条件が成り立たず、Priority[1]を最初に計算します。
空欄cで書き換え後ではPriority[2]を選ぶようにする必要があります。
何をしているのか、どうすればよいのかが分かったところで選択肢を見ていきます。
空欄ｃを解く
選択肢アは変数ipの初期値を変えてみよう！というものです。
例で考えているOpCntは4なので初期値は3になります。
変数iの初期値は1なので、この変更をすると、Periority[0]の値を比較しないことになってしまいます。
選択肢イとウは変数iの初期値を変えてみよう！というものです。
選択肢イはPriority[4]が最初の比較対象になりますが、そんなものはないので不正解だとすぐに分かります。
選択肢ウはどうでしょう。
最初の行⑦の比較の時に下記のメモのようになりますが、値は更新されません。
よって選択肢ウの場合も書き換え前と同様に左から順に計算されてしまうと分かります。
答えは選択肢エになります。
選択肢エのように「＜」から「≦」とすることで、優先順位が同じときは変数ipの値を更新する。
つまり同じ優先順位があったときに最後に更新される一番右の演算子が選択されていることになります。
このような条件の書き換えはアルゴリズム問題でたまに出ますが、全ての選択肢を正確に理解して時間内に解くのは未経験者にとっては少し難易度が高めです。
講評を見ても正答率は低く、ウと誤答する受験者が多かったようです。
他の設問を解いているうちにプログラムの意味が分かってあっさり正解できることもあるので、絶対にありえないものを外し、あたりをつけて先に進むのも戦略として良いと思います。
空欄dを解く
少し間が空いてしまったのでもう一度設問を確認します。
選択肢はこのようになっていて、ケース１は変わらないみたいですね。
四則演算のルールは分かっているのでプログラムのトレースはせずに、左からと右からで実際に解いてみたいと思います。
ケース２を左から計算するとこのようになります。
右から計算するとこのようになります。
割り算は左からと右からでは結果が変わるようですね。
今回はメモ書きしましたがこの程度なら暗算でOKです。
数学が得意な人はメモを取るまでもなく即答かもしれません。
割り算の結果が変わるということはケース４もNGですね。
ケース3だけ確認してみます。
まずは左から。
次に右から。
これもNGでした。
ちなみにここ、間違える人が多いようです。何を隠そう私も初見の時は引っかかりました。
①のときに「-3-1」と計算してしまいました。
プログラムの気持ちになって、問題になるのだから..と身構えて臨みたいですね。
話がそれましたが、ケース2～4は全て答えが異なったので、空欄dの答えはアになります。
設問3を解く
最後の設問3を読んでいきましょう！
不等号も出てきてしまいました。
そして新たに「2×（-1）」という具体例を提示してもらっているので活用していきます。
穴埋め箇所は図３の中にもあります。
プログラム自体は複雑ではないので地道にトレースしていきます。
トレースする過程で空欄ｆと空欄ｇを埋めていき、最後に空欄eを考えたいと思います。
トレースする
解析処理のプログラムをもう一度載せます。Expression[0]から順番に考えていきましょう。
Expression[0]は「2」なのでValue[OpCnt=0]に2を入れます。
Expression[1]は「×」なのでPriority[OpCnt=0]に「2（nest=0 + 2）」を入れます。
そしてOpCntは+1されて「1」になり、Value[OpCnt=1]に「０」を入れます。
メモはこのようになっています。（OpCntは更新を見込んで正で数えます）
次のExpression[2]は「（」なのでnestの値の更新だけです。今nestは「10」になっています。
Expression[3]は「-」なのでPriority[OpCnt=1]に「11（nest=10 + 1）」を入れます。
そしてOpCntは+1されて「2」になり、Value[OpCnt=2]に「０」を入れます。
Expression[4]は「1」なので「10×Value[2] + 1」をValue[2]に入れます。
ここの処理は2桁以上の数に対応させるための処理です。
Expression[5]は「）」なのでnestの値の更新だけです。今nestは「0」更新されました。
設問の空欄の箇所と見比べると、空欄ｆは「0」なので選択肢イが、空欄ｇは「2」なので選択肢エが正解になります。
空欄ｇのOpCntについては演算子の数を入れるだけで、トレース不要なので確実に取りたいです。
空欄ｅを解く
最後の問題です。
この選択肢を見るとアプローチ方法が2つ出てきます。
一つ目は具体例である「2×（-1）」を使って処理内容を理解し正解を求める。
二つ目は選択肢ア～エすべてを検証できるような例を作成して解析処理から始める。
「2×（-1）」を解くとイの選択肢について検証できますが、他は確定しません。
ア～エを検証するには、例えば「（-2）×（-1）」とすれば良さそうですが、時間内に解けるか..が鍵となってきます。
私は「設問の数」と「かかる時間」を天秤にかけて一つ目のアプローチを選びます。
丁寧にトレースしても正答率は1問分しか上がりません。
さらに今期の問題は全体的にしっかり考えるのに時間がかかる傾向だと思います。
試験時間は他の問題に回した方が合格に近づきます。
と、いうわけで「2×（-1）」の解析処理の結果を使って計算処理のトレースをしていきます。
OpCntは2なので2回計算処理を行います。
Periorityの値が最も高いのはPeriority[1]なので、ip=1を最初に計算します。
演算子は「-」なので処理はこの部分ですね。
Value[ip=1] – Value[ip=1 + 1]なので、「0-1」の結果をValue[1]に格納します。
そしてOpCntを-1して2回目のループに入ります。
ここで着目したいのはValue[1]に入る「0」の存在です。
我々は計算するときに「0」なんて考慮はしませんが、プログラムではこの「0」があるおかげで「-1」とすることができました。
ところでこの「-」が「+」でも計算としては「0+1」で+1と正しい値が入ります。
この「0」は今回が特殊ではなく、符号が入れば毎回同じことが起こります。
勘の良い人ならこの時点で空欄ｅは選択肢エの正しい値になりそうだと予想できるはずです。
念のため2周目も計算処理を追ってみます。
今度の演算子は「×」で同じ列（要素番号が同じ）のValueの値である「2」と、次の値である「-1」をかけてValue[ip=0]に格納します。
このプログラムは最後にValue[0]を答えとして返すので正しい値が返ってきたと結論付けられます。
よって答えはエで問題なさそうです。
おわりに
最後まで読んでくださりありがとうございます。
問題は解けましたか？
今回紹介した解き方がすべてのアルゴリズム問題に適応できるわけではありませんが、一つ一つ読み解いていけば合格へ近づきます。
少しでもアルゴリズム問題に対する苦手意識が減ってくれると嬉しいです。
一合格者の個人的な感想ですが、今期の問題は難しい＆ややこしいで苦戦しました。
この問題が初見で解けなくても全然だめだー！とならないで大丈夫です。
最後に公式の講評を貼っておきます。ご自身の正答率と比較してみてください。
コメント