FUNDAMENTAL INFORMATION TECHNOLOGY ENGINEER
基本情報技術者の問題解説：次の手続 greedySelect() を実行したときの戻り…
問題
次の手続 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
終了時刻が早い順に、直前に選んだ区間の終了時刻 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 を更新します。重なる区間は飛ばしましょう。
この問題について
公開問題・サンプル問題の形式、擬似言語記法、アルゴリズム読解・トレース・空欄補充・セキュリティ事例判断の傾向を参考にした独自問題です。本文・数値・選択肢は新規作成しています。
公式試験問題、公開問題、市販教材、外部問題サイトの問題文を転載・改題したものではありません。