FUNDAMENTAL INFORMATION TECHNOLOGY ENGINEER
基本情報技術者の問題解説：整列済み配列a,bに共通して現れる値を、重複も含めて数える。…
問題
整列済み配列a,bに共通して現れる値を、重複も含めて数える。戻り値はどれか。
整数型の配列: a ← {1, 2, 2, 4, 7}
整数型の配列: b ← {2, 2, 3, 4, 4, 7}
整数型: i ← 1, j ← 1, count ← 0
while (i ≦ aの要素数 and j ≦ bの要素数)
if (a[i] = b[j])
count ← count ＋ 1
i ← i ＋ 1
j ← j ＋ 1
elseif (a[i] ＜ b[j])
i ← i ＋ 1
else
j ← j ＋ 1
endif
endwhile
return count- ア 3
- イ 4（正解）
- ウ 5
- エ 6
出典：オリジナル問題｜参考範囲：試験要綱Ver.5.5 / FEシラバスVer.9.2 科目B範囲
正解と解説
正解：4
等しいときはiとjの両方を進め、重複も一致回数として数えます。2は2回一致し、4と7も一致します。
比較の流れは、1対2でiを進める、2対2でcount=1，次の2対2でcount=2，4対3でjを進める、4対4でcount=3，7対4でjを進める、7対7でcount=4 となります。
値の種類だけなら3ですが、このコードは一致した回数を数えます。
Hardでの確認点：二つの添字が別々に動く問題では、一致時に両方進むのか、一方だけ進むのかを確認します。重複を含める場合、同じ値が複数回一致するので、値の種類数ではなく一致した回数を数えましょう。
このアルゴリズムの正体：これは整列済みの二つの配列に対する「多重集合の共通部分の要素数」を求める処理で、片方が小さければその添字だけを進めるため、各反復で少なくとも一方が前進します。よって全体の計算量は要素数の和に比例するO(n+m)で、片方ずつ全比較するより効率的です。整列済みである点が成立の前提になります。
この問題について
公開問題・サンプル問題の形式、擬似言語記法、アルゴリズム読解・トレース・空欄補充・セキュリティ事例判断の傾向を参考にした独自問題です。本文・数値・選択肢は新規作成しています。
公式試験問題、公開問題、市販教材、外部問題サイトの問題文を転載・改題したものではありません。