平成27年(H27)春期 基本情報技術者試験 アルゴリズム問題 解き方解説

平成27年度春期午後のアルゴリズム問題である問8の私の解き方・考え方について解説していきます。

問題

IPAの公式サイトで公開されています。このページでは問8についての解説を行います。

https://www.jitec.ipa.go.jp/1_04hanni_sukiru/mondai_kaitou_2015h27_2/2015h27a_fe_pm_qs.pdf

問題の概要

配列内からn番目に小さい数を探索するアルゴリズムに関する問題です。この問題では特にクイックソートを利用してその探索を行います。

スポンサーリンク

設問1

処理終了後のTopLastの値が問われている問題です。これを解くには与えられた配列を用いて実際にプログラムがどう動いてTopLastがどう変化していくかを追っていく必要があります。

[プログラム]の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以下の数字となり、この時点のijで探索が終わります。ここまでが[プログラム]のオレンジ枠と緑枠の動きとなります。

続いてx[i]x[j]の値の交換を行います。

これが[プログラム]の赤枠の処理になります。さらにこの後にiを1増やし、jを1減らします。

ここまでが[プログラム]の9〜24行目の処理の流れです。これをij以上になるまで続けられます。

[プログラム]の9〜24行目の2巡目の処理が完了すると下記のような状態になります。

つまり、iが6、jが5となります。次のループではオレンジ枠・緑枠ともに一度もif文が成立しません。さらにこの時ij以上となっていますので、[プログラム]の9〜24行目のループを17行目のbreakにより抜け出します。

ループを抜け出すと、[プログラム]の25〜30行目が実行され、TopLastの値が更新されます。

i ≦ k は不成立、k ≦ j は成立ですので、Topは1のままとなり、Lastが5に更新されます。ですので[   a   ]の答えは「Topに値1、Lastに値5」となります。

 

続いてはこの更新された配列x[ ]TopLastに基づいてもう一度[プログラム]の9〜24行目のループ処理が実行されます。ループ開始時の状態は下記のような感じです。jLastから始まるので探索範囲が狭まったことになります。

ループ1巡目が完了した時点だと各変数の様子は下記のようになります。

この時点でijも2となります。次のループ時にはオレンジ枠のif文は一度も成立しませんが、緑枠側はx[2]が1より大きいためjが1に更新されます。さらに、ij以上になったので[プログラム]の9〜24行目のループを抜け、TopLastの更新処理が実行されます。

今回はi ≦ k が成立、k ≦ j は不成立ですので、Lastは5のままとなり、Topが2に更新されます。ですので[   b   ]の答えは「Topに値2、Lastに値5」となります。

設問2

設問2も与えられた配列を実際に入力した時の動きを追っていくしかないと思います。ただしプログラムの考え方は設問1と全く同じです。

γ部分が実行された後の結果をここで示します。設問1でプログラムの動きについては説明していますので、ここでは説明は割愛します。

・αの1回目

 γの1回目終了後

 γの2回目終了後

 γの3回目終了後

ここでiがj以上となるのでループ終了。Topは1、Lastは4に更新される。

・αの2回目

 γの4回目終了後

ここでij以上となるのでループ終了。Topは4、Lastは2に更新される。TopLastを上回るのでSelect関数は終了。

以上より、αは2回、γは4回実行されます。ですので、[   c   ]の答えは2[   d   ]の答えは4となります。

設問3

うーん、これも実際に配列入力した時の動きを見るのが良さそうですね。同じことばっかりやっていい加減疲れてきましたが・・・。

・「1,1,1,1,1,1」の場合

これは分かりやすいですね。[プログラム]の9〜24行目のオレンジ枠部分でx[i]Pivot以上かという判断が全て成立してしまうので配列外にまでアクセスしてしまいます。

ですので[   e   ]の答えは「配列の範囲を越えて参照する」となります。

・「1,3,2,4,2,2」の場合

こちらはγ後の各変数の状態がどう変更していくかを見ていってみましょう。

 γの1回目終了後

 γの2回目終了後

 γの3回目終了後

 γの4回目終了後

γ終了後の状態が3回目と4回目で全く同じですね。つまり5回目以降のγ終了後も同じ結果になると考えられ、ずっとTopLastの値を上回らないので無限ループになってしまいます。

ですので[   f   ]の答えは「処理が終了しない」となります。

スポンサーリンク

解いてみた感想

うーん、何度も同じことやらされたので疲れました。これぞアルゴリズム問題!といった感じなのでしょうか。

なぜこのアルゴリズムで数値の探索ができているかもわからなかったのですが、とにかくプログラムを実際に動かして考えてみることでなんとか正解を導くことができました。ただアルゴリズムの意味がよく分かってないので自信持った回答できないところが辛いところですね。それでもプログラムさえ追うことができれば解けてしまうのがアルゴリズム問題のいいところなのかもしれませんが。

本ページの図・プログラム・問題文について

図やプログラム、問題文はIPA公開の過去問題から引用しています。また図やプログラムに関しては説明に必要な部分に関してのみ加工して使用させていただいております。

出典:平成27年度 春期 基本情報技術者試験(FE)試験区分 午後 問8

コメントを残す

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