FUNDAMENTAL INFORMATION TECHNOLOGY ENGINEER
基本情報技術者の問題解説：次の長さ3の区間を調べるプログラムを実行したとき、戻り値はど…
問題
次の長さ3の区間を調べるプログラムを実行したとき、戻り値はどれか。
整数型の配列: a ← {2, 1, 3, 2, 4, 1}
整数型: left, right, sum ← 0, count ← 0
for (right を 1 から aの要素数 まで 1ずつ増やす)
sum ← sum ＋ a[right]
if (right ≧ 3)
if (sum ≧ 7)
count ← count ＋ 1
endif
sum ← sum － a[right - 2]
endif
endfor
return count- ア 1
- イ 2（正解）
- ウ 3
- エ 4
出典：オリジナル問題｜参考範囲：試験要綱Ver.5.5 / FEシラバスVer.9.2 科目B範囲
正解と解説
正解：2
rightが3以上になった時点から、直近3要素のsumを判定します。判定後にa[right-2]を引いて、次の区間へ窓を1つ進めます。
| right | 判定区間 | sum | count |
|---|---|---|---|
| 3 | {2,1,3} | 6 | 0 |
| 4 | {1,3,2} | 6 | 0 |
| 5 | {3,2,4} | 9 | 1 |
| 6 | {2,4,1} | 7 | 2 |
7以上の区間は2つです。sumを毎回全計算するのではなく、足してから古い要素を引く流れを追います。
選択肢の見分け方：1は9の区間だけを数えた値、3や4は長さ3以外の区間まで数えた誤りです。sumを判定した後に古い要素を引く順番が大切です。
このアルゴリズムの正体：区間ごとにsumを足し直さず、新しい要素a[right]を足して古いa[right-2]を引くことで窓を1つずらす「スライディングウィンドウ」です。各区間で3要素を毎回合計するとO(n×k)ですが、この方式なら1要素あたり加算と減算が一定回数で済み、全体O(n)で処理できます。
この問題について
公開問題・サンプル問題の形式、擬似言語記法、アルゴリズム読解・トレース・空欄補充・セキュリティ事例判断の傾向を参考にした独自問題です。本文・数値・選択肢は新規作成しています。
公式試験問題、公開問題、市販教材、外部問題サイトの問題文を転載・改題したものではありません。