平成２７年度春期午後のアルゴリズム問題である問８の私の解き方・考え方について解説していきます。
問題
IPAの公式サイトで公開されています。このページでは問８についての解説を行います。
https://www.jitec.ipa.go.jp/1_04hanni_sukiru/mondai_kaitou_2015h27_2/2015h27a_fe_pm_qs.pdf
問題の概要
配列内からn番目に小さい数を探索するアルゴリズムに関する問題です。この問題では特にクイックソートを利用してその探索を行います。
スポンサーリンク
設問１
処理終了後のTopとLastの値が問われている問題です。これを解くには与えられた配列を用いて実際にプログラムがどう動いてTopとLastがどう変化していくかを追っていく必要があります。
[プログラム]の9〜24行目はこんな感じの動きになっています。各色枠の動きを頭に入れておきましょう。
それではSelect関数の動きを追っていきましょう。
まずSelect関数スタート時の配列x[ ]や変数i、変数jは下記のようになっています。Pivotはピンクで示した6です。
この状態からx[i]が6以上の値が見つかるまでiを右方向に移動させながら探索、x[i]が6以下の値が見つかるまでjを左方向に移動させながら探索を行います。
iに関してはx[3]が初めての6以下の数字であり、jに関してはx[7]が初めての6以下の数字となり、この時点のiとjで探索が終わります。ここまでが[プログラム]のオレンジ枠と緑枠の動きとなります。
続いてx[i]とx[j]の値の交換を行います。
これが[プログラム]の赤枠の処理になります。さらにこの後にiを1増やし、jを1減らします。
ここまでが[プログラム]の9〜24行目の処理の流れです。これをiがj以上になるまで続けられます。
[プログラム]の9〜24行目の２巡目の処理が完了すると下記のような状態になります。
つまり、iが6、jが5となります。次のループではオレンジ枠・緑枠ともに一度もif文が成立しません。さらにこの時iがj以上となっていますので、[プログラム]の9〜24行目のループを17行目のbreakにより抜け出します。
ループを抜け出すと、[プログラム]の25〜30行目が実行され、TopとLastの値が更新されます。
i ≦ k は不成立、k ≦ j は成立ですので、Topは1のままとなり、Lastが5に更新されます。ですので[ a ]の答えは「Topに値1、Lastに値5」となります。
続いてはこの更新された配列x[ ]とTop、Lastに基づいてもう一度[プログラム]の9〜24行目のループ処理が実行されます。ループ開始時の状態は下記のような感じです。jはLastから始まるので探索範囲が狭まったことになります。
ループ１巡目が完了した時点だと各変数の様子は下記のようになります。
この時点でiもjも2となります。次のループ時にはオレンジ枠のif文は一度も成立しませんが、緑枠側はx[2]が1より大きいためjが1に更新されます。さらに、iがj以上になったので[プログラム]の9〜24行目のループを抜け、TopとLastの更新処理が実行されます。
今回はi ≦ k が成立、k ≦ j は不成立ですので、Lastは5のままとなり、Topが2に更新されます。ですので[ b ]の答えは「Topに値2、Lastに値5」となります。
設問２
設問２も与えられた配列を実際に入力した時の動きを追っていくしかないと思います。ただしプログラムの考え方は設問１と全く同じです。
γ部分が実行された後の結果をここで示します。設問１でプログラムの動きについては説明していますので、ここでは説明は割愛します。
・αの１回目
γの１回目終了後
γの２回目終了後
γの３回目終了後
ここでiがj以上となるのでループ終了。Topは1、Lastは4に更新される。
・αの２回目
γの４回目終了後
ここでiがj以上となるのでループ終了。Topは4、Lastは2に更新される。TopがLastを上回るのでSelect関数は終了。
以上より、αは２回、γは４回実行されます。ですので、[ c ]の答えは2、[ d ]の答えは4となります。
設問３
うーん、これも実際に配列入力した時の動きを見るのが良さそうですね。同じことばっかりやっていい加減疲れてきましたが・・・。
・「1，1，1，1，1，1」の場合
これは分かりやすいですね。[プログラム]の9〜24行目のオレンジ枠部分でx[i]がPivot以上かという判断が全て成立してしまうので配列外にまでアクセスしてしまいます。
ですので[ e ]の答えは「配列の範囲を越えて参照する」となります。
・「1，3，2，4，2，2」の場合
こちらはγ後の各変数の状態がどう変更していくかを見ていってみましょう。
γの１回目終了後
γの２回目終了後
γの３回目終了後
γの４回目終了後
γ終了後の状態が３回目と４回目で全く同じですね。つまり５回目以降のγ終了後も同じ結果になると考えられ、ずっとTopがLastの値を上回らないので無限ループになってしまいます。
ですので[ f ]の答えは「処理が終了しない」となります。
スポンサーリンク
解いてみた感想
うーん、何度も同じことやらされたので疲れました。これぞアルゴリズム問題！といった感じなのでしょうか。
なぜこのアルゴリズムで数値の探索ができているかもわからなかったのですが、とにかくプログラムを実際に動かして考えてみることでなんとか正解を導くことができました。ただアルゴリズムの意味がよく分かってないので自信持った回答できないところが辛いところですね。それでもプログラムさえ追うことができれば解けてしまうのがアルゴリズム問題のいいところなのかもしれませんが。
★オススメページ★
下記ページから他の回の解説もたどれます。他の回のアルゴリズム問題の解き方がわからない場合は是非読んでみてください！
基本情報技術者試験 午後問題「アルゴリズム」過去問の解き方 解説 まとめ本ページの図・プログラム・問題文について
図やプログラム、問題文はIPA公開の過去問題から引用しています。また図やプログラムに関しては説明に必要な部分に関してのみ加工して使用させていただいております。
出典：平成２７年度 春期 基本情報技術者試験（FE）試験区分 午後 問８
