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

表のデータを流れ図で処理する問題【ITパスポート 解説】

正解の理由

解法ステップ

1. 流れ図の各分岐での比較回数を確認する。
   • x に該当するデータ：比較 1 回で判定（x? が Yes）
   • y に該当するデータ：比較 2 回で判定（x? No → y? Yes）
   • z に該当するデータ：比較 3 回で判定（x? No → y? No → z? Yes）
   • その他のデータ：x,y,z 全て No → 比較 3 回で「その他の処理」へ
2. 各データ区分の件数に応じた重み付き和を考える。比較回数の合計は次の式で表せる。 $$\text{合計比較回数}=1\cdot f(x)+2\cdot f(y)+3\cdot f(z)+3\cdot f(\text{その他})$$ ここで $f(\cdot )$ は各区分の件数。
3. 右辺の定数部分 $3\cdot f(\text{その他})$ は固定（今回 10 件で 30 回）なので、可変部分 $1\cdot f(x)+2\cdot f(y)+3\cdot f(z)$ を最小化する。
   大きい件数には小さい係数（先にチェックする位置）を割り当てるのが最適（貪欲法的な直感）。
4. 頻度順に並べると C(50) > B(30) > A(10)。したがって x=C, y=B, z=A とすると、
   可変部分 = $1\times 50+2\times 30+3\times 10=50+60+30=140$。
   その他の固定分 30 を足して合計 170 回になる。

選択肢別の誤答解説

• ア: 170
  上述の割り当て（x=C, y=B, z=A）で得られる値。最小値であり正解です（ア）。
• イ: 190
  これは例えば不適切な割り当て（例：x=B, y=C, z=A）などで計算すると出る値です。頻度の高い C を先にチェックしないため余分な比較が発生します。
• ウ: 230
  さらに悪い順序（例：x=A, y=B, z=C）で、高頻度の C が最後に回るため比較回数が大きくなります。
• エ: 250
  最も非効率な割り当ての一つで、頻度の大小をまったく考慮していない結果です。

よくある誤解

1. 「その他は比較回数に入らない」と考える誤り
   → 「その他」に分類されるデータは x,y,z のいずれにも該当しないため、x?、y?、z? の3回の比較が必要になります。今回の「その他」10件は必ず3回ずつ比較されます。
2. 「順番を変えても合計は同じ」と思う誤り
   → 順序によって各カテゴリが受ける比較回数（1回・2回・3回）が変わるため合計は変わります。高頻度の項目を前に持ってくるほど合計は小さくなります。

補足コラム

• 最適な順序決定は「頻度の高いものを先にチェックする」という単純なルールで決まります。これは「期待比較回数の最小化」という観点で直感的に正しい方法です。
• この考え方は、検索や条件分岐での効率化全般に使えます。例えばよく使うメニュー項目をメニューの上位に置く、検索フィルタを頻度順に適用するなど、日常の設計にも応用できます。

import itertools

freq = {'A':10, 'B':30, 'C':50, 'その他':10}
best = None
for perm in itertools.permutations(['A','B','C']):  # perm = (x,y,z)
    total = 1*freq[perm[0]] + 2*freq[perm[1]] + 3*freq[perm[2]] + 3*freq['その他']
    if best is None or total < best[0]:
        best = (total, perm)
best  # (170, ('C','B','A'))

FAQ