平成26年春期午後問8

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

設問3のfに関して質問です.

なぜアが答えになるのか疑問があります.
「ウ」が適切ではないということは,空きセルがなくなるということ
つまり,「ア」で空きリストがなくなるということにはなりませんか?
2021.11.02 19:30
chihiroさん 
FE プラチナマイスター
(No.2)
"空き"セルと空きリストを混同してませんか?
たとえ始点1を-∞に、終点Nを+∞に設定しても、セルを並べている領域自体は有限なので、領域を全て使用すれば"空き"セルはなくなります。
始点や終点を∞値に設定したからといって領域が広がったり無限になるわけではないのです。
アは空き「リスト」の話であり、これは領域を全部使用しようが必ず1つは存在します。
2021.11.02 19:54
nhさん  
(No.3)
>chihiroさん

ご回答いただきありがとうございます.
おっしゃる通り,"空き"セルと空きリストの定義があいまいです...
空きリストの中の個々のセルが空きセルという認識ではないのでしょうか?
2021.11.03 10:43
chihiroさん 
FE プラチナマイスター
(No.4)
空きセルは領域中のセルのうち、未使用のセルのことです。(これについてはおそらく認識されている通りだと思います。)
空きリストは、領域中の各セルの使用状況("空き"又は"割当済み")の情報です。
領域中のセルが全て"割当済み"にはなっていない("空き"状態のセルが1つでも存在する)のであれば、仰る通り空きリストのうち、領域内に含まれるセルについては空きセルとなります。
一方、領域中のセルが全て"割当済み"になっている場合("空き"状態のセルが存在しない)は、空きリストは{{-∞,S-1},{E+1,+∞}}(S,Eはそれぞれ領域内のセルの先頭、終端とします)となります。当然ながらこの場合、空きセルは存在しません。(全部使っているのですから)
仮に始点1をS、終点NをEに設定した場合、全てのセルを使用すると空きリストは空になります。
そうなると困るので、始点1を-∞、終点Nを+∞に設定することで領域内の各セルをどんな風に使用してもリストが常に1つ以上存在するようにしているわけです。
要するに空きリストとは、単に領域内のセルの利用状況を表しているだけで、空きリストに対応するセル="空き"状態のセルになるとは限らないのです。(例えば上に書いたように、{{-∞,S-1},{E+1,+∞}}の個々のセルは"空き"状態のセルではないですよね?)
長くなりましたがこんなところです。
2021.11.03 13:30
nhさん  
(No.5)
>chihiroさん

ご丁寧にありがとうございます.
「領域」を全く考えていなかったため誤解が生じていました.
理解できました.
2021.11.03 17:25

返信投稿用フォーム

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

その他のスレッド


Pagetop