基本情報技術者試験の最大の難関はアルゴリズム問題です。
アルゴリズムの解説や勉強法、コツを検索すると「トレースしましょう」と言われます。
たしかに、問題文の意味を理解し、プログラムの動き通りに考え、丁寧にトレースすれば全問正解も容易でしょう。
しかし、問題文の解釈が難しい！プログラムの動きが分からない！穴埋めが分からない！丁寧にトレースする時間がない！と多くの人がなるはずです。
私もそうでした。解説を読めば何となく分かるけど解き方が分からない！という状態で、どうやって読めば本番で合格できるのだろう..と悩んでいました。
そこで、基本情報技術者試験の一合格者として、実際に解く際に「どこに着目して、どういうメモを取って、どういう風にトレースしているのか」を解説してみようと思いました。
本記事では平成29年秋期の過去問を使います。
導入部分を読む
まずはどんなことをするのか日本語ベースで読んでいきます。
今回の問題では文字列の誤りを検出するようです。
詳しい方法はこの時点では不明ですが、「検査文字」というものを使って誤り検出ができるようです。
今回使われる文字は表１の30種類ですね。
概要が分かったところで読み進めていきます。
プログラムの説明を読む
プログラムの説明が続くので日本語ベースで理解をしていきます。
ここでは「検査文字の生成」についての説明があります。
すこしややこしい文章なので、後に出てくる具体例を使って確認していきましょう。
具体例を使った確認～検査文字の生成～
今回使う文字列は「i p a _ _」です。※スペースはアンダーバーで表現しています。
これについて(1)の手順を実施し、検査文字「ｆ」が得られるか確認していきます。
①の手順についてメモを書くとこのようになります。
簡単な計算ですが、検査文字が「ｆ」にならなかった際にどこを読み間違えたのかすぐにわかるので、ここはメモに残すことをオススメします。
続いて②の手順です。偶数番目は足すだけなのでミスしにくいです。
③の手順で得られる数字は「32＋19」で51になります。
④の手順は読みにくいので分解して考えていきます。
まず、総和（５１）をN（３０）で割ったあまりを求めます。…④‐１
次に、N（３０）から④-1で求めたあまり（２１）を引きます。…④-2
最後に、④-2で求めたあまりをN（３０）で割りあまりを求めます。…④-3
手順通りに実施すると最終的に９が得られ、数値９に割り当てられている文字は「ｆ」なのでトレース成功です。
具体例を使った確認～検査文字付文字列の検証～
続いて先ほど作成した「i p a _ _ f」について検証してみます。
今回は「誤りはない」と判定されるはずです。
まずは①から確認していきます。
文字列の生成の時のように末尾を一文字目として色々やっていますが、今回は複雑な処理は偶数番目のようです。
末尾に一文字加わった影響で偶数・奇数番目の文字がズレて、計算自体は「検査文字の生成」と同じになりました。
②、③を実施すると総和が「６０」と求まりました。
④の手順で、６０は３０（N）で割り切れるので誤りはないです。
設問１を解く
ここまでで何をやるかを日本語ベースで理解することができました。
続いて設問１はプログラムの穴埋め問題です。
プログラムは２種類あり、それぞれ「検査文字の生成」と「検査文字付文字列の検証」に当たります。
順番に問題を解いていきましょう。
空欄ａ１と空欄ｂを解く
「検査文字の生成」プログラムは関数calcCheckCharacterというもののようです。
文字列（ipa_ _)とその長さ（5）を渡すと検査文字（ｆ）を返してくれるようです。
続いてソースを確認してみます。
ループで文字列の中身の文字をひとつづつ処理を行っています。
変数valueには文字に割り当てられている数字が入ります。
空欄ａ１の分岐の後はTrueなら単純に足しているので偶数番目の処理、Falseなら奇数番目の処理になります。
よって空欄ａ１には「変数is_evenが偶数である」という条件が入ります。
ここで変数is_evenの初期値はFalseであることがソースから読み取れるので、一番最初、つまり1番目＝奇数番目の時に変数is_evenはFalseになっていることが分かります。
さらに１回分の処理が終わると「not is_even」でTrue/Falseを逆転させています。
空欄ａ１ではis_evenが偶数（True）ならTrue分岐の処理に流したいので、「true」が入ります。
続いて空欄ｂの選択肢を見ると、総和の変数sumを使った処理、手順で言うと④に当たります。
手順を再度確認してみます。
選択肢を解釈すると、
- ア：Nから、総和をNで割った余りを引く。
- イ：総和をNで割った余り。
- ウ：Nから、総和をNで割った余りを引く。さらにその結果をNで割った余り。
- エ：総和からNを引く。さらにその結果をNで割った余り。
上記のようになるので答えはウです。
空欄ａ２と空欄ｃを解く
続いて「検査文字付文字列の検証」に関する設問を解いていきます。
プログラムは下記の通りです。
まず空欄ａ２については先ほどと同様偶数か、奇数かを確認すれば解けそうです。
変数is_oddの初期値はTrueなので、初手の奇数番目の時にTrueとなっていると分かります。
分岐条件はどうでしょう。
ただ足すシンプルな処理は奇数番目の時でした。よって空欄ａ２は「is_oddがtrueなら」という条件が当てはまります。
空欄ａ１にも「true」が当てはまったので答えはエになります。
続いて空欄ｃですが、これは文字列に対するループがすべて終了した時点で、返却値をTrueにするかFlaseにするかと決める条件分岐です。
空欄ｃの条件に当てはまるとFalse、つまり誤りありと判断されます。
手順を再度確認すると、「Nで割り切れないと誤り」となるようです。
つまり、Nで割った余りが0以外なら..と言い換えられるので答えはエになります。
設問２を解く
次の問題を解いていきます。
誤りがないと判断されるのはどれでしょう。
実はこの問題、処理を理解していれば一つ一つトレースしなくても解くことができるのです。
先ほど書いたメモを見てほしいです。
①と②に関して足し算の順番を変えても総和は同じになりますね。
例えば②。今「19+0+9」としていますが、「0+19+9」でも同じ答えになります。
同じ答えになれば最終的な③の総和も同じになるので割り切れてしまいます。
つまり、偶数/奇数番目さえ守っていれば順番を入れ替えてもプログラムには気づかれないのです。
さて、これをふまえてもう一度各ケースの文字を見てみましょう。
偶数番目と奇数番目に使われている文字が同じケースはケース２とケース４だと分かります。
空欄ｄの答えはオになります。
設問３を解く
続いて設問３を解きます。
設問２，３，４と大問が多く嫌になるかもしれませんが、逆に深い部分は聞かれないともとらえられるので前向きに解いていきます。
今まで横方向だけだったのが縦方向にも拡張したようです。
縦方向にも文字の長さをmとして検査文字列を生成するようです。
文字列を「 _ s _ _ 」として検査文字を作るようです。
これはソースをトレースしなくても最初の日本語の手順を追えばよいので楽勝です。
もし不安なら検査文字ｒ、ａ、ｖ、ｂのいずれかを使ってちゃんと縦方向にも生成されるか、自分の理解している生成手順があっているかを確認するのも手です。
ここは時間との相談です。ここまで10～15分で解けていれば念のため確認してから本題でもよいと思います。
計算すると15になったので文字としては「ｌ」になります。答えはウです。
設問４を解く
いよいよ最後の問題です。
設問２の時のように異なる文字列を入れてもプログラムをだませるのか？という問題です。
設問２からケース２とケース４は可能性があるので見ていきます。
縦方向に関しても偶数/奇数番目を守りつつ順番を入れ替えられていればプログラムを騙すことができます。
しかし、縦方向で考えるとどのケースも使う文字が変わってしまうのでしっかりと誤りと検出されてしまいます。
よって答えはカです。
おわりに
最後まで読んでくださりありがとうございます。
問題は解けましたか？
今回紹介した解き方がすべてのアルゴリズム問題に適応できるわけではありませんが、一つ一つ読み解いていけば合格へ近づきます。
少しでもアルゴリズム問題に対する苦手意識が減ってくれると嬉しいです。
一合格者の個人的な感想ですが、今期の問題はソースコードが理解できなくても解ける未経験者に非常に優しい内容となっています。
ただ、ロジック・考え方の練習にはなると思いますのでしっかり理解していきましょう。
また、ソースを追うのではなく、日本語ベースで問題を解く練習にもなります。
日本語ベースで問題を解けるようになると一気に時間短縮に繋がります。
ぜひチャレンジしてみてください。
最後に公式の講評を貼っておきます。ご自身の正答率と比較してみてください。
コメント