FUNDAMENTAL INFORMATION TECHNOLOGY ENGINEER
基本情報技術者の問題解説
問題
配列 a={3,1,4,1,5,9} に対して、次の手続 prefixQuery(a) を実行したときの戻り値はどれか。
○整数型: prefixQuery(整数型の配列: a)
整数型の配列: p[0..aの要素数]
整数型: i, s ← 0, x
p[0] ← 0
for (i を 1 から aの要素数 まで 1ずつ増やす)
p[i] ← p[i － 1] ＋ a[i]
endfor
区間 (2,5), (1,3), (4,6) をこの順に処理する
各区間 (l,r) について
x ← p[r] － p[l － 1]
if (x mod 2 = 0)
s ← s ＋ x ÷ 2 の商
else
s ← s ＋ x
endif
endfor
return s- ア 26
- イ 29
- ウ 30
- エ 34
出典：オリジナル問題｜参考範囲：試験要綱Ver.5.5 / FEシラバスVer.9.2 科目B範囲
正解と解説
正解：30
正解：30
累積和は p={0,3,4,8,9,14,23}。区間(2,5)の和は11で奇数なので+11。区間(1,3)の和は8で偶数なので+4。区間(4,6)の和は15で奇数なので+15。合計は30。
29は偶数区間8をそのまま8ではなく半分にする処理の前後を混同した場合に出やすい。34はすべての区間和をそのまま足した値、26は最後の区間の始点を誤った値に近い。
累積和は p[r]-p[l-1] で区間和を取る。求めた区間和をそのまま使うとは限らず、その後の偶奇分岐まで追う。
この問題について
公開問題・サンプル問題の形式、擬似言語記法、アルゴリズム読解・トレース・空欄補充・セキュリティ事例判断の傾向を参考にした独自問題です。本文・数値・選択肢は新規作成しています。
公式試験問題、公開問題、市販教材、外部問題サイトの問題文を転載・改題したものではありません。