平成２８年度春期午後のアルゴリズム問題である問８の私の解き方・考え方について解説していきます。
問題
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 を実行すると下記のような処理が行われます。
①一旦Memo[fromPos]の値を他の変数に退避
②toPosからfromPos-1のMemo[ ]を１つずつ後ろに移動
③①で退避した値をMemo[toPos]へ格納
上記の処理とプログラムの対応を見ると下記のようになっています。
「②toPosからfromPos-1のMemo[ ]を１つずつ後ろに移動」を行うための i に対するループの設定が[ d ]の答えになります。
この「②toPosからfromPos-1のMemo[ ]を１つずつ後ろに移動」を実現するためには、fromPos > toPos の場合、下記のような順番で Memo[i] ← Memo[i – 1] を行なっていく必要があります。
- Memo[fromPos] ← Memo[fromPos – 1]
- Memo[fromPos – 1] ← Memo[fromPos – 2]
- Memo[fromPos – 2] ← Memo[fromPos – 3]
- （同様の処理）
- Memo[toPos + 2] ← Memo[toPos + 1]
- Memo[toPos + 1] ← Memo[toPos]
上記の同様の処理を逆順に行った場合について考えてみましょう。
- Memo[toPos + 1] ← Memo[toPos]
- Memo[toPos + 2] ← Memo[toPos + 1]
- Memo[toPos + 3] ← Memo[toPos + 2]
- （同様の処理）
- Memo[fromPos – 2] ← Memo[fromPos – 3]
- Memo[fromPos – 1] ← Memo[fromPos – 2]
- Memo[fromPos] ← Memo[fromPos – 1]
これでも Memo[ ] の中身が１つずつ後ろに移動しているようにも思えますが、実はダメです。
例えば２行目に注目すると、Memo[toPos + 1] が Memo[toPos + 2] に格納されることになりますが、この Memo[toPos + 1] には、１行目で Memo[toPos] の値が格納されてしまっています。つまり、Memo[toPos + 2] には Memo[toPos] が格納されることになります。
３行目も同様で、Memo[toPos + 2] には Memo[toPos] が格納されているため、Memo[toPos + 3] には Memo[toPos] の値が格納されることになります。
それ以降も同様で、要は Memo[toPos] の値が Memo[toPos + 1] 〜 Memo[fromPos] に格納されることになり、toPosからfromPos-1のMemo[ ]を１つずつ後ろに移動することになりませんし、このようなことになれば、問題文の図５の状態から moveMemo(2, 0) を実行した場合に問題文の図６の状態にはなり得ません。
ですので、「②toPosからfromPos-1のMemo[ ]を１つずつ後ろに移動」を実現するためには、fromPos > toPos の場合、下記の順番で Memo[i] ← Memo[i – 1] を行なっていく必要があります。
- Memo[fromPos] ← Memo[fromPos – 1]
- Memo[fromPos – 1] ← Memo[fromPos – 2]
- Memo[fromPos – 2] ← Memo[fromPos – 3]
- （同様の処理）
- Memo[toPos + 2] ← Memo[toPos + 1]
- Memo[toPos + 1] ← Memo[toPos]
つまり、最初は i が fromPos の状態から処理が始まり、i を 1 ずつ減らしながら、i が toPos + 1 になるまで処理を行う必要があることになります（ループの中で行われる処理は Memo[i] ← Memo[i – 1] であり、左辺の添字が i となります）。
従って、このループを実現するための条件式を擬似言語で記述すれば、「i = fromPos, i ≦ toPos + 1, -1」となり、[ d ] の答えは イ となります。
今回は上記のように解説しましたが、この問題の場合はプログラムの穴埋め部分が１つだけですので、その穴埋め部分に全ての選択肢を当てはめた時に、実際に moveMemo を実行した時に仕様通りに動作するかを確認することでも答えは導き出せるのではないかと思います。
そもそも moveMemo(2, 0) を実行した場合、選択肢 イ 以外の場合は、Memo[0] ← Memo[-1] が実行されることになります。Memo[-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）試験区分 午後 問８
アルゴリズム問題の対策（PR）
過去問を解いてみて感触はいかがだったでしょうか？
全く分からなかった...という方もいらっしゃるかもしれません。はっきりいってアルゴリズム問題は、特に慣れないと難易度は高いです。
なので、こういった方にはもっと "簡単なアルゴリズム問題を解いて慣れていく" ことをオススメします。で、この簡単なアルゴリズム問題を解くのにオススメの本が下記の うかる！ 基本情報技術者 [午後・アルゴリズム編] です。
オススメする理由は、特に本の前半部分で難易度の低いアルゴリズムの紹介や解説が行われているところです。こういったアルゴリズムの動作などを実際にトレースして追ってみたりすることで簡単な問題からアルゴリズム問題に慣れていくことができます。
また、「アルゴリズムとは？」といったアルゴリズム入門から解説してくれているので、プログラミングをやったことない方にも親切な内容になっています。
アルゴリズム問題に全く手がつかないというような方は、まずは上記のような本でアルゴリズムに慣れるのがオススメです。
慣れてきたら、あとは実際の過去問を解いて "さらに考える力を養う" ＆ "実際のアルゴリズム問題に慣れる" のが良いと思います。
私のサイトでも過去問の解説をしていますので是非参考にしてください。私の解説だけでなく、他の人の解説も参考にしたいような場合には、下記のような過去問の参考書もオススメです（アルゴリズム問題だけでなく、全問題の解説も充実しています）。
度々すみません
設問1 [c] は文章から、pos+1 と書いてあるからという理由はだめですか？
設問1 [d] が全く分かりません
to pos と from pos は恐らく実行前と実行後で区別しているのだと思います
ほかに何か根拠となる部分はありますでしょうか？
②toPosからfromPos-1のMemo[ ]を１つ後ろに移動
という部分で、図を見る限り１つ前だと思うのですがどうして後ろなのでしょう？
gg さん
コメントありがとうございます！
＞設問1 [c] は文章から、pos+1 と書いてあるからという理由はだめですか？
今回の場合は問題が素直なので良いですが、
例えば deleteMemo 関数が、
・”i < MemoCnt” の部分を “i + 1 < MemoCnt”
・”Memo[i – 1] ← Memo[i]” の部分を “Memo[i] ← Memo[i + 1]”
みたいな感じで置き換えられて処理が記述されていた場合、設問 1 – [c] の答えは pos になってしまいます。
こんな感じで、ちょっと意地悪にプログラムが書かれていると問題文中に記載されているものと設問の答えが異なる場合があるので注意が必要だと思います。
問題文に書いてある仕様を満たすためのプログラムの書き方はいくつもあるはずなので、
問題に書いてあるからという理由ではなく、問題に書かれている仕様を満たすために穴埋め部分に何を入れるべきかを考えた方が、正解率は上がるのではないかと思います（時間はかかりますが…）。
＞設問1 [d] が全く分かりません
＞to pos と from pos は恐らく実行前と実行後で区別しているのだと思います
＞ほかに何か根拠となる部分はありますでしょうか？
イが答えになる根拠は、イ以外の選択肢を穴埋め部分に当てはめた場合、プログラムが moveMemo の仕様通りに動作しないことがあるからです。
これはおそらく全選択肢をプログラムの穴埋め部分に入れ、さらに fromPos と toPos に実際に数字を当てはめて処理を確認してみれば確認できると思います。
・アの場合は toPos が 0 の場合にうまく動作しない（Memo[-1]なんて存在しない）
・ウとエの場合は、データの移動だけでなく、変に Memo のデータのコピーが行われてしまう
ので、解はイになると思います。
＞②toPosからfromPos-1のMemo[ ]を１つ後ろに移動
＞という部分で、図を見る限り１つ前だと思うのですがどうして後ろなのでしょう？
これは、moveMemo の説明箇所で私が書いた図において、
moveMemo(3, 1) を実行すると、
Memo[1] の値の 5 が１つ後ろの Memo[2] に移動し、
Memo[2] の値の 10 が１つ後ろの Memo[3] に移動することになるので、
“１つ後ろ” に移動と記述しています。
設問1 [d] 解説の記述を少し変更してみました。