慶應SFC 総合政策学部 情報入試 2019年 大問Ⅴ 過去問解説

この問題には4つの解が存在する。

解1

(ア)

まずだが、これは
・等しいならば「到達不可能」と出力する
・途中で更新されている
ことから
i番目の配置の集合
であると分かる。
したがっては{s}である。

処理Aが始まった段階ではiが1増えたばかりで今の配置は分かっていない。
したがってを空集合とする。(※1)
そしての各要素に対して次に動かしたときにどうなるか処理を行う。(※2)

の候補はの各要素である。

途中で変数の値をとすればよい。

にはi番目の配置の集合が入っているから、これが空集合となった場合は到達不可能である。(※3)

(イ)
Zはすでに探索した配置の集合。
2回以上探索しないようにZを用いたアルゴリズムを組み込んでいる。

(ウ)
gに到達可能なsから始めた場合は、処理Cでq=gになることはあるから、時間はかかるかもしれないが正しい結果は得られる。
gに到達不可能なsから始めた場合は、に必ずqを追加してしまうから、が空集合にならず無限に繰り返し実行される。(※4)

解2

解1の※1でを{s}としても解1は成り立つ。
その場合、※3も{s}となった場合としなくてはいけない。
なぜなら、は{s}であり、Zの存在によりi≧1の場合のにs以外の既に探索したものが入ることはないからである。

解3

解1の※1でとしても解1は成り立つ。
その場合、※3もとなった場合としなくてはいけない。
理由は解2と同じ。
そしてこのとき、※4が変わる。
gに到達不可能なsから始めた場合でも、Zの存在により以前のものしか入っていなかったら、もう変更は不可能だと判断できる。
よって時間はかかるかもしれないが正しい結果は得られる。

解4

解3の場合で、※2を
そしての各要素に対してどうなっているか処理を行う
としても解3は成り立つ。
にはあらかじめが入っているにすぎない、と見做せるからである。

AO入試・小論文に関するご相談・10日間無料添削はこちらから

「AO入試、どうしたらいいか分からない……」「小論文、添削してくれる人がいない……」という方は、こちらからご相談ください。
(毎日学習会の代表林が相談対応させていただきます!)









コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です