次の規則に従って配列の要素A[0]、A[1]、…、A[9]に正の整数k を格納する。
k として16、43、73、24、85を順に格納するとき、85が格納される場所はどこか。
ここで、x mod y はx をy で割った剰余を返す。
また、配列の要素はすべて0に初期化されている。
[規則]
|
| ア | 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(エ)になります。
【キーワード】
・ハッシュ探索
- ハッシュ探索
ハッシュ探索ではデータを格納する位置を計算によって求めます。
その計算式をハッシュ関数と呼びます。(この問題では規則がハッシュ関数になります。)
ハッシュ探索ではハッシュ関数がわかれば、探したいデータの格納位置が計算で簡単に求められるので、探索する時間が非常に短く高速に処理を求めることができます。
ただし、ハッシュ値がぶつかったときの処理の考慮が必要になるのが、使用時の注意点です。
もっと、「ハッシュ探索」について調べてみよう。
戻る
一覧へ
次へ