平成２９年度秋期午後のアルゴリズム問題である問８の私の解き方・考え方について解説していきます。
問題
IPAの公式サイトで公開されています。このページでは問８についての解説を行います。
https://www.jitec.ipa.go.jp/1_04hanni_sukiru/mondai_kaitou_2017h29_2/2017h29a_fe_pm_qs.pdf
問題の概要
この回の問題は検査文字についての問題でした。
検査文字というのは、例えば受信した文字列が本当に正しいのか？を調べるときなどに用いられる技術です。検査文字を用いれば、携帯のメールで受信した文字列ががノイズなどによって間違ったものになっている場合に、送信元に再送信を要求したりすることができます。
それでは問題を見ていきましょう。
重要なのは[プログラムの説明]部分だと思います。ここでしっかり検査文字をどうやって生成し、どうやってその検査文字で文字列が正しいかどうかを判断しているかを理解すればこの問題は解けます。
[検査文字付文字列の生成例]では実際に「ipa__（下カッコの出し方がわからないので”_”で書いています）」に対する検査文字が”f”であることを書いてくれています。こういった具体例を自分で試して見るのはアルゴリズムの理解にかなり役に立ちますので、実際に自分でも”f”が導けることを確認しておきましょう。プログラムの仕様についても目を通しておきましょう。スポンサーリンク
設問１
それでは設問１を解いていきましょう。設問１に関しては[プログラムの説明]を読みながら解けば正解できます。
[ a ]は（１）検査文字の生成に関する問題です。①文字列の末尾の文字を1番目の文字とし、文字列の先頭に向かって奇数番目の文字に割り当てた数値を2倍してNで割り、商と余りの和を求め、全て足し合わせる。
②偶数番目の文字に割り当てた数値はそのまま全て足し合わせる。
①はなかなか難しい文ですが②は分かりやすいですね。この①②がプログラム上で表れているのが書き部分になります。
この分岐文の上側（YES側）が②の処理だということはすぐ分かりますね。逆に下側（NO側）は①です。まだプログラムの方が分かりやすい？！
つまりis_even = [ a1 ]の部分は偶数番目の文字かどうかを判断していると言えます。ではis_evenはtrueかfalse、どちらの時に偶数と判断できるでしょうか。
is_evenの使われ方を見てみましょう。
このループは文字列の末尾から計算していくためにiをlenで初期化しています。ループの直前でis_evenはfalseで初期化されていますので1番目の文字の時はis_evenはfalseで処理されます。1番目なので奇数として処理必要ができます。なのでis_evenは偶数の時にtrueが格納される変数と考えて良さそうです。
ループが終わるたびに、文字が先頭に向かって１進むごとにfalseとtrueを逆にしているのもわかります。末尾から2文字目ではtrue、3文字目はfalseになりますのめやはりこの推測で合っていそうです。
ですので[ a1 ]は「true」です。
[ a2 ]は（２）検査文字付文字列の検証に関する問題ですが、同様の考え方で答えは導け出せます。[ a2 ]も答えは「true」になります。続いて[ b ]を埋めましょう。
ループが終わっているので（１）の③が終了したと考えられます。なので次は④を行うと考えることができ、[ b ]はその④をプログラムで表現したもので埋めてやれば良さそうです。
④Nから③で求めた総和をNで割った余りを引く。さらにその結果をNで割り、余りを求める。求めた数値に対応する文字を検査文字とする。
割った余りを求める際に用いる演算子は「％」です。
まず③で求めた総和をNで割った余りは
value % N
で求めることができ、Nからこの数引くのは
N – value % N
で実行できます。さらにこの結果をNで割った余りを求める処理は
(N- value % N) % N
で実行できます。ですので、この式が[ b ]の答えになります。
[ c ]も同様にして（２）の④から答えを導き出すことができます。 [ c ]は判断文であり、これがYESの時にfalseを返すようですNで割り切れる場合は誤りがないと判断でき、表３より誤りがある場合にfalseを返却する関数なので、この条件式としては
value % N ≠ 0
を選択すれば良いです。[ c ]の答えは↑です。
設問２
これは全てのパターンで誤りがあると判断されるか、判断されないかを確かめてみれば誰でも答えが導け出せます。
もう少しスマートに考えるのであれば、検査文字を求める際に求める処理は偶数文字目か奇数文字目かによって変化します。逆に偶数文字目は全て同じ計算方法で、奇数文字目も全て同じ計算方法です。何文字目かどうかは偶数か奇数か以外では関係ありません。
ですので、偶数番目の文字同士もしくは奇数番目の文字同士であれば（２文字目と４文字目、５文字目と７文字目、などなど）文字を入れ替えても検査文字は変わりません。
この考え方で答えを考えると、１文字目と３文字目を入れ替えているイと１文字目と５文字目、２文字目と４文字目を入れ替えているエは検査文字が変化しないので誤りはないと判断されます。
設問３
設問１では文字列を横方向に対してのみ検査を行っていましたが、設問３では縦方向に対しても検査を行うようになっています。問題が２次元的になって難しそうに見えますが、設問１を理解すれば設問３も楽々解けます。
設問１では上図の緑枠のような横方向の検査文字のみを考えていましたが、設問３では青枠のような縦方向についても検査文字を計算するようになっています。ただ計算方法は緑枠側と全く同じで、例えば青枠であれば「ask.」という文字列に対する検査文字を設問１で説明されていた計算方法と全く同じことを実行してやれば「v」を求めることが可能です。
ですので[ e ]に関しては[_s__」に対する検査文字を設問１と同様に[プログラムの説明」（１）に記載されている計算方法で求めてやれば良いだけです。
最初は「①文字列の末尾の文字を1番目の文字とし、文字列の先頭に向かって奇数番目の文字に割り当てた数値を2倍してNで割り、商と余りの和を求め、全て足し合わせる。」を行います。
末尾から１文字目の空白文字「_」は割り当てられている数値が0なので計算結果も0になります。
末尾から３文字目の「s」に関しては割り当てられている数値が22です。ですので、
(22 * 2) / 30 + (22 * 2) % 30により答えは求まります。計算結果は15になります。１文字目と３文字目の総和は15になります。
続いて「②偶数番目の文字に割り当てた数値はそのまま全て足し合わせる。」を行いますが、２文字目も４文字目も空白文字なので総和は0です。
さらに③で①と②の結果を足し合わせます。結果は15です。
最後に「④Nから③で求めた総和をNで割った余りを引く。さらにその結果をNで割り、余りを求める。求めた数値に対応する文字を検査文字とする。」を行います。
③で求めた総和は15なので、
(N – (15 % N)) % N を計算すれば結果は15になり、表１より検査文字が「l」であることが導け出せます。
スポンサーリンク
設問４
こちらは設問２の応用になります。設問２同様に表４の全てのケースを１行目に当てはめて検査文字を算出してみれば必ず答えが導け出せます。
設問２の場合は検査文字が１つでしたが、設問４の場合は検査文字が最終列に４つ、最終行に５つあるので計９つになります。この９つのうち１つでも１行目を「ipa__」とした時から変化するものがあれば、それは「誤りがある」と判断できますので、試してみて１つでも変化するものがあった時点でその文字列に対する検査は終了しても問題ありません。
なのでまず表４のケース１とケース３に関しては、下の図のピンク枠の部分が「f」以外になることは設問２で解いているはずなので、この問題ではもう考える必要がありません。ケース１とケース３は「謝りがある」と判断される文字列です。
ケース２とケース４についても１列目の検査文字から求めて行ってみると、両方とも１列目の検査文字が「r」以外になります。なのでケース２とケース４も「誤りがある」と判断されることになります。
したがって「誤りがない」と判断されるケースはありませんが答えになります。
解いてみた感想
H３０春の問題よりは簡単だと思いました。
検査文字と聞くと難しそうに感じるかもしれませんが、結局問題文を読めば仕組みは簡単に理解できると思います。
ただこの問題の場合、計算が結構複雑なので計算間違いをしないよう気をつけることが重要ですね。
また後半の設問は前半の設問の応用の問題になっています。ですので、前半で考え方が間違っていたらこの午後の問８総崩れになる可能性も高いです。
特に前半側の問題は慎重にじっくり問題読んで理解するようにしましょう。
★オススメページ★
下記ページから他の回の解説もたどれます。他の回のアルゴリズム問題の解き方がわからない場合は是非読んでみてください！
基本情報技術者試験 午後問題「アルゴリズム」過去問の解き方 解説 まとめ
本ページの図・プログラム・問題文について
図やプログラム、問題文はIPA公開の過去問題から引用しています。また図やプログラムに関しては説明に必要な部分に関してのみ加工して使用させていただいております。
出典：平成２９年度 秋期 基本情報技術者試験（FE）試験区分 午後 問８
アルゴリズム問題の対策（PR）
過去問を解いてみて感触はいかがだったでしょうか？
全く分からなかった...という方もいらっしゃるかもしれません。はっきりいってアルゴリズム問題は、特に慣れないと難易度は高いです。
なので、こういった方にはもっと "簡単なアルゴリズム問題を解いて慣れていく" ことをオススメします。で、この簡単なアルゴリズム問題を解くのにオススメの本が下記の うかる！ 基本情報技術者 [午後・アルゴリズム編] です。
オススメする理由は、特に本の前半部分で難易度の低いアルゴリズムの紹介や解説が行われているところです。こういったアルゴリズムの動作などを実際にトレースして追ってみたりすることで簡単な問題からアルゴリズム問題に慣れていくことができます。
また、「アルゴリズムとは？」といったアルゴリズム入門から解説してくれているので、プログラミングをやったことない方にも親切な内容になっています。
アルゴリズム問題に全く手がつかないというような方は、まずは上記のような本でアルゴリズムに慣れるのがオススメです。
慣れてきたら、あとは実際の過去問を解いて "さらに考える力を養う" ＆ "実際のアルゴリズム問題に慣れる" のが良いと思います。
私のサイトでも過去問の解説をしていますので是非参考にしてください。私の解説だけでなく、他の人の解説も参考にしたいような場合には、下記のような過去問の参考書もオススメです（アルゴリズム問題だけでなく、全問題の解説も充実しています）。
