[0097] アルゴリズム 比較回数

平成12年度秋期 (旧)第2情報処理技術者試験より
 売上ファイルのレコードの項目の一つに処理区分があり、この処理区分に応じた処理をしたい。全売上データに対する各処理区分の出現比率はあらかじめ分かっている。処理区分を判定するための比較回数に関する記述のうち、適切なものはどれか。
出現比率が中間の処理区分のものを先に判定すると、全体の比較回数が少なくなる。
出現比率が最も大きい処理区分から先に判定すると、全体の比較回数が少なくなる。
出現比率が最も小さい処理区分から先に判定すると、全体の比較回数が少なくなる。
どのような順番でも全体の比較回数は同じである。

正解

解説

 アルゴリズムの高速化に関する問題です。

 問題文の処理を流れ図で記述してみましょう。


※処理区分、および処理区分ごとに行なう処理については問題文中で明記されていないので、処理区分A、B、Cとして表記した。


 この問題を解くポイントは、上図のオレンジ色の破線で囲まれた処理部です。繰り返し構造で、売上ファイルからデータを読み込み、処理区分ごとに処理を行なっています。

 処理区分 = A の判定処理で、処理区分が A以外の場合は、下の処理区分Bの判定処理に入ります。処理区分Bの判定処理で、処理区分がBでもない場合は、さらに下の処理区分Cの判定処理に入ります。

 処理区分Cの判定処理まできてしまった場合は、A、Bと合わせて合計3回の比較を行なうことになります。したがって、コンピュータの処理量を減らす、すなわち、比較回数を少なくするためには、出現比率の高い処理区分の判定処理をできるだけ早く行なうことが重要です。

 したがって、イが正解となります。
※ 解説の内容は執筆時点のものであり,含まれている情報の正確性,妥当性について保証するものではありません。ご注意ください・・・

関連する(かもしれない)問題