パソコン教室・IT資格情報処理技術者試験対策講座基本情報技術者試験レッスンノート 2014年度春期 午後問8の解説

2014年度春期 午後問8の解説

基本情報技術者試験対策講座のレッスンノート

レッスンノートって?レッスンノートって?

2/25のレッスン内容は、以下の通りです。

 ○ 2014年度春期 午後問8(つづき)

詳細を以下に記します。

□ 2014年度春期 午後問8

前回解説した設問1は、問題本文のみの情報で答えるものでした。

今回の設問2から、擬似言語が出てきます。

○ 擬似言語について

データ構造とアルゴリズム分野の問題で、最大の壁となるのが「擬似言語と、問題本文の仕様説明との関連付け」となります。

そこで、今回擬似言語で記述された関数Allocを見ていきましょう。

(1) 始点と終点の管理

この擬似言語では、空きリスト{{始点1,終点1},{始点2,終点2},・・・,{始点N,終点N}}の情報を、始点と終点という別々の配列で管理しています。

 始点={始点[1], 始点[2],・・・,始点[N]}, 一般項を始点[I](I=1,2,・・・,N)で示す
 終点={終点[1], 終点[2],・・・,終点[N]}, 一般項を終点[I](I=1,2,・・・,N)で示す

(2) パラメータで指定された始点P、終点Pの条件チェック

この関数では、I番目の空き要素{始点[I],終点[I]}の範囲内に始点P~終点Pが収まるという条件を満たす必要があり、この場合のみ処理を実施する仕様になっています。

そしてこの条件を満たすためには、終点P≦終点[I](Iは、この不等式を満たす最小数)かつ始点[I]≦始点Pを両方満たす必要があります。

そこで、最初のループ部分ではI=1から順番に見ていき「初めて終点P≦終点[I]を満たす」ようなIを探し、I番目となり得る候補の場所を探しています。

さらに始点[I]≦始点Pを満たすことをチェックして、前述の条件を満たすことが確認できることになります。

(3) 割り当て処理

割り当て処理は、実際は「始点P~終点Pの範囲を、空きリストから除外する」というものになります。

空き要素に対する始点P~終点Pの重なりかたは前回レッスンでお話ししたように4通りあり、その4通りが別々の条件文内で処理されています。


○ 空欄 e

今回は3つの空欄のうち、eを見ていきました。eは、始点P~終点Pが空き要素に対して中抜きのような形で指定された場合です。

この場合、空き要素の数が+1されることになります(元々のI番目が、I番目とI+1番目に分かれるため)。そして、元々のI+1番目以降を新しいI+2番目以降に変更する必要があります。

元々の要素番号を大きい側にずらす場合、ずらす処理は「大きい要素番号側」からおこなう必要があります。そして今回は、I+1番目も対象となりますね。

よって、正解はウとなります。
このレッスンノートを書いたコーチ

実体験で培ったノウハウで、あなたの合格を戦略的にアシストします

基本情報技術者試験対策セミナー
源田雄一 (基本情報技術者試験)

品川・戸塚・武蔵中原・立川・北府中・新横浜・町田・関内・石川町・八幡山・京王永山・相...

レッスンノート ページ先頭へ

基本情報技術者試験情報

サイタの基本情報技術者試験講師がブログを通して、基本情報技術者試験情報を発信。更新情報のチェックはこちらから!