FUNDAMENTAL INFORMATION TECHNOLOGY ENGINEER
基本情報技術者の問題解説
問題
配列 a={2,1,3,2} に対して、次の手続 dpHard(a) を実行したときの戻り値はどれか。
○整数型: dpHard(整数型の配列: a)
整数型の配列: dp[0..aの要素数]
整数型: i
dp[0] ← 0
dp[1] ← a[1]
for (i を 2 から aの要素数 まで 1ずつ増やす)
if (dp[i － 1] ＞ dp[i － 2] ＋ a[i])
dp[i] ← dp[i － 1]
else
dp[i] ← dp[i － 2] ＋ a[i]
endif
endfor
return dp[aの要素数]- ア 4
- イ 5
- ウ 6
- エ 7
出典：オリジナル問題｜参考範囲：試験要綱Ver.5.5 / FEシラバスVer.9.2 科目B範囲
正解と解説
正解：5
正解：5
隣り合う要素を同時に選ばない最大和を dp で求めている。dp[1]=2。i=2では max(2,1)=2、i=3では max(2,2+3)=5、i=4では max(5,2+2)=5 となる。したがって戻り値は dp[4]=5。
6は3と2を隣接して選んでしまった場合、7は2+3+2のように制約を無視した場合に出やすい。4は最後の dp[4] 更新だけを見た途中値。
DPでは、dp[i] が何を表すかを先に決める。この問題では「i番目まで見たときの最大和」なので、選ぶ場合は dp[i-2]+a[i]、選ばない場合は dp[i-1]。
この問題について
公開問題・サンプル問題の形式、擬似言語記法、アルゴリズム読解・トレース・空欄補充・セキュリティ事例判断の傾向を参考にした独自問題です。本文・数値・選択肢は新規作成しています。
公式試験問題、公開問題、市販教材、外部問題サイトの問題文を転載・改題したものではありません。