基本情報技術者 試験情報＆徹底解説 -新制度に完全対応-

キーxのハッシュ関数として h(x)＝mod(x，97)を用いるとき，キー1094とハッシュ値が一致するものは，キー1～1000の中に幾つあるか。
という問題の解答解説で、
「xを満たす値は0～10までの11種なので答えは11個」とあります。

問題を読むと、キーxは1以上のはずなのに、なぜ0を含めた個数が正解となるのでしょうか。

いつの過去問でしょうか？

掲題の過去問のリンクを貼らせて頂きます。

[PC版]
https://www.fe-siken.com/kakomon/20_haru/q14.html

[SP版]
https://www.fe-siken.com/s/kakomon/20_haru/q14.html

この投稿は投稿者により削除されました。(2020.07.12 10:46)

この投稿は投稿者により削除されました。(2020.07.12 10:44)

掲題の過去問へのご質問に回答させて頂きます。

1094÷97＝11余り27ですので、
「キー1～1000の中でキー1094とハッシュ値が一致するもの」は
キーｘ、商ｎを用いると、ｘ＝97×ｎ＋27で表せます。

ｎ＝11のときx＝1094＞1000のため、nは11未満です。

ｎ、ｘが最大となるのは、
ｎを一つずつ下げ、最初にx＜＝1000となるときです。
ｎ＝10のとき、ｘ＝97×10＋27＝997＜1000となり、
ｎの最大値は10、ｘの最大値は997です。

ｎ、ｘが最小となるのは、ｘがハッシュ値自身になるときで、
ｎの最小値は0、ｘの最小値は27です。

解説の不等式の変数ｘは、設問のキーｘではなく、
上記のｎに相当するようですので、
ｎに読替えていただければすっきりすると思います。
ｎ＝０を含むのは、キーが最小になるとき、
ハッシュ値と同じになる時を考慮してのことと考えます。

別解を考えました。
[別解]
1094÷97＝11余り27なので
「キー1～1000の中でキー1094とハッシュ値が一致するもの」は
「キー1～1000の中で、97で割った余りが27になる整数」です。

条件に該当するキーは以下の特徴があります。
・各キーの差分は97
・キーの最大値は、1094から97づつ引いて最初に1000以下になったもの
・キーの最小値は、ハッシュ値自身

1094－97＝997＜1000なのでキーの最大値は997
ハッシュ値は27なのでキーの最小値は27
条件を満たすキーの個数は
{(最大値－最小値)÷差分}＋1＝{(997ー27)÷97}＋1＝11

おわ！さん

別解まで教えていただきありがとうございます。
ハッシュ値自身がキーの最小値となるというのが理解できました。

一つ気になるのは問題文の解釈です。
「キーxのハッシュ関数  h(x)=mod(x,97)」のh(x)というのはキーx=1094の時、h(1094)ではなくh(11)になると言いうことでしょうか？
つまり、キーxとh(x)は、全く別のxを表しているということでしょうか。

miniさん
ご質問に回答致します。

問題文のハッシュ関数h(x)は、
引数xを97で割った余りを返す関数です。
引数xをキー、戻り値をハッシュ値と呼んでいます。

h(x)＝mod(x，97) はキーxが1094のときは、
h(1094)＝27 を返します。
h(11)＝11 は返しません。

キーxはh(x)の引数ですので、
キーxとh(x)のxは同じxを表しています。

問題文の解釈ですが、
以下の条件を満たすxの「個数」を求める問題に帰着されます。
・h(x)＝mod(x，97)＝27
・xは1以上1000以下の整数

正解の11はキーxの値ではなく、条件を満たすキーxの個数です。

条件を満たすxの個数の求め方はいろいろあります。
xを97で割った商をnとして
x＝97×n＋27 で表せることに着目し、
nの取り得る値（0, 1, ..., 10）の個数11からxの個数11を導く、
あるいは、xの取り得る値（27, 124, ..., 900, 997）から
直接xの個数11を導くなどがあります。
不等式を使ってn の個数を求めてもよし、
xの最大値と最小値と差分からxの個数を求めてもよし、
やりやすい方法でどうぞ、です。

おわ！さん

おかげさまで謎が解けました！
条件を満たす個数を求める考え方について、理解が深まってきました。
私の感覚になっちゃうんですが、キーxが初期値27、増分97でループのようなことをしていて、その繰り返し条件がx<=1,000の間みたいな感じなんですね！
とても勉強になりました！ありがとうございました！！

miniさん

>キーxが初期値27、増分97でループのようなことをしていて、
>その繰り返し条件がx<=1,000の間みたいな感じなんですね！

お見事です。完璧です！
私の回答よりずっと本質的で、分かりやすいです。
管理人様の解説の後半は、上記の動きをトレースしたものですね。
こちらこそ勉強になりました。ご丁寧にありがとうございました。

不等式の中でキー値と同じ x を使用してしまったため混乱させてしまった部分があったかもしれません。解説を改善させていただきました。

管理人様

ご対応ありがとうございます。
更新頂いた解説を拝読致しました。
大変分かりやすいです。

今後とも宜しくお願い致します。

nの最大値+1でもいいよね。