FUNDAMENTAL INFORMATION TECHNOLOGY ENGINEER
基本情報技術者の問題解説
問題
配列 a={3,1,2,5,4} に対して、次の手続 lisScore(a) を実行したときの戻り値はどれか。
○整数型: lisScore(整数型の配列: a)
整数型の配列: dp[1..aの要素数]
整数型: i, j, best ← 1
for (i を 1 から aの要素数 まで 1ずつ増やす)
dp[i] ← 1
for (j を 1 から i － 1 まで 1ずつ増やす)
if (a[j] ＜ a[i] and dp[j] ＋ 1 ＞ dp[i])
dp[i] ← dp[j] ＋ 1
endif
endfor
if (dp[i] ＞ best)
best ← dp[i]
endif
endfor
return best × 10 ＋ dp[aの要素数]- ア 23
- イ 32
- ウ 33
- エ 34
出典：オリジナル問題｜参考範囲：試験要綱Ver.5.5 / FEシラバスVer.9.2 科目B範囲
正解と解説
正解：33
正解：33
各位置で終わる増加部分列の長さをdpに入れる。a[1]=3は1、a[2]=1も1、a[3]=2は1→2で長さ2、a[4]=5は1,2,5などで長さ3、a[5]=4も1,2,4で長さ3。best=3、dp[5]=3なので戻り値は33。
32は最後のdp[5]を2とした場合、34は5番目の値4を戻り値の一部に使った誤り。23はbestとdp[5]を逆または途中値で読んでいる。
LISのDPでは、dp[i]は全体の最大ではなく「i番目で終わる最大長」。最後にbestとdp[n]が同じとは限らないが、この問題ではどちらも3になる。
この問題について
公開問題・サンプル問題の形式、擬似言語記法、アルゴリズム読解・トレース・空欄補充・セキュリティ事例判断の傾向を参考にした独自問題です。本文・数値・選択肢は新規作成しています。
公式試験問題、公開問題、市販教材、外部問題サイトの問題文を転載・改題したものではありません。