作成日 2014/2/16
最終更新日 2014/2/16

応用情報H25秋 問7の解説

 応用情報H25秋 問7の解説をします。


分野:テクノロジ系
大分類:基礎理論
中分類:アルゴリズムとプログラミング
小分類:アルゴリズム

1.問題
2.解説


1.問題

 自然数をキーとするデータを,ハッシュ表を用いて管理する。キーx のハッシュ関数h (x )を
   h (x ) = x mod n
とすると,キーab が衝突する条件はどれか。ここで,n はハッシュ表の大きさであり,x mod nxn で割った余りを表す。

ア a + bn の倍数   イ a - bn の倍数
ウ na + b の倍数   エ na - b の倍数
このページのトップへ

2.解説

 数学としては、一応、商と余りの関係ということで、高校2年生レベルかな。でも、そんなに難しくはないです。


◆普通に解く
 an で割った余りを R とします。
 すると、
   a = k × n + R (k の具体的な値は不明だが、整数ではある)
 という式が成り立ちます。
 同じように、
   b = j × n + R (j の具体的な値は不明だが、整数ではある。k とは違っていても良いし、同じでも良い)
 という式が成り立ちます。
ab も、n の倍数にR を足したものであるということを数式で表しています。

 2つの式を「R = 」の式に直します。すると、

   R = a - k × n
   R = b - j × n

 という式が出てきます。2つは同じだから(「R = 」)で始まっているから、
   a - k × n = b - j × n
 とすることが出来ます。
 これを式変形すると、
   a - b = (k - j ) × n
 となります。(k - j ) は整数だから、a - bn の倍数であることが分かります。

よって、答えはイです。

◆実際に値を当てはめてる
 この方法でも答えを出すことが可能です。
 しかも、そんなに計算時間もかかりません。この方法もお勧めできます。
   a = 12
   b = 22
   n = 10
 だったら、どうでしょうか?n = 10 だから、余りを計算するのは簡単ですし。
   a + b = 34
   a - b = 10
 となります。
 ここから、アとウが選択から外れます。

 他の数字で試してみます。
   a = 12
   b = 122
   n = 10
 の場合は、
   a + b = 134
   a - b = 110
 ということで、エも選択から外れます。

よって、答えはイです。
Prev Up Next  Top
このページのトップへ


このページの利用によって発生した、いかなる損害について、このホームページの作成者は責任を負いません。
このページの間違いや嘘を見つけた方、このページに書いて欲しい情報がある方はメールをお願いします。

Microsoft 、Windows 、Visual Basic および Excel は米国Microsoft Corporationの米国およびその他の国における登録商標または商標です。
ここではExcel® をエクセル、Visual Basic® for Applications をVBAと表記する場合があります。
Mac 、Mac OS 、Mac OS X は米国Apple Computer,Inc.の登録商標または商標です。
その他、社名および商品名、システム名称などは、一般に各社の商標または登録商標です。

このホームページの作成者はこれらの会社とはいっさい関係がありません。