平成26年春期午後問8

小林さん  
(No.1)
https://www.fe-siken.com/kakomon/26_haru/pm08.html

表1の一つ目のケースですが、

アルゴリズムを見ると
I←1
・・・・
↑ (始点[I]=始点P) and (終点P=終点[I])
|■L:I+1,L<=N,1
||・始点[L-1]←始点[L]
||・終点[L-1]←終点[L]
|■
↓・N←N-1

になっています
この部分が理解できません

始点[1]←始点[2]/終点[1]←終点[2]、始点[2]←始点[3]/終点[2]←終点[3]・・・・・という動きなのでしょうが
なぜひとつづつ前にずらしているのでしょうか

■□□□□□□□□・・・□■

□□□□□□□□・・・□■

□空
■割当済
2022.08.10 17:01
nsさん 
FE シルバーマイスター
(No.2)
「一つずつずらす」というのはその通りですが、何をずらしているのかを理解できていないように見受けられます。

問題文〔空きリストの説明〕(2)の図のような状態を考えます。
図にあるように空きリストの状態は{{-∞, 0}, {3, 5}, {9, +∞}}と表されます。

この空きリストに対してAlloc(3,5)を実行しましょう。真ん中部分の空き領域(3~5)を割り当て済にするような処理です。
i = 2のとき、始点2(= 3) = 始点p(= 3) かつ 終点2(= 5) = 終点p(= 5)となります。
したがって、
始点[2] <- 始点[3](= 9)
終点[2] <- 終点[3](= +∞)
という処理が行われます。

最後にNが1減算されるため、実行後の空きリストの状態は{{-∞, 0}, {9, +∞}}となります。
最初の空きリストの状態から、真ん中の空きブロック(3~5の部分)が埋まった形になりましたね。
2022.08.10 20:43
小林さん  
(No.3)
配列でしたね。理解できました
2022.08.12 14:23

返信投稿用フォーム

スパム防止のためにスレッド作成日から30日経過したスレッドへの書込みはできません。

その他のスレッド


Pagetop