平成30年度 秋期
応用情報技術者試験問題と解答
問27
自然数を除数とした剰余を返すハッシュ関数がある。値がそれぞれ571、
1168、1566である三つのレコードのキー値を入力値としてこのハッシュ
関数を施したところ、全てのハッシュ値が衝突した。この時使用した除数は
幾つか。

 ア 193  イ 197  ウ 199  エ 211



【正解】 ウ

除数をx、剰余をy とおくと、以下が成り立つ。
x×A+y = 571   ・・・@
x×B+y = 1168  ・・・A
x×C+y = 1566  ・・・B

A−@より (B−A)x=1168−571 = 597 ・・・C
B−@より (C−A)x=1566−571 = 995 ・・・D
B−Aより (C−B)x=1566−1168 = 398 ・・・E

C-Eより (B−A−C+B)x = 199

199は素数だから x =
199
すなわち、除数は
199である。

EXCEL VBAのご相談なら ファーストマクロ 



問26 目次 問28
ファーストマクロ TOPページ