ITパスポート 2015年 秋期 問48

最少比較回数【ITパスポート解説】

正解の理由

解法ステップ

1. フローチャートの判断順を確認する。ここでは順に「xか? → yか? → zか?」で、見つかればその時点で処理を行う（比較回数はその位置の回数）。「その他」は最後の“No”で到達するため比較は3回。
2. 各区分の件数を整理する：A=10、B=30、C=50、その他=10（その他は固定で3回）。
3. 重み付きの比較回数を最小にするため、比較回数の小さい位置（1回目→2回目→3回目）に出現頻度の大きい区分を置く。つまり件数の多い順に並べる（降順）。
4. 並べ方を決めて合計を計算する：最適は C(1回), B(2回), A(3回)。合計170と求まる。

選択肢別の誤答解説

• ア相当（170） — 最適
  並び: x=C, y=B, z=A
  計算: C:1×50=50, B:2×30=60, A:3×10=30, その他:3×10=30 → 合計170
  これが最小になります。
• イ（190）
  例1 並び: x=C, y=A, z=B
  計算: C:1×50=50, A:2×10=20, B:3×30=90, その他:30 → 合計190
  例2 並び: x=B, y=C, z=A
  計算: B:1×30=30, C:2×50=100, A:3×10=30, その他:30 → 合計190
  どちらも頻度順に並んでいないため、アより大きくなります。
• ウ（230）
  例1 並び: x=B, y=A, z=C
  計算: B:1×30=30, A:2×10=20, C:3×50=150, その他:30 → 合計230
  例2 並び: x=A, y=C, z=B
  計算: A:1×10=10, C:2×50=100, B:3×30=90, その他:30 → 合計230
  いずれも最頻値（C）を後ろに置いているため不利です。
• エ（250）
  並び: x=A, y=B, z=C
  計算: A:1×10=10, B:2×30=60, C:3×50=150, その他:30 → 合計250
  最も出現が多いCを最後にすると最大値になります。

よくある誤解

• 「その他」は4回目の比較が必要だと思う誤り
  実際は zの判断で“No”になった直後にその他の処理へ行くため、比較は3回で済みます。4回と誤認すると合計が過大になります。
• 頻度が多いものを後ろに置く誤り
  出現頻度の高いものほど前に置く（比較回数を小さくする）ことで全体が小さくなります。
• 単純に件数の大きさだけ見るが、計算を確認しない
  並べ替えの効果を確かめるために必ず「比較回数×件数」の和を出して確認しましょう。

補足コラム

FAQ