平成29年(H29)秋期 基本情報技術者試験 アルゴリズム問題 解き方解説

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

問題

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

https://www.jitec.ipa.go.jp/1_04hanni_sukiru/mondai_kaitou_2017h29_2/2017h29a_fe_pm_qs.pdf

問題の概要

この回の問題は検査文字についての問題でした。

検査文字というのは、例えば受信した文字列が本当に正しいのか?を調べるときなどに用いられる技術です。検査文字を用いれば、携帯のメールで受信した文字列ががノイズなどによって間違ったものになっている場合に、送信元に再送信を要求したりすることができます。

それでは問題を見ていきましょう。

重要なのは[プログラムの説明]部分だと思います。ここでしっかり検査文字をどうやって生成し、どうやってその検査文字で文字列が正しいかどうかを判断しているかを理解すればこの問題は解けます。

[検査文字付文字列の生成例]では実際に「ipa__(下カッコの出し方がわからないので”_”で書いています)」に対する検査文字が”f”であることを書いてくれています。こういった具体例を自分で試して見るのはアルゴリズムの理解にかなり役に立ちますので、実際に自分でも”f”が導けることを確認しておきましょう。プログラムの仕様についても目を通しておきましょう。

スポンサーリンク

設問1

それでは設問1を解いていきましょう。設問1に関しては[プログラムの説明]を読みながら解けば正解できます。

[   a   ]は(1)検査文字の生成に関する問題です。

①文字列の末尾の文字を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が格納される変数と考えて良さそうです。

ループが終わるたびに、文字が先頭に向かって1進むごとにfalseとtrueを逆にしているのもわかります。末尾から2文字目ではtrue、3文字目はfalseになりますのめやはりこの推測で合っていそうです。

ですので[   a1   ]は「true」です。

[   a2   ]は(2)検査文字付文字列の検証に関する問題ですが、同様の考え方で答えは導け出せます。[   a2   ]も答えは「true」になります。

続いて[   b   ]を埋めましょう。

ループが終わっているので(1)の③が終了したと考えられます。なので次は④を行うと考えることができ、[   b   ]はその④をプログラムで表現したもので埋めてやれば良さそうです。

④Nから③で求めた総和をNで割った余りを引く。さらにその結果をNで割り、余りを求める。求めた数値に対応する文字を検査文字とする。

割った余りを求める際に用いる演算子は「%」です。

まず③で求めた総和をNで割った余りは

value % N

で求めることができ、Nからこの数引くのは

N – value % N

で実行できます。さらにこの結果をNで割った余りを求める処理は

(N- value % N) % N

で実行できます。ですので、この式が[   b   ]の答えになります。

[   c   ]も同様にして(2)の④から答えを導き出すことができます。

[   c   ]は判断文であり、これがYESの時にfalseを返すようですNで割り切れる場合は誤りがないと判断でき、表3より誤りがある場合にfalseを返却する関数なので、

この条件式としては

value % N ≠ 0

を選択すれば良いです。[   c   ]の答えは↑です。

設問2

これは全てのパターンで誤りがあると判断されるか、判断されないかを確かめてみれば誰でも答えが導け出せます。

もう少しスマートに考えるのであれば、検査文字を求める際に求める処理は偶数文字目か奇数文字目かによって変化します。逆に偶数文字目は全て同じ計算方法で、奇数文字目も全て同じ計算方法です。何文字目かどうかは偶数か奇数か以外では関係ありません。

ですので、偶数番目の文字同士もしくは奇数番目の文字同士であれば(2文字目と4文字目、5文字目と7文字目、などなど)文字を入れ替えても検査文字は変わりません

この考え方で答えを考えると、1文字目と3文字目を入れ替えているイと1文字目と5文字目、2文字目と4文字目を入れ替えているエは検査文字が変化しないので誤りはないと判断されます。

設問3

設問1では文字列を横方向に対してのみ検査を行っていましたが、設問3では縦方向に対しても検査を行うようになっています。問題が2次元的になって難しそうに見えますが、設問1を理解すれば設問3も楽々解けます。

 

設問1では上図の緑枠のような横方向の検査文字のみを考えていましたが、設問3では青枠のような縦方向についても検査文字を計算するようになっています。ただ計算方法は緑枠側と全く同じで、例えば青枠であれば「ask.」という文字列に対する検査文字を設問1で説明されていた計算方法と全く同じことを実行してやれば「v」を求めることが可能です。

ですので[   e   ]に関しては[_s__」に対する検査文字を設問1と同様に[プログラムの説明」(1)に記載されている計算方法で求めてやれば良いだけです。

最初は「①文字列の末尾の文字を1番目の文字とし、文字列の先頭に向かって奇数番目の文字に割り当てた数値を2倍してNで割り、商と余りの和を求め、全て足し合わせる。」を行います。

末尾から1文字目の空白文字「_」は割り当てられている数値が0なので計算結果も0になります。

末尾から3文字目の「s」に関しては割り当てられている数値が22です。ですので、

(22 * 2) / 30 + (22 * 2) % 30により答えは求まります。計算結果は15になります。1文字目と3文字目の総和は15になります。

続いて「②偶数番目の文字に割り当てた数値はそのまま全て足し合わせる。」を行いますが、2文字目も4文字目も空白文字なので総和は0です。

さらに③で①と②の結果を足し合わせます。結果は15です。

最後に「④Nから③で求めた総和をNで割った余りを引く。さらにその結果をNで割り、余りを求める。求めた数値に対応する文字を検査文字とする。」を行います。

③で求めた総和は15なので、

(N – (15 % N)) % N を計算すれば結果は15になり、表1より検査文字が「l」であることが導け出せます。

スポンサーリンク

設問4

こちらは設問2の応用になります。設問2同様に表4の全てのケースを1行目に当てはめて検査文字を算出してみれば必ず答えが導け出せます

設問2の場合は検査文字が1つでしたが、設問4の場合は検査文字が最終列に4つ、最終行に5つあるので計9つになります。この9つのうち1つでも1行目を「ipa__」とした時から変化するものがあれば、それは「誤りがある」と判断できますので、試してみて1つでも変化するものがあった時点でその文字列に対する検査は終了しても問題ありません。

なのでまず表4のケース1とケース3に関しては、下の図のピンク枠の部分が「f」以外になることは設問2で解いているはずなので、この問題ではもう考える必要がありません。ケース1とケース3は「謝りがある」と判断される文字列です。

 

ケース2とケース4についても1列目の検査文字から求めて行ってみると、両方とも1列目の検査文字が「r」以外になります。なのでケース2とケース4も「誤りがある」と判断されることになります。

したがって「誤りがない」と判断されるケースはありませんが答えになります。

解いてみた感想

H30春の問題よりは簡単だと思いました。

検査文字と聞くと難しそうに感じるかもしれませんが、結局問題文を読めば仕組みは簡単に理解できると思います。

ただこの問題の場合、計算が結構複雑なので計算間違いをしないよう気をつけることが重要ですね。

また後半の設問は前半の設問の応用の問題になっています。ですので、前半で考え方が間違っていたらこの午後の問8総崩れになる可能性も高いです。

特に前半側の問題は慎重にじっくり問題読んで理解するようにしましょう。

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

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

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

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

出典:平成29年度 秋期 基本情報技術者試験(FE)試験区分 午後 問8

コメントを残す

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