平成31年度春期 情報処理安全確保支援士 午前Ⅰ 問3

午前I 問03

データが9個あるので、最初のHは「9を3で割って小数を切り捨てる」から `⌊9÷3⌋=3` だよ。そこから手順(3)に従って、Hを `⌊3÷3⌋=1`、さらに `⌊1÷3⌋=0` と更新していく。Hが0になったら終了、という流れを順番に追えばOKだよ。

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

この問題では、アルゴリズムの手順を上から順にたどって、Hが何回更新されるかを落ち着いて数えられるかがポイントだよ。Hを「次の作業間隔を決める目盛り」みたいに考えて、3、1、0と小さくなっていく様子を追っていこう。

Shell Sort Gap Sequence

H starts at 3 and is updated to 1 then 0

initial H = 3\nstep(3): 3 -> 1\nstep(3): 1 -> 0

確認ポイント

• データの並び替え回数ではありません。
• `H` の更新回数だけを数える。
• 2 回で完了する。

正解

ア

出典

問題文と解答は IPA 公開の過去問題冊子・解答例を基にしています。

選択肢ア（正解）

正解だよ。公式のアは「2回」。データは9個なので、最初に H=[9÷3]=3。手順(3)で H=[3÷3]=1 になり、まだ0じゃないからもう一周。次の手順(3)で H=[1÷3]=0 になって終了。つまり手順(3)は2回だけ。階段を3段幅で降りて、次に1段幅で降りたら地面に着く、みたいなイメージだよ。

選択肢イ

不正解だよ。公式のイは「3回」だけど、実際は H が 3→1→0 と変わるので、手順(3)は2回で終わるよ。3回目まで数えるのは、もう店じまいした窓口にもう一度並びに行くようなもので、0になった時点で処理は終了なんだ。

選択肢ウ

不正解だよ。公式のウは「4回」だけど、そこまで繰り返さないよ。H は毎回3で割って小数点以下を切り捨てるので、3の次は1、1の次は0。0になったら終了だから、4回も手順(3)を実行する余地はないんだ。

選択肢エ

不正解だよ。公式のエは「5回」だけど、これは明らかに多すぎるよ。シェルソートでは間隔Hをだんだん小さくして、最後にHが0になったら終わり。この問題では H=3 と H=1 の2段階だけ確認すればよく、5回もぐるぐる回る必要はないよ。