平成30年秋期試験問題 午前問27
問27解説へ
自然数を除数とした剰余を返すハッシュ関数がある。値がそれぞれ571,1168,1566である三つのレコードのキー値を入力値としてこのハッシュ関数を施したところ,全てのハッシュ値が衝突した。このとき使用した除数は幾つか。
- 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しかありません。
広告