HOME»応用情報技術者平成25年秋期»午前問7
応用情報技術者平成25年秋期 午前問7
問7
自然数をキーとするデータを,ハッシュ表を用いて管理する。キーxのハッシュ関数h(x)を
h(x) = x mod n
とすると,キーaとbが衝突する条件はどれか。ここで,nはハッシュ表の大きさであり,x mod nはxをnで割った余りを表す。
h(x) = x mod n
とすると,キーaとbが衝突する条件はどれか。ここで,nはハッシュ表の大きさであり,x mod nはxをnで割った余りを表す。
- a+bがnの倍数
- a-bがnの倍数
- nがa+bの倍数
- nがa-bの倍数
- [出題歴]
- 応用情報技術者 R1秋期 問7
- 応用情報技術者 R4秋期 問5
- 応用情報技術者 H21春期 問6
- 応用情報技術者 H23秋期 問5
- 応用情報技術者 H27春期 問5
- ソフトウェア開発技術者 H16春期 問13
- ソフトウェア開発技術者 H17秋期 問13
- ソフトウェア開発技術者 H19秋期 問12
分類
テクノロジ系 » アルゴリズムとプログラミング » アルゴリズム
正解
イ
解説
aをnで割ったときの商をk、bをnで割ったときの商をl、余りがどちらもxとなる場合を式で表すと、
a=kn+x
b=ln+x
となります。これをxについて解くと、
x=a-kn
x=b-ln
と変換できます。余りであるxが等しくなるとき a-kn と b-ln は等しいので、方程式で関係を導きます。
a-kn=b-ln
a-b=kn-ln
a-b=n(k-l)
ここで、aとb及びnが自然数であることから商であるkとlも自然数となります。よって n(k-l) はnの倍数です。
∴余りxが同じとき、a-bはnの倍数
以上より、キーの衝突には「a-bがnの倍数」という条件があるとわかります。したがって「イ」が正解です。
ここまでが論理的に解を導く方法ですが、計算結果が同じになるa・b・nを用意して選択肢の記述の正誤を判断することもできます。例えば、a=51、b=27、n=12(どちらも余りが3)で試してみると、
a=kn+x
b=ln+x
となります。これをxについて解くと、
x=a-kn
x=b-ln
と変換できます。余りであるxが等しくなるとき a-kn と b-ln は等しいので、方程式で関係を導きます。
a-kn=b-ln
a-b=kn-ln
a-b=n(k-l)
ここで、aとb及びnが自然数であることから商であるkとlも自然数となります。よって n(k-l) はnの倍数です。
∴余りxが同じとき、a-bはnの倍数
以上より、キーの衝突には「a-bがnの倍数」という条件があるとわかります。したがって「イ」が正解です。
ここまでが論理的に解を導く方法ですが、計算結果が同じになるa・b・nを用意して選択肢の記述の正誤を判断することもできます。例えば、a=51、b=27、n=12(どちらも余りが3)で試してみると、
- a+b=78なので、12の倍数ではありません(×)。
- a-b=24なので、12の倍数になっています(〇)。
- a+b=78なので、12は78の倍数ではありません(×)。
- a-b=24なので、12は24の倍数ではありません(×)。