平成３０年度春期午後のアルゴリズム問題である問８の私の解き方・考え方について解説していきます。
問題
IPAの公式サイトで公開されています。このページでは問８についての解説を行います。
https://www.jitec.ipa.go.jp/1_04hanni_sukiru/mondai_kaitou_2018h30_1/2018h30h_fe_pm_qs.pdf
設問１
まずは問題を読んで重要なポイントを整理していきましょう。
- データを昇順に整列することが目的のアルゴリズム
- 整列はヒープの性質を利用して行う
- 親は１つもしくは２つの子を持ち、親は子よりも値が大きい
- 親を持たない節は根であり、根は最大の値を持つ
- 各節の値は配列heapに格納される
- heap[0]が根
- heap[i]の子はheap[2 * i + 1]とheap[2 * i + 2]
- lchild(), rchild(), parent()により、引数で指定した要素番号に対する子や親の要素番号が取得可能
- swap()は第二引数と第三引数で指定した要素番号の節の値を入れ替える
この辺りが頭に入ってくると解ける問題だと思います。
[プログラム１]
設問１はプログラム中の[ a ]と[ b ]に入る答えを選べ、というものです。
[ a ]の選択肢ア. heap[k] > heap[lchild(k)]
イ. heap[k] > heap[parent(k)]
ウ. heap[k] > heap[rchild(k)]
エ. heap[k] < heap[lchild(k)]
オ. heap[k] < heap[parent(k)]
カ. heap[k] < heap[rchild(k)]
[ b ]の選択肢
ア. heap[hnum – 1]
イ. heap[k]
ウ. parent(hunum – 1)
エ. parent(k)
スポンサーリンク
設問１の考え方
正直ここだけだと[ a ]に関しては私には答えはパッと浮かびませんでした。ただヒープの性質を満たすことが目的で、[ a ]が成立した時に[ b ]を行うアルゴリズムになっていることは分かるので、おそらく親子の大小関係が逆の場合にswap関数で値を入れ替えるのだろうなぁという推測はできました。
なので大小関係が異なっていることが条件式になるのでイ、エ、カの３択に絞れると考えました。ただどれかはハッキリわからない・・・。
そこで[ b ]の方を先に考えることにしました。[ b ]に関してはすぐ答えは導けますね。heap()の第三引数として指定する値は要素番号です。なので、要素番号ではなく要素の値を指定しようとしているアとイはまず選択肢から消去できます。
またヒープの性質を満たすことが目的なので、kの子供か親の値を入れ替えなければその目的を達成するアルゴリズムにならないと考えたのでエを選択しました。
swap後にkにparent(k)の値を代入していることからも、ヒープの下の方の要素から親子の大小関係を整えていることがわかりますね。
[ b ]側がわかったので[ a ]側の答えもわかりました。kとparent(k)の値を交換する必要があるのは、kとparent(k)の親子の大小関係が崩れている時なので、答えはイと考えることができます。
設問２
新しいプログラム2が登場しますね。まず説明読んでポイント整理しましょう。
- heap配列は整列対象領域と整列済みデータ領域の2つに分かれる
- ヒープの性質を満たしておけばheap[0]は整列対象領域で必ず最大値
- そのheap[0]を整列対象領域の最後の要素と交換し、整列対象領域の最後の要素を整列済みデータ領域に含める
- 交換により整列対象領域がヒープ性質を満たさなくなるので、再度整列対象領域をヒープ性質を満たすように再構築する
- これらを繰り返すことで昇順にソートする
こっちはプログラム１より理解しやすかったです。
実際のプログラム2は下記です。
[プログラム2]
設問２の考え方
では設問２を解いていきましょう。こちらはプログラムの動きを実例を使って実際に追っていけば簡単に解けました。
まずα時点での配列の様子が↓になっているとのことです。
次のswap()により要素番号last（整列対象領域の最後の要素）と要素番号0の値が交換されます。これにより配列は下のように変化します。
なので[ c ]で問われているheap[0]の値は20になります。
問題を読み進めていきましょう。次はdownHeap()の動きについての問題になっています。
(1)はプログラムの3行目の説明ですね。
(2)はプログラム数行をまとめて説明しています。
まず「要素番号 n の配列要素に対応する節の左側の子の要素番号を tmp に代入する」は5行目の処理、「要素番号 n の子が二つあり」は6行目の条件式、問題となる「右側の子の値が左側の子の値[ d ]」は一旦飛ばして、「右側の子の要素番号を tmp に代入する」は8行目の処理の説明であることはプログラムと照らし合わせて考えれば理解できると思います。
では「右側の子の値が左側の子の値[ d ]」は何行目の説明かというと、6行目と8行目の間の7行目であることもすぐ分かると思います。なので7行目のプログラムを日本語で考えてやれば問題は解けます。
であり、tmpにはnの左の子の値が代入されているので、結局「nの右の子の値がnの左の子の値以上の時」という条件式であると考えられます。
ですので[ d ]の解答は「以上のときは」です。
[ e ]に関しては最初に15行目が実行されるときのtmpの値を問いています。問題の実例を用いて実際にプログラムを頭の中で実行してやれば答えは出てきます。
3行目よりnは0から始まります。
実行時のheap配列は↓となっています。
nの左の子の要素番号は1（n * 2 + 1）、右の子の要素番号は2（n * 2 + 2）となります。
また整列済みデータ領域は1つ、整列対象領域は6つです。なのでhlastも6になり、4行目の比較はYESになります。
そのため5行目でtmpにnの左の子の要素番号である1が代入されます。
6行目の条件式もnの右の子の要素番号が2でhlastが6なのでYESとなります。
さらにnの左の子の値が30、右の子の値が45なので7行目の条件式もYESです。
そのため8行目が実行され、tmpに右の子の要素番号である2が代入されます。
次は11行目の条件式の判断が行われます。要素番号nと要素番号tmpの値の比較です。ここまでの処理で、nには0が、tmpには2(節0の右の子）がそれぞれ代入されていますので、20と45の比較となりtmp側（子供側）の方が大きいためこの条件式もYESです。
そのため12行目が実行され、要素番号2と要素番号0の値が交換されます。
また11行目の条件式がYESのため、13行目は実行されません。つまりdownHeapから抜けません。なので15行目が実行されることになります。
この時のtmpは…、8行目で代入された2ですね。[ e ]は2になります。
こんな感じに実際にプログラムを追っていくと答えが導け出せます。
スポンサーリンク
解いてみた感想
難しかったです…。特に設問１に関してはゴリ押しで解いた感じがします。ただゴリ押しででも答えが導け出せるのがアルゴリズム問題のいいところですね。
ヒープって単語見て敬遠する人もいるかもしれませんが、しっかりヒープの意味も問題文の中で説明してくれているのでじっくり問題読んで論理的に解けば正解できる問題だとおもいます。
設問２に関してはプログラム追っていけば誰でも正解できる問題ですね。
解いてみてポイントだと思ったのは、下記の３点です。
- 順番にとらわれずに分かるところから解く。特に穴埋め問題だとその解いて埋めた部分が分からない問いへのヒントになることがある
- プログラムの全体像がイメージできないなら実例を用いてプログラムを追ってみる。これによりプログラムの動きが分かって全体像も見えてくるはず
- プログラミングやっている人でも擬似言語の記号の説明ははしっかり読んでおいたほうが良い（問題のP.3)
初めてアルゴリズム問題の解説をしてみたのですが、最初に解いた問題が難しくてビックリです。この問題はアルゴリズム問題の中でも難易度高い方なのではと思いました。
★オススメページ★
下記ページから他の回の解説もたどれます。他の回のアルゴリズム問題の解き方がわからない場合は是非読んでみてください！
基本情報技術者試験 午後問題「アルゴリズム」過去問の解き方 解説 まとめ
本ページの図・プログラム・問題文について
図やプログラム、問題文はIPA公開の過去問題から引用しています。また図やプログラムに関しては説明に必要な部分に関してのみ加工して使用させていただいております。
出典：平成３０年度 春期 基本情報技術者試験（FE）試験区分 午後 問８
アルゴリズム問題の対策（PR）
過去問を解いてみて感触はいかがだったでしょうか？
全く分からなかった...という方もいらっしゃるかもしれません。はっきりいってアルゴリズム問題は、特に慣れないと難易度は高いです。
なので、こういった方にはもっと "簡単なアルゴリズム問題を解いて慣れていく" ことをオススメします。で、この簡単なアルゴリズム問題を解くのにオススメの本が下記の うかる！ 基本情報技術者 [午後・アルゴリズム編] です。
オススメする理由は、特に本の前半部分で難易度の低いアルゴリズムの紹介や解説が行われているところです。こういったアルゴリズムの動作などを実際にトレースして追ってみたりすることで簡単な問題からアルゴリズム問題に慣れていくことができます。
また、「アルゴリズムとは？」といったアルゴリズム入門から解説してくれているので、プログラミングをやったことない方にも親切な内容になっています。
アルゴリズム問題に全く手がつかないというような方は、まずは上記のような本でアルゴリズムに慣れるのがオススメです。
慣れてきたら、あとは実際の過去問を解いて "さらに考える力を養う" ＆ "実際のアルゴリズム問題に慣れる" のが良いと思います。
私のサイトでも過去問の解説をしていますので是非参考にしてください。私の解説だけでなく、他の人の解説も参考にしたいような場合には、下記のような過去問の参考書もオススメです（アルゴリズム問題だけでなく、全問題の解説も充実しています）。
