平成２８年度春期午後のアルゴリズム問題である問８の私の解き方・考え方について解説していきます。
問題
IPAの公式サイトで公開されています。このページでは問８についての解説を行います。
https://www.jitec.ipa.go.jp/1_04hanni_sukiru/mondai_kaitou_2016h28_1/2016h28h_fe_pm_qs.pdf
問題の概要
配列の要素の削除や追加等の管理の問題です。
スポンサーリンク
設問１
[プログラムの説明]の特に各関数の説明は図付きの説明で、どういったことを行う関数かのイメージはかなり湧きやすいと思います。
どういった関数があるかをしっかり把握しておいて、設問１を問いて行きましょう。
[ a ]と[ b ]はaddMemo関数に関するものです。下の図は図３の状態からaddMemo(3, “ino”)を実行した時の例です。皆さんも解くときは実際にこの関数を実行したらどのような結果になるかを考えて解くとわかりやすいと思います。
この図やaddMemo関数の仕様から分かるように、addMemo(3, “ino”)を実行すると下記のような処理が行われます。
①Memo[MemoCnt(4)]にDataLen(19)を格納する
②Data[DataLen(19)]にtextLen(3)を格納する
③Data[DataLen(19) + 1]からtextLen(3)分、text(ino)の文字列をコピー
④MemoCnt(4)を1増やす（5になる）
⑤DataLen(19)をtextLen(3)+1増やす（23になる）
このような処理が実行されることを頭に入れて[ a ]と[ b ]を解いていきましょう。
上記の処理とプログラムの対応を見ると下記のようになっています。
①ではMemo[MemoCnt]にDataLenを格納するので、[ a ]の答えはDataLenとなります。
⑤は上記の処理そのままをプログラムに置き換えると上手くいきません。なぜならプログラムでは③の直前でDataLenの値をすでに1増やしているからです。ですので、プログラムの⑤ではDataLenにDataLenをtextLen分増やしてやった値を格納する必要があります。したがって[ b ]の答えはDataLen + textLenとなります。
続いて[ c ]を解いていきます。[ c ]の穴埋めはdeleteMemo関数に関するものです。下の図は図３の状態からdeleteMemo(1)を実行した時の例です。
この図やdeleteMemo関数の仕様から分かるように、deleteMemo(1)を実行すると下記のような処理が行われます。
①pos+1以降のMemo[ ]を１つ後ろに移動
②MemoCnt(4)を1減らす（3になる）
上記の処理とプログラムの対応を見ると下記のようになっています。
プログラムの①ではMemo[i – 1]にMemo[i]の値を代入し、それをiがMemoCntになるまで繰り返しています。
Memo[i – 1]に Memo[i]にコピーしていっているので、iの初期値である[ c ]はpos+1になります。
iの初期値をposにしてしまうと、関係ないMemo[i – 1]の値が変わってしまいますし、posが0のときにMemo[-1]になってしまいおかしな領域にアクセスしてしまい関数が成立しません。
アルゴリズム問題では結構この「+1」するか、「-1」するか、のあたりで迷うことも多いですが、それぞれのケースで実際にプログラムを追ってみて成立するものを探し出す方法が良いと思います。
次は[ d ]を解いていきます。[ d ]の穴埋めはmoveMemo関数に関するものです。moveMemo関数は引数のfromPosとtoPosの大小関係で処理が異なります。[ d ]があるのはfromPosがtoPosよりも大きい場合のプログラムです。ですので今回はそちらのケースに絞って見ていきましょう。
下の図は図３の状態からmoveMemo(3, 1)を実行した時の例です。
この図やmoveMemo関数の仕様から分かるように、moveMemo(3, 1)を実行すると下記のような処理が行われます。
①一旦Memo[fromPos(3)]の値を他の変数に退避
②toPosからfromPos-1のMemo[ ]を１つ後ろに移動
③①で退避した値をMemo[toPos(1)]へ格納
上記の処理とプログラムの対応を見ると下記のようになっています。
「②toPosからfromPos-1のMemo[ ]を１つ後ろに移動」を行うためにiに対するループの設定が[ d ]の答えになります。
候補は２つあると思います。
- i: toPos + 1, i <= fromPos, 1
- i: fromPos , i >=toPos + 1, -1
この２は両方とも同じ範囲をiが変化します（toPos + 1 <= i <= fromPos）。ただし結果は大きく異なります。
前者は１回目のループでMemo[toPos + 2]にMemo[toPos + 1]が格納されます。
続いて２回目のループでMemo[toPos + 3]にMemo[toPos + 1]が格納されます。
１回目のループでMemo[toPos + 2]はMemo[toPos + 1]で上書きされているので、２回目のループではMemo[toPos + 3]にMemo[toPos + 1]の値が格納されることになります。
つまり、ループするたびにMemo[toPos + 1]の値がコピーされることになるので、Memo[toPos + 1]からMemo[fromPos]が全てMemo[toPos + 1]の値になってしまいます。
なので[ d ]は 「toPos + 1, i <= fromPos, 1」ではありません。
一方、後者であれば、１回目のループでMemo[fromPos – 1]の値がMemo[fromPos]に格納され、
２回目のループでMemo[fromPos – 2]の値がMemo[fromPos – 1]が格納されることになります。
しかしこの場合は１回目のループ時でMemo[fromPos – 1]の値はMemo[fromPos]で上書きされるようなことはありませんので、Memo[ ]の値が１つずつ後ろにずれさせることができ、所望の動作を実行することができます。
したがって、[ d ]の答えは 「fromPos , i >=toPos + 1, -1」です。
設問２
設問２clearGarbage関数実行後の各変数の値を答える問題になります。
図６に対してプログラムを実行した後の状態がわかれば問題は解くことができます。なので、他の関数の説明で図が記載されていたように、この関数においてもプログラムを実行するたびにMemo[ ]やData[ ]、他の変数がどのように変わっていくかを追っていけば正解を導くことができるはずです。
下図が図６の状態のMemo[ ]、Data[ ]に対するclearGarbage関数実行後の結果になります。要はclearGarbage関数とはMemo[ ]から参照されない部分をData[ ]から削除する関数になります。
この図からもわかるように、Memo[1]の値である[ e ]は4、Memo[2]の値である[ f ]は9、DataLenの値である[ g ]は13となります。
解いてみた感想
プログラム的にも問題文的にも非常に分かりやすい問題だと思いました。特に各関数が図で説明されているので、文章だけで説明されているような問題に比べて非常に分かりやすかったです。設問１でも説明しましたが、アルゴリズム問題やプログラミングの問題では初期値やループの範囲として+1すべきか否か、-1すべきか否かで結構迷うことが多いです。迷った場合は実際にプログラムに当てはめてどちらが正しいかを判断するのが楽だと思います。
★オススメページ★
下記ページから他の回の解説もたどれます。他の回のアルゴリズム問題の解き方がわからない場合は是非読んでみてください！
基本情報技術者試験 午後問題「アルゴリズム」過去問の解き方 解説 まとめ本ページの図・プログラム・問題文について
図やプログラム、問題文はIPA公開の過去問題から引用しています。また図やプログラムに関しては説明に必要な部分に関してのみ加工して使用させていただいております。
出典：平成２８年度 春期 基本情報技術者試験（FE）試験区分 午後 問８
