FUNDAMENTAL INFORMATION TECHNOLOGY ENGINEER
基本情報技術者の問題解説
問題
次の手続 greedySelect() を実行したときの戻り値はどれか。
○整数型: greedySelect()
区間は終了時刻の昇順に (1,3), (2,5), (4,7), (6,9), (8,10)
整数型: lastEnd ← 0, c ← 0
各区間 (start, end) について順に調べる
if (start ≧ lastEnd)
c ← c ＋ 1
lastEnd ← end
endif
endfor
return c × 10 ＋ lastEnd- ア 30
- イ 39
- ウ 40
- エ 31
出典：オリジナル問題｜参考範囲：試験要綱Ver.5.5 / FEシラバスVer.9.2 科目B範囲
正解と解説
正解：40
正解：40
終了時刻が早い順に、直前に選んだ区間の終了時刻 lastEnd 以降に始まる区間だけを選ぶ。最初に(1,3)を選び lastEnd=3。次の(2,5)は開始2なので選ばない。(4,7)を選び lastEnd=7、(6,9)は選ばず、(8,10)を選ぶ。選択数c=3、lastEnd=10なので戻り値は40。
30はcだけを10倍した途中の見方、39は最後の区間を(6,9)と誤って選んだ場合に出やすい。31はlastEndではなくcを足した誤り。
貪欲法は、並び順と選択条件が重要。今回は終了時刻順に見て、選んだら lastEnd を更新する。重なる区間は飛ばす。
この問題について
公開問題・サンプル問題の形式、擬似言語記法、アルゴリズム読解・トレース・空欄補充・セキュリティ事例判断の傾向を参考にした独自問題です。本文・数値・選択肢は新規作成しています。
公式試験問題、公開問題、市販教材、外部問題サイトの問題文を転載・改題したものではありません。