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

問題文

10進法で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

##: ハッシュ法（各桁の総和を mod 13）による格納位置判定【午前2 解説】

要点まとめ

結論：54321 の各桁和は $5 + 4 + 3 + 2 + 1 = 15$ であり、 $15 mod 13 = 2$ なので配列の位置は 2 です。
根拠：問題のハッシュ関数は「各桁の和を13で割った余り」を位置とするため、桁ごとの和を計算して剰余を求めます。
差がつくポイント：図の配列が位置0〜12で表されている点を見落とさず、0始まりのインデックスで答えることが重要です。

正解の理由

与えられたハッシュ関数は mod(

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

, 13) です。
54321 の各桁和を計算すると

5 + 4 + 3 + 2 + 1 = 15

となり、これを13で割った余りは

15 - 13 = 2

、すなわち

15 mod 13 = 2

です。
配列の「位置」ラベルが0から始まっているため、求めたハッシュ値 2 に対応する配列セルが格納位置となります。したがって正解はイ（2）です。

よくある誤解

「54321 をそのまま 13 で割る」という誤り：これは数値全体の剰余で、問題で指定された関数とは異なります（その場合は 7 になります）。
インデックスが1始まりと誤認するミス：図の位置ラベルが0からなので、0始まりで考えないとオフバイワンになります。
桁の和の計算ミス：桁を読み間違えたり、桁を逆に扱って誤った和を出すと余りが変わります。

解法ステップ

与えられた数の各桁を取り出す：5, 4, 3, 2, 1。
各桁を足し合わせる： $5 + 4 + 3 + 2 + 1 = 15$ 。
その和を13で割った余りを求める： $15 mod 13 = 2$ 。
図の「位置」ラベルが0〜12であることを確認し、余り2に対応する配列位置に格納する。

選択肢別の誤答解説

ア: 1 — 桁の和を誤って14と計算してしまった場合に出る答えです。桁和は15であり誤りです。
イ: 2 — 正解。 $5 + 4 + 3 + 2 + 1 = 15$ 、 $15 mod 13 = 2$ に一致します。
ウ: 7 — 54321 をそのまま $13$ で割った余り（ $54321 mod 13 = 7$ ）を答えてしまったケースです。問題は「桁の和」を使う点に注意。
エ: 11 — 桁や計算手順を別の方法で誤解し、異なる和や演算（例：桁を重み付きで処理する等）をしてしまった場合に出る値で、定義と一致しません。

補足コラム

この問題のハッシュ法（桁の和を剰余で取る）は実装が簡単ですが、分布が偏りやすく実用的なハッシュ関数としては脆弱です。実務では桁ごとに重みを付ける多項式ハッシュや暗号学的なハッシュ、良質な乱数的拡散を持つ関数が用いられます。試験問題では「与えられた定義に従って正確に計算すること」が重要です。また、mod 演算の性質として

(a + b) mod m = (a mod m + b mod m) mod m

が使える場面もあります。

FAQ

Q1: mod の結果はどの範囲ですか？
A1: mod(

x

,13) の結果は 0 から 12 までの整数です。

Q2: 位置の数え方が問題文で曖昧なときは？
A2: 図や説明で明示されていればその通りに、明示がない場合は一般的に図中のラベル（0始まりか1始まり）を優先します。

Q3: もし桁にマイナスやアルファベットが混じっていたら？
A3: 問題の定義に従い、扱われる文字や形式に合わせて変換ルール（数値変換やASCII変換など）を適用します。

Q4: 累乗や重み付き和を使うべき場合は？
A4: 配列の衝突を避けたい実用用途では、各桁に重みを付ける方法（例えば多項式ハッシュ）がよく使われます。

関連キーワード: ハッシュ法、ハッシュ関数、剰余演算、桁和ハッシュ、衝突回避、配列インデックス、モジュロ演算、オフバイワン

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

\ せっかくなら /

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

クイズ画面へ遷移する→

すぐに利用可能！