ITパスポート試験 ITパスポート 2015年 (平成27年 秋期) 問48: 表に示す構成のデータを,流れ図の手順で処理する場合について考える。流れ図中のx,y,zをそれぞれデータ区分A,B,Cと適切に対応させれば,比較("xか?","y

問題本文

表に示す構成のデータを,流れ図の手順で処理する場合について考える。流れ図中のx,y,zをそれぞれデータ区分A,B,Cと適切に対応させれば,比較("xか?","yか?","zか?")の回数の合計は,最低何回で済むか。 (流れ図: 開始→「xか?」→Yesでx処理, Noで「yか?」→Yesでy処理, Noで「zか?」→Yesでz処理, Noでその他の処理→「終わりか?」)

選択肢

• ア.170
• イ.190
• ウ.230
• エ.250

正解

ア. 170

解説

比較回数最小化の流れ図問題. 4区分のデータ(A=10件,B=30件,C=50件,その他=10件)を「xか?→yか?→zか?→その他」と3回の判定で振り分ける. 各レコードは「自分の区分」までの比較を通過するため,比較回数の合計を最小化するには「件数が多い区分ほど早く判定する」のがコツ. つまりx=C(50件,1回比較),y=B(30件,2回比較),z=A(10件,3回比較),その他=10件(3回全部通過). 総比較回数=50×1+30×2+10×3+10×3=50+60+30+30=170回となり最小値. これを誤って小件数を先に判定すると比較回数が増える(逆順だと最大値). 「頻度の高いものから判定」が探索効率化の基本原理である.

選択肢ごとの解説

• ア.正解. 件数の多い順に判定すると比較回数が最小化される. C(50件)→1回,B(30件)→2回,A(10件)→3回,その他(10件)→3回を全部通過で,合計=50×1+30×2+10×3+10×3=50+60+30+30=170回. これがx=C,y=B,z=Aと割当てた場合の比較回数最小値となる. 頻度順判定が鍵.
• イ.誤り. 190回はx=B,y=C,z=Aなどの順序で計算した場合の値. 件数50のCを2回目以降の判定にすると,C全件50×2=100回となり,Cを先頭に置く場合の50×1=50よりも比較回数が増えるため,合計が170より大きくなる. 件数多い区分が後回しになると損する典型例.
• ウ.誤り. 230回はx=A,y=B,z=Cなど件数の少ない順に判定した場合に近い値. Aを先頭に置くとAレコード10×1=10だが,C50×3=150と大きな比較回数が発生し合計が増える. 頻度の低い区分を優先判定すると比較回数が増大することの典型的な計算結果である.
• エ.誤り. 250回はx=その他のような不適切な順序で,その他に該当しないレコードも3回の判定をフル通過する場合に近い値. 区分の判定順を頻度逆順あるいは無作為に並べた場合に発生する非効率な総比較回数で,正しい最適配置からは大きく離れた誤った設定の結果.