平成27年度 秋期 ITパスポート試験 公開問題 問48 解説 流れ図の比較回数

この問題は、効率的な条件分岐の順序を導き出す計算問題です。合計の比較回数を最小にするには、件数が多いものから順に判定を行います。

手順は以下の通りです。

1. データごとの件数を確認する：A=10, B=30, C=50, その他=10（合計100件）
2. 件数の多い順に判定を割り当てる：1番目（50件）にC、2番目（30件）にB、3番目（10件）にAを割り当てる。
3. 各判定に必要な回数を算出する：
   • Cの場合：1回の比較で終了（50件×1回 = 50回）
   • Bの場合：CでNo、次にBでYesとなるため2回の比較（30件×2回 = 60回）
   • Aの場合：CでNo、BでNo、次にAでYesとなるため3回の比較（10件×3回 = 30回）
   • その他の場合：CでNo、BでNo、AでNoの計3回の比較（10件×3回 = 30回）
4. 合計を計算する：$50 + 60 + 30 + 30 = 170$回

効率的なアルゴリズムの考え方

この問題の本質は、コンピュータが処理を行う際の「コスト」を意識することにあります。コンピュータは命令を1つずつ実行するため、条件分岐が多いプログラムでは、頻繁に発生する条件を先にチェックすることで、平均的な処理時間を短縮できます。

日常生活に例えると、これは「よく使う道具を一番手前に置く」整理整頓の考え方に似ています。もし、最も頻繁に使う道具を一番奥に置いていたら、毎回引き出しを全部開ける手間が発生しますよね。プログラムにおいても、処理回数が多いデータを早い段階で特定することで、不要な判定回数を削減し、システム全体のパフォーマンスを向上させることができます。

実務における重要性

この知識は、大規模なデータを扱うシステム開発やデータ処理の最適化で非常に重要です。例えば、膨大な顧客リストから特定の属性を持つユーザーを検索する際、検索条件の順序を頻度の高い順に並べるだけで、検索のレスポンスが改善することがあります。

特に、Webサイトの閲覧履歴からユーザーの嗜好を分析したり、在庫管理システムで品目ごとの出庫処理を行ったりする場面では、このような「出現頻度に基づいた条件分岐」はアルゴリズムの基本として重宝されます。効率のよいプログラムは、ただ動くというだけでなく、ハードウェアの負荷を抑え、ユーザーを待たせないという付加価値を生むのです。

参考リンク

• ITパスポート試験対策サイト - 探索の効率化
• Qiita - プログラムの実行速度を改善するアルゴリズムの基礎
• 情報処理学会 - 計算量理論とアルゴリズムの定義