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

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

問題

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

https://www.jitec.ipa.go.jp/1_04hanni_sukiru/mondai_kaitou_2016h28_1/2016h28h_fe_pm_qs.pdf

問題の概要

配列の要素の削除や追加等の管理の問題です。

スポンサーリンク

設問1

[プログラムの説明]の特に各関数の説明は図付きの説明で、どういったことを行う関数かのイメージはかなり湧きやすいと思います。

どういった関数があるかをしっかり把握しておいて、設問1を問いて行きましょう。

[   a   ]と[   b   ]はaddMemo関数に関するものです。下の図は図3の状態から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増やしているからです。ですので、プログラムの⑤ではDataLenDataLentextLen分増やしてやった値を格納する必要があります。したがって[   b   ]の答えはDataLen + textLenとなります。


 

続いて[   c   ]を解いていきます。[   c   ]の穴埋めはdeleteMemo関数に関するものです。下の図は図3の状態からdeleteMemo(1)を実行した時の例です。

この図やdeleteMemo関数の仕様から分かるように、deleteMemo(1)を実行すると下記のような処理が行われます。

①pos+1以降のMemo[ ]を1つ後ろに移動

②MemoCnt(4)を1減らす(3になる)

上記の処理とプログラムの対応を見ると下記のようになっています。

プログラムの①ではMemo[i – 1]Memo[i]の値を代入し、それをiMemoCntになるまで繰り返しています。

Memo[i – 1] Memo[i]にコピーしていっているので、iの初期値である[   c   ]はpos+1になります。

iの初期値をposにしてしまうと、関係ないMemo[i – 1]の値が変わってしまいますし、posが0のときにMemo[-1]になってしまいおかしな領域にアクセスしてしまい関数が成立しません。

アルゴリズム問題では結構この「+1」するか、「-1」するか、のあたりで迷うことも多いですが、それぞれのケースで実際にプログラムを追ってみて成立するものを探し出す方法が良いと思います。

次は[   d   ]を解いていきます。[   d   ]の穴埋めはmoveMemo関数に関するものです。moveMemo関数は引数のfromPostoPosの大小関係で処理が異なります。[   d   ]があるのはfromPostoPosよりも大きい場合のプログラムです。ですので今回はそちらのケースに絞って見ていきましょう。

下の図は図3の状態からmoveMemo(3, 1)を実行した時の例です。

この図や問題文のmoveMemo関数の仕様から分かるように、moveMemo を実行すると下記のような処理が行われます。

①一旦Memo[fromPos]の値を他の変数に退避

②toPosからfromPos-1のMemo[ ]を1つずつ後ろに移動

③①で退避した値をMemo[toPos]へ格納

上記の処理とプログラムの対応を見ると下記のようになっています。

「②toPosからfromPos-1Memo[ ]を1つずつ後ろに移動」を行うための i に対するループの設定が[   d   ]の答えになります。

この「②toPosからfromPos-1Memo[ ]を1つずつ後ろに移動」を実現するためには、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[ ] の中身が1つずつ後ろに移動しているようにも思えますが、実はダメです。

例えば2行目に注目すると、Memo[toPos + 1] が Memo[toPos + 2] に格納されることになりますが、この Memo[toPos + 1] には、1行目で Memo[toPos] の値が格納されてしまっています。つまり、Memo[toPos + 2] には Memo[toPos] が格納されることになります。

3行目も同様で、Memo[toPos + 2] には Memo[toPos] が格納されているため、Memo[toPos + 3] には Memo[toPos] の値が格納されることになります。

それ以降も同様で、要は Memo[toPos] の値が Memo[toPos + 1] 〜 Memo[fromPos] に格納されることになり、toPosからfromPos-1Memo[ ]を1つずつ後ろに移動することになりませんし、このようなことになれば、問題文の図5の状態から moveMemo(2, 0) を実行した場合に問題文の図6の状態にはなり得ません。

ですので、「②toPosからfromPos-1Memo[ ]を1つずつ後ろに移動」を実現するためには、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 ] の答えは イ となります。

今回は上記のように解説しましたが、この問題の場合はプログラムの穴埋め部分が1つだけですので、その穴埋め部分に全ての選択肢を当てはめた時に、実際に moveMemo を実行した時に仕様通りに動作するかを確認することでも答えは導き出せるのではないかと思います。

そもそも moveMemo(2, 0) を実行した場合、選択肢 イ 以外の場合は、Memo[0] ← Memo[-1] が実行されることになります。Memo[-1] の値は無いので、この問題の場合は、この時点でおかしいと判断して答えの選択肢から外してしまっても問題ないかもしれません。

設問2

設問2clearGarbage関数実行後の各変数の値を答える問題になります。

図6に対してプログラムを実行した後の状態がわかれば問題は解くことができます。なので、他の関数の説明で図が記載されていたように、この関数においてもプログラムを実行するたびにMemo[ ]Data[ ]、他の変数がどのように変わっていくかを追っていけば正解を導くことができるはずです。

下図が図6の状態のMemo[ ]Data[ ]に対するclearGarbage関数実行後の結果になります。要はclearGarbage関数とはMemo[ ]から参照されない部分をData[ ]から削除する関数になります。

この図からもわかるように、Memo[1]の値である[   e   ]は4Memo[2]の値である[   f   ]は9DataLenの値である[   g   ]は13となります。

解いてみた感想

プログラム的にも問題文的にも非常に分かりやすい問題だと思いました。特に各関数が図で説明されているので、文章だけで説明されているような問題に比べて非常に分かりやすかったです。設問1でも説明しましたが、アルゴリズム問題やプログラミングの問題では初期値やループの範囲として+1すべきか否か、-1すべきか否かで結構迷うことが多いです。迷った場合は実際にプログラムに当てはめてどちらが正しいかを判断するのが楽だと思います。

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

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

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

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

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

3 COMMENTS

gg

度々すみません
設問1 [c] は文章から、pos+1 と書いてあるからという理由はだめですか?

設問1 [d] が全く分かりません
to pos と from pos は恐らく実行前と実行後で区別しているのだと思います
ほかに何か根拠となる部分はありますでしょうか?

②toPosからfromPos-1のMemo[ ]を1つ後ろに移動
という部分で、図を見る限り1つ前だと思うのですがどうして後ろなのでしょう?

返信する
daeu

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[ ]を1つ後ろに移動
>という部分で、図を見る限り1つ前だと思うのですがどうして後ろなのでしょう?
これは、moveMemo の説明箇所で私が書いた図において、
moveMemo(3, 1) を実行すると、
Memo[1] の値の 5 が1つ後ろの Memo[2] に移動し、
Memo[2] の値の 10 が1つ後ろの Memo[3] に移動することになるので、
“1つ後ろ” に移動と記述しています。

返信する

コメントを残す

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