本文へスキップ

技術士試験(情報工学部門)・情報技術者試験。ファーストマクロ。


Since 2016.4.19

平成30年度 秋期 応用情報技術者試験問題と解説

問27

自然数を除数とした剰余を返すハッシュ関数がある。値がそれぞれ571、1168、1566である三つのレコードのキー値を入力値としてこのハッシュ関数を施したところ、全てのハッシュ値が衝突した。この時使用した除数は幾つか。

ア 193

イ 197

ウ 199

エ 211


正解


解説

除数を x、剰余を y とおくと、以下が成り立つ。
x+y = 571  ・・・@
x+y = 1168 ・・・A
x+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である。

問26 目次 問28