HOME»基本情報技術者試験掲示板»平成26年春期午後問8
投稿する
空きリスト{{始点1，終点1}，{始点N，終点N}}
のように、このような場合は二組。
残っている状態 空きリスト{{始点1，終点1}，{始点N，終点N}}
残っていない状態 空きリスト｛なし｝
これは想像ができない。
このような解釈をしています。
についてですが、
で解説した通り、セルを使い切っていても、「{-∞,-1}, {10, ∞}」の2個のセルがあります。
この状態のように、-∞, ∞を設けることで、空きリストの組の個数が0にならないようにされているため、正解はアです。
平成26年春期午後問8 [3840]
初心者さん(No.1)
https://www.fe-siken.com/kakomon/26_haru/pm08.html
設問３の「ｆ」で質問があります。
イ、ウ、エがなぜ不正解なのか解説を見てもわかりませんでした。
よろしくお願いいたします。
設問３の「ｆ」で質問があります。
イ、ウ、エがなぜ不正解なのか解説を見てもわかりませんでした。
よろしくお願いいたします。
2021.11.15 10:43
KanaSatoさん(No.2)
ｆに関する解答群がそれぞれ主張していることについてはわかりますか？
とはどういうことなのかわかりますか？「空きリスト中の組」とは何なのかわかりますか？
領域に空きセルが残っている状態・残っていない状態を想像できますか？
「領域中の一つの連続した"空き"セル」が何なのかわかりますか？「一つの組で表せる」とはどういうことなのかわかりますか？
これらがわからないとイウエが不正解である理由がわかるわけがありません。
まずは、どこまでわかってどこからわからないのかを教えてください。
＞関数 Free の実行時に空きリスト中の組の個数が 2 以上であることが保証される
とはどういうことなのかわかりますか？「空きリスト中の組」とは何なのかわかりますか？
＞始点1 又は 終点N の値が変わらない限り領域中に"空き"セルが残っている
領域に空きセルが残っている状態・残っていない状態を想像できますか？
＞領域中の一つの連続した"空き"セルが幾ら長くても一つの組で表せる
「領域中の一つの連続した"空き"セル」が何なのかわかりますか？「一つの組で表せる」とはどういうことなのかわかりますか？
これらがわからないとイウエが不正解である理由がわかるわけがありません。
まずは、どこまでわかってどこからわからないのかを教えてください。
2021.11.15 11:13
初心者さん(No.3)
＞関数 Free の実行時に空きリスト中の組の個数が 2 以上であることが保証される
空きリスト{{始点1，終点1}，{始点N，終点N}}
のように、このような場合は二組。
＞始点1 又は 終点N の値が変わらない限り領域中に"空き"セルが残っている
残っている状態 空きリスト{{始点1，終点1}，{始点N，終点N}}
残っていない状態 空きリスト｛なし｝
＞領域中の一つの連続した"空き"セルが幾ら長くても一つの組で表せる
これは想像ができない。
このような解釈をしています。
2021.11.15 11:36
KanaSatoさん(No.4)
OKです。
についてですが、通常関数freeが実行されるときというのは、どこかしらのメモリが使われている状態というのが通常想定されるべき状態です。しかしながら、もし、どこのメモリも使われていなかったとしたら、「空きリスト中の組」はどうなるでしょうか？
空きメモリの組は、{-∞,∞}の一組です。したがって、「空きリスト中の組の個数が 2 以上であることが保証される」は誤りであるといえるわけです。
についてですが、「[空きリストの説明〕」の図でいうところの、1から9のすべてが埋まってしまうことがあるかないかと聞かれています。
これについては、あるので「領域中に"空き"セルが残っている」も誤りであるといえます。
なお、空きセルがない状態の空きリストは「{-∞,-1}{10,∞}」と書き表せます。したがって、空きセルがなくても空きリストがなくなることはないことに注意してください。
についてですが、「連続した"空き"セル」というのは、例えば、セル番号0と1が空いている状態です。
この場合の空きリストは{0,1}と書けます。
「一つの連続した"空き"セルが幾ら長くても」というのは、今回の場合は0～9までなので想像がつきにくいと思いますが、
これが0～9999だったとして、0～9000までが連続した空きセルであるなら、空きリストはどのように表せるかということです。
空きセル0～1が{0,1}で書けるのと同じように、空きセル0～9000も{0,9000}と書けます。
これが、「領域中の一つの連続した"空き"セルが幾ら長くても一つの組で表せる」ということです。
しかし、これは-∞や∞を設けなくてもできることです。そのため、
という文章とはフィットしません。
＞関数 Free の実行時に空きリスト中の組の個数が 2 以上であることが保証される
についてですが、通常関数freeが実行されるときというのは、どこかしらのメモリが使われている状態というのが通常想定されるべき状態です。しかしながら、もし、どこのメモリも使われていなかったとしたら、「空きリスト中の組」はどうなるでしょうか？
空きメモリの組は、{-∞,∞}の一組です。したがって、「空きリスト中の組の個数が 2 以上であることが保証される」は誤りであるといえるわけです。
＞始点1 又は 終点N の値が変わらない限り領域中に"空き"セルが残っている
についてですが、「[空きリストの説明〕」の図でいうところの、1から9のすべてが埋まってしまうことがあるかないかと聞かれています。
これについては、あるので「領域中に"空き"セルが残っている」も誤りであるといえます。
なお、空きセルがない状態の空きリストは「{-∞,-1}{10,∞}」と書き表せます。したがって、空きセルがなくても空きリストがなくなることはないことに注意してください。
＞領域中の一つの連続した"空き"セルが幾ら長くても一つの組で表せる
についてですが、「連続した"空き"セル」というのは、例えば、セル番号0と1が空いている状態です。
この場合の空きリストは{0,1}と書けます。
「一つの連続した"空き"セルが幾ら長くても」というのは、今回の場合は0～9までなので想像がつきにくいと思いますが、
これが0～9999だったとして、0～9000までが連続した空きセルであるなら、空きリストはどのように表せるかということです。
空きセル0～1が{0,1}で書けるのと同じように、空きセル0～9000も{0,9000}と書けます。
これが、「領域中の一つの連続した"空き"セルが幾ら長くても一つの組で表せる」ということです。
しかし、これは-∞や∞を設けなくてもできることです。そのため、
＞このアルゴリズムでは，空きリスト{{始点1，終点1}，{始点2，終点2}，…，{始点N，終点N}}の始点1に値 -∞ を，終点Nに値 +∞ をそれぞれ設定している。このような設定をすることの利点の一つに，**f**という特徴が挙げられる
という文章とはフィットしません。
2021.11.15 12:17
KanaSatoさん(No.5)
＞空きリストが空(組の個数が0)にならない
についてですが、
＞始点1 又は 終点N の値が変わらない限り領域中に"空き"セルが残っている
で解説した通り、セルを使い切っていても、「{-∞,-1}, {10, ∞}」の2個のセルがあります。
この状態のように、-∞, ∞を設けることで、空きリストの組の個数が0にならないようにされているため、正解はアです。
2021.11.15 12:22
初心者さん(No.6)
とても分かりやすかったです！理解できました！
領域外の話や、問題文の「のような設定をすることの利点の一つに，fという特徴が挙げられる。」という部分の理解があいまいでした。より問題文を理解して読み進めるようにしていきます。
本当にありがとうございました。
領域外の話や、問題文の「のような設定をすることの利点の一つに，fという特徴が挙げられる。」という部分の理解があいまいでした。より問題文を理解して読み進めるようにしていきます。
本当にありがとうございました。
2021.11.15 15:05