基本情報技術者過去問題 平成30年春期 午後問8 設問1　解説

本問を最初に解いたとき、筆者はある重大なミスをしてしまうのですが、そこからどうリカバリーすればよいかも含めて、参考にしていただければと思います。

引数を設定する

図１を見ると、親と子の関係は正しいのですが、根の子は左側が小さく、左側の子の子は右側が小さいので、きちんと整列されていない状態なのがわかると思います。
そしてプログラム１の関数名が「makeHeap（ヒープを作る）」であることから、図１で引数を作り、プログラム１を走らせて整列させると判断し、引数を用意しました。

data[]
[0] [1] [2] [3] [4] [5] [6]
60 30 45 15 5 10 20

hnum = 7

makeHeapをトレースする

このような箱を作ります。

heap[]
[0] [1] [2] [3] [4] [5] [6]
　 　 　 　 　 　 　

i k
　 　

１回目のループ

・i: 0, i ＜ hnum, 1
ループはデータ数回繰り返します。
i の初期値は 0 です。

heap[]
[0] [1] [2] [3] [4] [5] [6]
　 　 　 　 　 　 　

i k
0 　

・heap[ i ] ← data[ i ]

heap[]
[0] [1] [2] [3] [4] [5] [6]
60 　 　 　 　 　 　

i k
0 　

・k ← i

heap[]
[0] [1] [2] [3] [4] [5] [6]
60 　 　 　 　 　 　

i k
0 0

k が 0 なので内側のループには入らず、１回目のループは終了です。

２回目のループ

・i: 0, i ＜ hnum, 1
・heap[ i ] ← data[ i ]
・k ← i

heap[]
[0] [1] [2] [3] [4] [5] [6]
60 30 　 　 　 　 　

i k
0 1 0 1

k が 0 より大きいので内側のループに入ります。
空欄ａですが、そもそもいまだ入力されていない子の値を参照することはできないので、 アウエカは消えます。
そして、子が親より大きければ上の処理（親と子を交換する処理）を、子が親以下の値なら下の処理をしたいので、空欄ａはイです。

子より親のほうが大きいので下の処理をします。
break とあるので、何もせず内側のループを抜け、外側のループの２回目は終了です。

３回目のループ

・i: 0, i ＜ hnum, 1
・heap[ i ] ← data[ i ]
・k ← i

heap[]
[0] [1] [2] [3] [4] [5] [6]
60 30 45 　 　 　 　

i k
0 1 2 0 1 2

と、ここまで来てようやく私は自分の勘違いに気づきます。
このままでは最後まで内側のループの上の処理に入れません。

問題を読み進めてみると、私は本プログラムを、
data[]を、副プログラム「makeHeap」を使って完璧に整列させるものと勘違いしたのですが、
実際は、
data[]を、副プログラム「makeHeap」で、まずは親子の関係を整列させ、
副プログラム「downHeap」でヒープの特性を利用して、数列を昇順に整列させるものだと判明するのです。

兄弟関係は並べ直ししません。

引数を自分で作る

なぜこのようなミスを犯したかと言うと、 実は本問には makeHeap を検査する引数は用意されていないのです。
すでに整列し終わった状態の数値しかありません。
結構いじわるですよね。
ではどうすればよいでしょうか？
引数が問題文にないときは自分で作ります。
このテクニックを覚えてください。
過去にも数問ですが、架空の引数を自分で作らなければならない問題があります。

ここでリカバリーのテクニックなのですが、馬鹿正直に独創的な引数を考える必要はありません。
ようは内側のループの上の処理を通ればいいだけなのですから、いままで使ってきた引数をほんのちょこっと加工してしまえばいいのです。

data[3] の値を 5 から 70 に変更します。

４回目のループ

・i: 0, i ＜ hnum, 1
・heap[ i ] ← data[ i ]
・k ← i

heap[]
[0] [1] [2] [3] [4] [5] [6]
60 30 45 70 　 　 　

i k
0 1 2 3 0 1 2 3

k が 0 より大きいので内側のループに入ります。
heap[3] が heap[parent(3)] より大きいので上の処理をします。

副プログラム「swap」は、現在の状態の数列 heap[] と、２つの添え字を引数として与えれば、それを交換してくれます。

空欄ｂは k の親を意味するエです。

・swap[heap, k, parent(k)]
heap[]
[0] [1] [2] [3] [4] [5] [6]
60 30 70 45 70 30 　 　 　

・k ← parent(k)
一番大きい子が親に移動したので、 k も親の要素番号に書き換えます。

i k
0 1 2 3 0 1 2 3 1

k が 0 より大きいのでループします。

heap[1] が heap[parent(1)] より大きいので上の処理をします。

・swap[heap, k, parent(k)]
heap[]
[0] [1] [2] [3] [4] [5] [6]
60 70 30 70 60 45 70 30 　 　 　

・k ← parent(k)
i k
0 1 2 3 0 1 2 3 1 0

ｋ が 0 なのでループを抜けます。

これ以上続けても無意味なので、以降の処理は割愛します。

いちおうの最終結果はこうなります。
heap[]
[0] [1] [2] [3] [4] [5] [6]
60 70 30 70 60 45 70 30 5 10 20

ホームに戻るボタン↓