77Lifeworkベータ版

77Lifeworkベータ版

IT関係の話をメインとして、その他私の趣味や雑記用のブログです。ここに書いた内容が少しでも参考になれば嬉しいです。

基本情報技術者試験:アルゴリズム解説 平成30年度 春期

平成30年度春期 基本情報技術者試験(FE)の午後問題 問8アルゴリズムについて、問題文を見ながら解説していきたいと思います。

 

 

今回のプログラムですが、問題文の1行目にある通り、「データを昇順に整列する」ことを目的とし、これにあたってヒープの性質を利用すると書いてありますね。ヒープの具体例として下図が問題文に示されています。

f:id:J-back:20190729232036p:plain

 そもそもヒープとは

「子要素は親要素より常に大きいか等しい(または常に小さいか等しい)という制約を持つ木構造の事。」です。今回は後者の場合ですね。

出典: フリー百科事典 ウィキペディアWikipedia))

ja.wikipedia.org

 

ヒープを使ってどうやって昇順ソートするの?って疑問は後ほど問題文中で解消できますので、お待ちを。

 

さて、問題文に[プログラム1の説明]とあるので、上から見ていきます。

================================================================

f:id:J-back:20190730000303p:plain

f:id:J-back:20190730003952p:plain

f:id:J-back:20190730004108p:plain

f:id:J-back:20190730004238p:plain

f:id:J-back:20190730004343p:plain
================================================================

(1)について、まあこれは通常の配列ってことですね。

(2)はヒープ構造と配列の対応が説明されています。今回の問題では、ヒープ構造を配列heapで表現します。

ある1次元配列dataを入力として関数makeHeapを実行すると、配列dataに格納されている値をヒープ構造にして格納した配列heapを返します。

配列と問題文のヒープ構造の図を対応させてみると、下のようになります。

f:id:J-back:20190730004953j:plain

 

つまり、上図を配列で表現すると heap = [60, 30, 45, 15, 5, 10, 20] です。

例えば、1次元配列dataが data = [5, 45, 10, 20, 60, 30, 15] だった場合、この配列の要素は7個あるので、hnum = 7であり、配列dataに関数makeHeapを適用すると、問題文のルールでヒープ構造を表現する配列として heap = [60, 30, 45, 15, 5, 10, 20] が返却されるのです。関数makeHeapの処理の中身については設問になっているため後ほど見ていきます。

 

(3)について、これはヒープ構造の例を配列で表現したものです。

(4)について、ここでは3つの関数が登場しています。

①のlchild(i)は、ある節(要素番号がi)の左側の子に対応する配列の要素番号を出力します。例えばheap[1]に注目した場合には、i = 1 なので、lchild(1)が2×1+1 = 3 となり、

heap[1]の左側の子に対応するのは heap[3] であることを示しています。

②のrchild[i]はある節(要素番号がi)の右側の子に対応する配列の要素番号を出力します。①と同じ考え方で、heap[1]に注目するとrchild(1)は2×1+2 = 4となり、heap[1]の右側の子はheap[4]であることを示します。
③のparent(i)については、①と②の逆の操作をする関数です。例えばheap[3]に注目すれば i = 3 なので、parent(i) = (3 - 1) / 2 = 1となり、heap[3]の親がheap[1]であることを示しています。また、heap[4]に注目した場合にも、i = 4 なので、parent(4) = (4 - 1) / 2 = 1

(少数点以下は切り捨てです)となり、heap[4]の親がheap[1]であることを示しています。

(5)について、swap関数は1次元配列とその配列の要素番号を2つ受け取り、受け取った要素番号の配列要素を交換した配列を返します。

例えばtest = [10, 20]という配列があった場合、test[0] = 10, test[1] = 20なので、

swap(test, 0, 1)はtestという配列の要素番号0と要素番号1の値を交換した配列

[20, 10]を返すことになります。

(6)について、関数makeHeapと関数swapの引数がそれぞれ示されています。

 

設問1の解説

さて、ここからは設問について考えていきましょう。

まずは設問1ですが、[プログラム1]として副プログラムmakeHeapの処理が記載されており、この穴埋めですね。

f:id:J-back:20190802011350j:plain

上記の赤色文字は行数を記載しました。ここでは例として、入力値を

data = [5, 45, 10, 20, 60, 30, 15], hnum = 7 としてmakeHeapの動きを見てみましょう。

