ネットワークスペシャリスト平成30年秋期 午前Ⅰ 問9

問9

自然数を除数とした剰余を返すハッシュ関数がある。値がそれぞれ571,1168,1566である三つのレコードのキー値を入力値としてこのハッシュ関数を施したところ,全てのハッシュ値が衝突した。このとき使用した除数は幾つか。
  • 193
  • 197
  • 199
  • 211
  • [出典]
  • 応用情報技術者
    平成30年秋期 問27と同題

分類

テクノロジ系 » アルゴリズムとプログラミング » アルゴリズム

正解

解説

剰余がそのままハッシュ値となるので、3つの入力値を各除数で割った余りを求め、それらが全て一致するものを導きます。
  • 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しかありません。
© 2015-2024 ネットワークスペシャリストドットコム All Rights Reserved.

Pagetop