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

問題文

10進法で5桁の数

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

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

m o d (a_{1} + a_{2} + a_{3} + a_{4} + a_{5}, 13)

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

m o d (x, 13)

は、

x

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

🖊️ 解答を隠して解いてみる

選択肢

ア：1

イ：2（正解）

ウ：7

エ：11

🔒 解説は解答すると表示されます

ハッシュ関数による格納位置【午前解説】

正解の理由

問題のハッシュ関数は明確に「

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

を 13 で割った余り」を用いると定義されています。
54321 の各桁を足すと

5 + 4 + 3 + 2 + 1 = 15

です。これを 13 で割った余りは

15 mod 13 = 2

となるため、配列の位置は 2 が求まります。よって正解はイです。

解法ステップ

与えられた数 54321 を各桁に分解する： $a_{1} = 5, a_{2} = 4, a_{3} = 3, a_{4} = 2, a_{5} = 1$ 。
各桁を合計する： $S = 5 + 4 + 3 + 2 + 1 = 15$ 。
ハッシュ関数に従って剰余を求める： $S mod 13 = 15 mod 13 = 2$ 。
求めた剰余 2 が配列の位置（インデックス）なので、答えは 2（選択肢イ）。

選択肢別の誤答解説

ア: 1 — 桁の和を誤って $14$ と計算し $14 mod 13 = 1$ とした可能性があります。桁和は必ず確認しましょう。
イ: イ — 正解。桁和 $15$ の $15 mod 13 = 2$ に対応します。
ウ: 7 — 「54321 をそのまま $54321 mod 13$ で計算した」場合の結果が 7 になるため、この誤りに対応する選択肢です。問題文のハッシュ定義を読み間違えるとこうなります。
エ: 11 — 桁和や剰余の計算を別の誤った手順（桁を重み付きで足す、あるいは別の基数で計算するなど）で行った結果として出ることがあり得ます。計算手順を再確認してください。

よくある誤解

「54321 をそのまま 13 で割る」：数値全体に mod を取ると余りは 7 になり、誤答（ウ）につながります。
「桁の和を誤って計算する」： $5 + 4 + 3 + 2 + 1$ を 14 や別の値に誤計算すると誤答（アなど）になります。
「配列の位置が 1 始まりだと思い込む」：問題図は 0 から始まるため、インデックス基準の取り違えに注意が必要です。

補足コラム

ハッシュ法では「どの値をハッシュ値にするか（この例では桁和）」と「ハッシュ値を配列サイズに合わせる方法（ここでは mod 13）」の2点が重要です。

インデックスは通常 0 始まりで与えられることが多く、問題の図も0から示されています。
ハッシュ関数の選び方次第で衝突（複数の要素が同じ位置に割り当てられる）が発生します。桁和は簡単ですが衝突が起きやすいことを覚えておきましょう。

FAQ

Q1: mod の意味は何ですか？
A1:

x mod m

は

x

を

m

で割ったときの余りを指します。符号や言い回しに注意してください。

Q2: インデックスが 0 始まりか 1 始まりかはどう判断しますか？
A2: 問題文や図で位置ラベルが示されている場合はそちらに従います。本問の図は 0 から始まっています。

Q3: 桁の和が 13 以上になったらどうしますか？
A3: そのまま

(

桁の和

) mod 13

を計算します。剰余の範囲は

0

から

12

です。

関連キーワード: ハッシュ法、ハッシュ関数、剰余演算、配列インデックス、桁和、衝突対策

← 前の問題へこの年度をクイズで解く次の問題へ →

\ せっかくなら /

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

クイズ画面へ遷移する→

すぐに利用可能！