アルゴリズムとプログラミング (全23問中12問目)
No.12
表に示す構成のデータを，流れ図の手順で処理する場合について考える。流れ図中のx，y，zをそれぞれデータ区分A，B，Cと適切に対応させれば，比較("xか?"，"yか?"，"zか?")の回数の合計は，最低何回で済むか。
出典：平成27年秋期 問48
- 170
- 190
- 230
- 250
分類
テクノロジ系 » アルゴリズムとプログラミング » アルゴリズムとプログラミング
正解
ア
解説
設問の流れ図では1件ごとに以下の処理が行われています。
処理の流れを見ると、どのデータ区分に属するかによって比較回数が異なり、x は1回、y は2回、z とその他は3回の比較が行われることに気が付きます。これをもとにデータ区分とx, y, zの対応を考えると、件数が多いデータ区分を比較回数の少ないものに、件数の少ないデータ区分には何回も比較するものを対応させることで総比較回数を最少化できることがわかります。
つまりデータ件数が50件と最も多い C を x に、続いて30件である B を y に、最も少ない10件の A を z に対応させると比較回数を最も少なくできることになります。
このケースでは、比較回数1回の x のデータ区分が50件、比較回数2回の y のデータ区分が30件、比較回数3回の zとその他 のデータ区分が(10＋10=)20件となるので、
50×1＋30×2＋20×3＝170
最も少ない比較回数は170回です。
- まず「xか?」の比較を行い、データ区分が x であれば x の処理を行う。
- データ区分が x でなければ「yか?」の比較を行い、データ区分が y であれば y の処理を行う。
- データ区分が x, y のどちらでもなければ「zか?」の比較を行い、データ区分が z であれば z の処理を行う。
- どれにも該当しなかったデータに関してはその他の処理を行う。
つまりデータ件数が50件と最も多い C を x に、続いて30件である B を y に、最も少ない10件の A を z に対応させると比較回数を最も少なくできることになります。
このケースでは、比較回数1回の x のデータ区分が50件、比較回数2回の y のデータ区分が30件、比較回数3回の zとその他 のデータ区分が(10＋10=)20件となるので、
50×1＋30×2＋20×3＝170
最も少ない比較回数は170回です。