FUNDAMENTAL INFORMATION TECHNOLOGY ENGINEER
基本情報技術者の問題解説
問題
次の二ポインタ法で，和が8以下の組の数を求める。戻り値はどれか。
整数型の配列: a ← {1, 2, 3, 5, 7}
整数型: left ← 1, right ← 5, count ← 0
while (left ＜ right)
if (a[left] ＋ a[right] ≦ 8)
count ← count ＋ (right - left)
left ← left ＋ 1
else
right ← right - 1
endif
endwhile
return count- ア 5
- イ 6
- ウ 7
- エ 8
出典：オリジナル問題｜参考範囲：試験要綱Ver.5.5 / FEシラバスVer.9.2 科目B範囲
正解と解説
正解：7
正解：7
配列は昇順なので，a[left]+a[right]が8以下なら，leftとleft+1〜rightまでの全ての組が条件を満たす。そのためcountにright-leftを一気に足す。
| left | right | 判定 | count |
|---|---|---|---|
| 1 | 5 | 1+7≦8 | 4 |
| 2 | 5 | 2+7>8 | 4 |
| 2 | 4 | 2+5≦8 | 6 |
| 3 | 4 | 3+5≦8 | 7 |
最終的にcountは7。条件を満たすたびに1だけ増やすのではない点が重要である。
選択肢の見分け方：5や6は一括加算right-leftを一部しか足していない値，8は条件を超える組まで含めた値である。整列済みであることを利用してまとめて数える。
この問題について
公開問題・サンプル問題の形式、擬似言語記法、アルゴリズム読解・トレース・空欄補充・セキュリティ事例判断の傾向を参考にした独自問題です。本文・数値・選択肢は新規作成しています。
公式試験問題、公開問題、市販教材、外部問題サイトの問題文を転載・改題したものではありません。