平成25年度秋期 ITストラテジスト 午前Ⅰ 問3

交換回数の追跡で見る基準

この種の問題では、処理の各段階で状態がどう変わったかを順に記録し、回数として扱う出来事の定義を途中で変えないことが重要です。全体の印象ではなく、観測単位をそろえて確認しましょう。

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

確認する観点は、数え上げの対象となる一回の出来事をどの時点で記録しているかです。処理前後の状態を見比べ、同じ基準で各段階を追えているかだけに集中してください。途中で別の操作と混同していないかも点検します。

視点

手順を読むときは、変化が起きた箇所を時系列に並べ、記録する単位を固定して整理します。個々の値の増減よりも、観察の基準が一貫しているかを優先して確認してください。

確認ポイント

• 回数として記録する対象を、最初に自分の言葉で定めたか
• 各段階の前後で状態を記録し、記録漏れを作っていないか
• 途中で別の操作や比較結果を回数に混ぜていないか

正解

ウ

解説

流れ図は、後ろの要素から前へ向かって隣接要素を比較する処理を繰り返します。各外側ループで交換回数を数えると、4回、3回、1回、0回、0回となり、合計は8回です。

理由

初期配列21，5，53，71，3，17に対し、外側ループごとの交換回数は順に4回、3回、1回、0回、0回です。したがって、入替え回数は 4＋3＋1＋0＋0＝8回となります。

比較

この問題では、隣接要素を比較した回数そのものではなく、a[j−1]＞a[j]が成立して実際に値を入れ替えた回数を数えます。成立しない比較は交換回数に含めません。

選択肢ア

これは不正解だよ。外側ループごとに条件 a[j−1]＞a[j] が成立した隣接対を追跡すると、交換回数は4回、3回、1回、0回、0回となる。3回では、初回の処理で小さい値を前方へ移す交換などを取りこぼしている。

選択肢イ

これは不正解だよ。全ての外側ループを終えるまでの交換回数は、各回の4回、3回、1回、0回、0回を合計して8回である。6回という数は、条件が成立する交換を二つ分少なく数えており、流れ図全体の処理結果と一致しない。

選択肢ウ（正解）

これは正解だよ。外側ループごとの交換回数を順に数えると、4回、3回、1回、0回、0回となる。よって、a[j−1]とa[j]の値を入れ替える回数は、4＋3＋1＋0＋0＝8回である。

選択肢エ

これは不正解だよ。15回は、n＝6のときに二重ループで隣接要素を比較する総回数である。しかし、比較しても大小条件が成立しない場合は入替えを行わないため、比較回数15回を交換回数として数えることはできない。

学習のポイント

隣接交換型の整列では、比較回数と実際の交換回数を区別して追跡することが重要です。