HOME»基本情報技術者試験掲示板»平成26年春期 午後問8 アルゴリズム 設問2
投稿する

[0725] 平成26年春期 午後問8 アルゴリズム 設問2

 名無しさん(No.1) 
Lのループが何をしているか分かりません。
どなたか解説して下さい。
宜しくお願い致します。
2016.10.12 14:17
multi777さん(No.2) 
このループは表1の4番目のケースを示しています。
とりあえず領域Iの部分についてのみ着目すると
(空領域を*、確保領域を■で表します。この場合*の一番左の位置が始点I、*の一番右の位置が終点I)
…■**********■…
となっている部分が
…■***■■■■***■…
というように空領域が2つに分割されます。
(左の空領域の組がI番目、右の空領域の組がI+1番目)

実際に空領域の分布をこれに当てはめてみると
[1]|■|[2]|■…■|[     I     ]|■|[I+1]|■…■|[N]
↓[I]の間に領域を確保する(始点I<始点P  かつ  終点P<終点I)
[1]|■|[2]|■…■|[I]|■|[I+1]|■|[I+2]|■…■|[N+1] (IとI+1の間に領域が増えるのでI+1以降の組が+1される)

という感じになります。
なので、この処理では
①  既存のI+1番目~N番目に格納されている値をI+2番目~N+1番目に格納する(ループ部分)
②  I+1番目の空領域を更新する((終点P)+1~終点I)
③  I番目の空領域を更新する(始点I~(始点P)-1)

といった流れになります。
②、③についてはループ後の処理となっているので、ループ部分を考えてみると、
設定されている値を消すことなく格納されている組を+1するので
N番目 →  N+1番目に格納
N-1番目 →  N番目に格納

I+1番目 →  I+2番目に格納
の順で処理をしていきます。
なので、ループについては
LをN~I+1まで1ずつ減らしてループすることになるので
N, L≧I+1, -1
の(ウ)になります。
2016.10.14 00:04
 名無しさん(No.3) 
multi777さんありがとうございます。
2016.10.14 10:13

返信投稿用フォーム

スパム防止のためにスレッド作成日から30日経過したスレッドへの書込みはできません。
© 2010-2024 基本情報技術者試験ドットコム All Rights Reserved.

Pagetop