平成30年秋期試験午前問題 午前Ⅰ 問9

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

  • 193
  • 197
  • 199
  • 211
正解 問題へ
分野:テクノロジ系
中分類:アルゴリズムとプログラミング
小分類:アルゴリズム
剰余がそのままハッシュ値となるので、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しかありません。

Pagetop