1行目では i が 0 から hnumの値(今回の例では7) まで、1ずつ増加するループが始まっています。最初は i = 0 ですね。

2行目でheap[0] に data[0]、つまり 5 が入ります。

3行目で k に i の値、つまり0が入ります。

4行目では k > 0 の場合に実行されるループが始まっています。今はk が 0 なので、実行されず、1行目に戻ります。

この段階で、heap = [5] です。

次にi = 1となり、2行目の処理へ。

2行目ではheap[1] に data[1] つまり45 が入り、3行目で k に 1 が入ります。

この時点で heap = [5, 45] ですね。

k = 1となったので、4行目以降の処理が実行されます。

5行目で設問になっている(a)という条件がTrueである場合にのみ、6行目・7行目が実行されます。

6行目は配列heapの要素の中で、要素番号がkであるものと要素番号が(b)であるものを入れ替えるという処理です。

7行目は要素番号kの配列要素の親にあたる要素番号(k - 1)/2 を新たにkとしています。

問題文にある通り、配列heap はヒープ構造を満たしている、つまり、makeHeapの処理が実行された後にはheap[0]の左側の子がheap[1]、右側の子がheap[2]という状態になっているはずです。したがって、5行目以降の処理を通ることによってheap = [45, 5]となることが予想できます。

ここで(a)と(b)の選択肢を見てみます。

まずは(b)について、これは関数swapの引数の中で、配列の要素数を指定する部分なので、配列要素そのものを表している選択肢アとイは不適切です。

また、hnumは配列data の要素数を示しているので今回の例ではhnum = 7であり、選択肢ウはparent(6)となります。この時点で配列heapに要素番号6は存在しないので、不適切です。したがって設問1の(b)は選択肢エ が正解となります。

 

ここまでで、

(a)という条件がTrueの場合 ・・・(5行目)

配列heapの 要素番号kの要素と要素番号parent(k)の要素を入れ替え・・・(6行目)

kにparent(k)の値を入れる・・・(7行目)

というところまで分かりました。次は(a)について考えます。

問題文より、ヒープ構造を満たしている場合、親は子よりも大きいか等しい値を持つ、と記載があるので、6行目の入れ替え処理を実行する必要があるのはheap[k]よりもheap[parent(k)]が大きい値を持っている場合です。したがって設問1の(a)は選択肢イが適切です。

 

設問2の解説

次に設問2に移ります。

問題文中の[プログラム2の説明]ってとこを読んで、どんな処理なのか掴みましょう。

ここでは当初の目的であった、ヒープの性質を用いて「データを昇順に整列する」方法を説明しています。

まずは昇順ソートをしたい元の配列dataに対し、副プログラムmakeHeapを実行します。これによって出力される配列heapはヒープの性質を満たす順序でデータが格納されている配列です。ヒープの性質を満たすということは「根」に対応するheap[0]が配列heapの要素の中で最も大きな値となっています。

このheap[0]を配列heapの最後の要素であるheap[last]に格納し、次はheap[last]を除いたheap[0]からheap[last-1]の間の要素に対してmakeHeapを実行。新たにheap[0]となった要素をheap[last-1]に格納。そしてheap[0]からheap[last-2]の要素に対してmakeHeapを実行・・・を繰り返していくと、配列heapは最後の要素が最大値となって、最後から2番目の要素が2番目に大きい値・・・となり、昇順ソートが実現されるというわけです。

しかし、単純にmakeHeapを実行してheap[0]とheap[last]を入れ替える、を繰り返しやっても期待した通りの結果にはなりません。makeHeapを適用する範囲が配列heapの全要素となっていると、せっかく昇順に整列させた部分さえも壊してヒープの性質を満たすように整列させ直してしまいます。これではいつまでたっても目的の昇順ソートを実現できません。これを防ぐために、副プログラムdownHeapでは、heap[0]とheap[last]の値を交換した後にlastの値を1減らすという処理が実行されています。これによって、ヒープの性質を満たすように整列を行う対象から、すでに昇順ソート済みの部分を除くようになっています。

 

設問の(c)、(d)、(e)は具体的な値を入れて副プログラムheapSortの動作を見る問題となっているため、実際に値を入れて追っていくのが良いと思います。

問題文の[プログラム2の動作]に記載がある通り、副プログラムheapSortの3行目の実行が終了した時点での配列heapは以下の図の状態です。

f:id:J-back:20190730003952p:plain

