基本情報技術者 2010年秋期午前（科目A）問07

問題文

5けたの数

a_{1} a_{2} a_{3} a_{4} a_{5}

を、ハッシュ法を用いて配列に格納したい。ハッシュ関数をmod(

a_{1}

a_{2}

a_{3}

a_{4}

a_{5}

, 13) とし、求めたハッシュ値に対応する位置の配列要素に格納する場合、54321は次の配列のどの位置に入るか。ここで、mod(

x

, 13) の値は、

x

を13で割った余りとする。

選択肢

ア：1

イ：2（正解）

ウ：7

エ：11

5けたの数のハッシュ配置（各桁和を13で除した余り）【午前2 解説】

要点まとめ

結論：54321の各桁の和は $5 + 4 + 3 + 2 + 1 = 15$ であり、 $15 mod 13 = 2$ のため配列位置は2になります。
根拠：ハッシュ関数はmod(各桁の和,13)で定義され、求めた余りがそのまま配列のインデックスとなるルールです。
差がつくポイント：桁和を取ることと0始まりのインデックス（0～12）を使う点を混同しないのが得点差になります。

正解の理由

54321の各桁を足すと

5 + 4 + 3 + 2 + 1 = 15

です。ハッシュ関数は mod(15,13) を求めますから、

15 mod 13 = 2

となり、配列の位置は「2」になります。従って正解はイです。

正解: イ

よくある誤解

各桁の合計ではなく数値自体に対してmodを取る（54321 mod 13）してしまう誤り。問題文の定義を確認すること。
インデックスを1始まりで考え「位置1」とするミス。配列位置が0から0～12である点を見落とす受験者が多いです。
余りの計算で符号やマイナスを誤って扱う（本問では非該当だが一般のmod問題でミスしやすい）点。

解法ステップ

数字54321を桁ごとに分解する（5,4,3,2,1）。
各桁の和を求める： $5 + 4 + 3 + 2 + 1 = 15$ 。
その和を13で割った余りを計算する： $15 mod 13 = 2$ 。
得られた余り $2$ が配列の格納位置となる（答え：位置2）。

参考の簡易計算（Python例）

n = 54321
digits = [int(d) for d in str(n)]
s = sum(digits)            # 15
pos = s % 13               # 2
print(pos)                 # 2

選択肢別の誤答解説

ア: 1 — 各桁和の計算やmodの誤りで15を13で割った余りを1と誤認した可能性。正しくは2です。
イ: 2 — 正解。 $5 + 4 + 3 + 2 + 1 = 15$ 、 $15 mod 13 = 2$ で位置2に格納されます。
ウ: 7 — 例えば桁の配置を逆にして計算したり、別のハッシュ規則（桁の重み付けなど）を誤適用した結果の誤答です。
エ: 11 — 余りの計算を間違えた、もしくは13から差を取るなどの誤った手順によるミスです。

補足コラム

桁和を用いるハッシュは実装が簡単ですが、衝突（異なる数が同じ桁和になる）を起こしやすい点に注意が必要です。より良い分布を得たい場合は、桁に重み付けをして多項式的に評価する手法（例えばローリングハッシュ）や、表のサイズと素数の選定、衝突解決（チェイン法やオープンアドレッシング）を検討します。

FAQ

Q1: modの結果はどの範囲になりますか？
A1: 0以上12以下（13個）の整数になります。本問では0～12のインデックスに対応します。

Q2: もし結果が0ならどこに入りますか？
A2: 位置0に格納します。配列が0始まりであるため余り0は有効なインデックスです。

Q3: 桁和ではなく元の数値を使った場合は？
A3: 問題定義が異なるため、必ず問題文に従ってどの値にmodを適用するかを確認してください。

関連キーワード: ハッシュ法、剰余演算、mod計算、配列インデックス、桁和、衝突、ハッシュ分布、チェイン法、オープンアドレッシング

← 前の問題へ次の問題へ →

\ せっかくなら /

基本情報技術者を
クイズ形式で学習しませんか？

クイズ画面へ遷移する→

すぐに利用可能！