平成31年度春期 プロジェクトマネージャ 午前Ⅰ 問3

処理回数を整理する考え方

処理回数を考えるときは、操作を数える単位と、入力全体を一度に扱うのか段階ごとに分けるのかを先に整理し、与えられた条件との対応を丁寧に確認しましょう。数える基準を途中で変えないことも重要です。

この問題で問われていること

注目する観点を、各段階で何を一回の処理として数えるかに絞りましょう。数え始める前に対象範囲と繰り返しの区切りをそろえると、見落としや重複を避けやすくなります。全体の基準を保って確認します。

視点

処理回数は、対象・区切り・数える操作の定義をそろえてから整理します。段階をまたぐときも、同じ基準で記録できているかを確認することが大切です。

確認ポイント

• 一回として数える操作の単位を確認する
• 処理を区切る段階や範囲を整理する
• 同じ操作を重複して数えていないか見直す

正解

ア

解説

データ数9から初期の間隔Hを求めると3になります。Hが3の段階で部分列を整列し、その後Hを1へ更新します。Hが1の段階でも整列した後、更新によってHが0になるため、手順(3)の繰返し回数は2回です。

理由

データ数は9なので、最初のHは［9÷3］=3です。1回目の手順(2)を終えると、手順(3)でHは［3÷3］=1になります。2回目の手順(2)の後、手順(3)でHは［1÷3］=0となり、手順(4)で終了します。したがって手順(3)は2回繰り返します。

比較

数える対象はHの値そのものではなく、手順(3)を実行した回数です。H=0になった後は手順(2)へ戻らないため、終了判定だけの段階を整列回数に加えてはいけません。

選択肢ア（正解）

これは正解だよ。データ数9から初期値H=［9÷3］=3を求め、H=3で整列した後に手順(3)を実行するとH=［3÷3］=1になります。H=1で再び整列した後、手順(3)でH=［1÷3］=0となるため、手順(3)の実行回数は2回です。

選択肢イ

これは不正解だよ。Hは3から1へ、さらに0へ更新されますが、手順(3)を実行するのはその更新の2回です。Hが0になった後は手順(4)で完了するため、終了判定の段階を追加の1回として数えることはできません。

選択肢ウ

これは不正解だよ。初期値H=3、次の値H=1、その次にH=0となる流れは、手順(3)を2回実行した時点で完了します。Hの異なる値を三つ数えても、その値の個数は手順(3)の実行回数とは一致しません。

選択肢エ

これは不正解だよ。手順(3)では毎回Hを3で割って小数点以下を切り捨てます。H=3から1、H=1から0の2回で終了するため、さらに整列処理や間隔更新を続ける前提は手順(4)の終了条件と合いません。

学習のポイント

シェルソートの間隔列と、整列処理の回数を正しく対応させる。