heap = [60, 30, 45, 15, 5, 10, 20] 、要素数は7なので、hnum = 7 ですね。heapSortの3行目の処理というのは副プログラムmakeHeapなので、この配列heapはヒープの性質を満たす状態となっています。

次にheapSortの4-7行目の繰り返し処理が実行されます。

lastの値が  hnum - 1 = 6 からはじまって、ループを回る度に-1されます。

lastが0より大きい間ループ処理が続行されます。

まずはlast = 6 の状態で、5行目のswap(heap, 0, 6)が実行されます。

これは配列heapのheap[0]とheap[6]の値を入れ替える処理です。

したがって、heap = [20, 30, 45, 15, 5, 10, 60]となります。配列heapの要素の中で最大のものが最も後ろの要素に移動されました。 

ここでheap[0]が20となったので、設問の(c)は選択肢エとなります。

この段階で配列heapの最後の要素であるheap[6]が最大の値となったので、heap[6]は固定した状態で、次に大きな値がheap[5]となるように整列させればよいことになります。

しかし、上記のswap(heap, 0, 6)の処理によるheap[0]とheap[6]の入れ替えによってheap[0]からheap[5]の要素はヒープの性質を満たす整列順となっていないので、これを再びヒープの性質を満たすように並べ替える必要があります。

というわけで6行目のdownHeap(heap, 5)の出番です。問題文にも記載がありますが、このdownHeap(heap, hlast)は、配列heapの要素番号0からhlastまでの要素をヒープの性質を満たすように並べ替えてくれます。

ここからは副プログラムdownHeapに処理が移ります。

まずはdownHeapの3行目で、nに0が代入されます。

4-16行目のループ処理はlchild(n)がhlastより小さいか等しい場合に実行されます。

今の場合はn = 0でありlchild(0) = 1、hlast = 5なので、条件が成立し、ループ処理に入ります。

5行目では要素番号nの左側の子の要素番号をtmpに代入します。

ここではn=0なので、tmpにlchild(0)、つまり1が代入されます。

6行目の条件、要素番号nの右側の子であるrchild(n)がhlastより小さいか等しい場合に7-9行目が実行されます。今回は

n = 0なのでrchild(0) = 2

hlast = 5

であるため、7-9行目が実行されます。

7行目の条件、ここが設問の(d)になっています。

これは、heap[tmp]よりheap[rchild(n)]が小さいか等しい場合に8行目が実行されるという条件です。ここで、5行目を見ると、tmpにはlchild(n)が格納されていることが分かるので、heap[tmp] は heap[lchild(n)] を表しています。

この上で7行目を見ると、これは

heap[lchild(n)] ≦ heap[rchild(n)]

つまり

右側の子の値であるheap[rchild(n)]が左側の子の値であるheap[lchild(n)]以上である

という条件を表していることが理解できます。

したがって、設問の(d)は選択肢イが適切ですね。

今の場合はtmp = 1、n = 0なのでrchild(n) = 2なので、

heap[tmp] は heap[1]

heap[rchild(n)] は heap[2]

となります。heap[1]とheap[2]を比較して、heap[1]の方がheap[2]より小さいか等しい場合に8行目が実行されることがわかります。

ここで

heap[1] = 30

heap[2] = 45

であり、7行目の条件が満たされるので、8行目が実行され、tmpにrchild[n] = 2 が代入され、

tmp = 2

です。

11行目の条件であるheap[tmp]>heap[n]がTrueの場合に12行目が実行され、Falseの場合に13行目が実行されます。

今はtmp = 2であり、n = 0ですので、heap[tmp] = 45、heap[0] = 20となり、11行目の条件が成立し、12行目のswap(heap, 0, 2)が実行されます。

これによってheap[0]とheap[2]の値が入れ替えられ、配列heapは

heap = [45, 30, 20, 15, 5, 10, 60]

となります。

15行目で n に tmp の値が入ります。

この段階では tmp = 2 なので、n = 2 となります。

したがって設問の(e)は 選択肢イとなります。

 

最後に 

以上で解説終わりです。

「それぞれのプログラムが何をしようとしているのか」をつかむのが難しいとは思いますが、1行ずつ追っていけばだんだんとわかるようになると思います。

 

長くなってしまいましたが、最後まで読んでくださり、ありがとうございました。 

 

出典:平成30年度 春期 基本情報技術者試験 午後 問8