平成18年 秋期 基本情報技術者 午前 問15
次の規則に従って配列の要素A[0], A[1], …, A[9]に正の整数k を格納する。
16, 43, 73, 24, 85を順に格納するとき、85が格納される場所はどこか。
ここで、x mod y はx をy で割った剰余を返す。
また、配列の要素はすべて0に初期化されている。
[規則]
| (1) |
A[k mod 10] = 0ならば、k →A[k mod 10]とする。 |
| (2) |
(1)で格納できないとき、A[(k +1) mod 10] = 0ならば、
k →A[(k + 1) mod 10]とする。 |
| (3) |
(2)で格納できないとき、A[(k + 4) mod 10] = 0ならば、
k →A[(k +4) mod 10]とする。 |
|
| ア |
A[3] |
| イ |
A[5] |
| ウ |
A[6] |
| エ |
A[9] |
答え エ
【解説】
16, 43, 73, 24, 85の順にデータを格納し、答えを求めます。
まず、A[0], A[1], …, A[9]は0に初期化されています。
- 16を格納
規則の(1)で16 mod 10 = 6でA[6] = 0なので、A[6] = 16になります。
- 43を格納
規則の(1)で43 mod 10 = 3でA[3] = 0なので、A[3] = 43 になります。
- 73を格納
規則の(1)で73 mod 10 = 3でA[3] = 43 ≠ 0なので、規則の(2)を適用します。
規則の(2)で(73 + 1) mod 10 = 4でA[4] = 0なので、A[4] = 73になります。
- 24を格納
規則の(1)で24 mod 10 = 4でA[4] = 73 ≠ 0なので、規則の(2)を適用します。
規則の(2)で(24 + 1) mod 10 = 5でA[5] = 0なので、A[5] = 24になります。
- 85を格納
規則の(1)で85 mod 10 = 5でA[5] = 24 ≠ 0なので、規則の(2)を適用します。
規則の(2)で(85 + 1) mod 10 = 6でA[6] = 16 ≠ 0なので、規則の(3)を適用します。
規則の(3)で(85 + 4) mod 10 = 9でA[9] = 0なので、A[9] = 85(エ)になります。
【キーワード】
・ハッシュ探索
【キーワードの解説】
- ハッシュ探索
ハッシュ探索ではデータを格納する位置を計算によって求めます。
その計算式をハッシュ関数と呼びます。(この問題では規則がハッシュ関数になります。)
ハッシュ探索ではハッシュ関数がわかれば、探したいデータの格納位置が計算で簡単に求められるので、探索する時間が非常に短く高速に処理を求めることができます。
ただし、ハッシュ値がぶつかったときの処理の考慮が必要になるのが、使用時の注意点です。
戻る
一覧へ
次へ