アルゴリズム(全101問中19問目)
No.19解説へ
自然数を除数とした剰余を返すハッシュ関数がある。値がそれぞれ571，1168，1566である三つのレコードのキー値を入力値としてこのハッシュ関数を施したところ，全てのハッシュ値が衝突した。このとき使用した除数は幾つか。
出典：平成30年秋期 問27
- 193
- 197
- 199
- 211
広告
解説
剰余がそのままハッシュ値となるので、3つの入力値を各除数で割った余りを求め、それらが全て一致するものを導きます。
571－ax＝1168－bx
－ax＋bx＝597
(b－a)x＝597
(b－a)は自然数なのでxは597の約数、選択肢の中で597の約数であるのは199しかありません。
- 571÷193＝2 余り 185
1168÷193＝6 余り 10
1566÷193＝8 余り 22
剰余が異なるので誤りです。 - 571÷197＝2 余り 177
1168÷197＝5 余り 183
1566÷197＝7 余り 187
剰余が異なるので誤りです。 - 571÷199＝2 余り 173
1168÷199＝5 余り 173
1566÷199＝7 余り 173
剰余が一致するので正解です。 - 571÷211＝2 余り 149
1168÷211＝5 余り 113
1566÷211＝7 余り 89
剰余が異なるので誤りです。
571－ax＝1168－bx
－ax＋bx＝597
(b－a)x＝597
(b－a)は自然数なのでxは597の約数、選択肢の中で597の約数であるのは199しかありません。
広告