「分かりそう」で「分からない」でも「分かった」気になれるIT用語辞典

予備知識

問題

問題文
表に示す構成のデータを，流れ図の手順で処理する場合について考える。流れ図中のx，y，zをそれぞれデータ区分A，B，Cと適切に対応させれば，比較("xか?"，"yか?"，"zか?")の回数の合計は，最低何回で済むか。
ピヨ意訳：以下の流れ図の通りに処理するよ。 データ区分A、B、Cは、流れ図にあるx、y、zのどれかだよ。 つまり、可能性としては １．A→x、B→y、C→z ２．A→x、B→z、C→y ３．A→y、B→x、C→z ４．A→y、B→z、C→x ５．A→z、B→x、C→y ６．A→z、B→y、C→x の6パターンが考えられるよ。 データ区分A、B、Cとx、y、zの対応によって「xか?」「yか?」「zか?」の比較回数が変わるんだけど、一番比較回数が少なくなる組み合わせのとき、比較回数は全部で何回？

正解

ピヨピヨ解説

問題文がクソですね。
何を聞きたいのかが分かりにくいです。

問題文で聞いているのは「xか?」「yか?」「zか?」の比較回数が最も少なくなるデータ区分A、B、Cとx、y、zの対応……のときの比較回数です。

データ区分A、B、Cは流れ図にあるx、y、zのどれかです。
組み合わせの可能性としては

１．A→x、B→y、C→z
２．A→x、B→z、C→y
３．A→y、B→x、C→z
４．A→y、B→z、C→x
５．A→z、B→x、C→y
６．A→z、B→y、C→x

の6パターンが考えられます。

仮に組み合わせが

１．A→x、B→y、C→z

だったとしましょう。

その場合

■データ区分「A」のデータを処理
　「xか?」の比較を10回やる

■データ区分「B」のデータを処理
　「xか?」の比較を30回やる
　「yか?」の比較を30回やる

■データ区分「C」のデータを処理
　「xか?」の比較を50回やる
　「yか?」の比較を50回やる
　「zか?」の比較を50回やる

■データ区分「その他」の処理
　「xか?」の比較を10回やる
　「yか?」の比較を10回やる
　「zか?」の比較を10回やる

になるので、比較回数は全部で

10＋30×2＋50×3＋10×3＝250回

です。

データ区分A、B、Cとx、y、zの対応によって比較回数は変わります。
それじゃあ、一番比較回数が少なくなる組み合わせのとき、比較回数は全部で何回ですか？という問題です。

それを踏まえて、本題に入ります。

地道に全部計算していっても良いのですが、手を抜きましょう。

データが「x」の場合、比較は「xか?」の1回で済みます。
データが「y」の場合、比較は「xか?」「yか?」の2回発生します。
データが「z」の場合、比較は「xか?」「yか?」「zか?」の3回必要です。

つまり、できるだけ多くのデータが「x」の方が比較回数は少なくて済むわけです。

ということは、1番件数の多いデータ区分「C」が「x」で2番目に件数の多いデータ区分「B」が「y」のときに比較回数が一番少なくなります。
組み合わせとしては

６．A→z、B→y、C→x

の場合です。

あとは比較回数を計算するだけです。

■データ区分「C」のデータを処理
　「xか?」の比較を50回やる

■データ区分「B」のデータを処理
　「xか?」の比較を30回やる
　「yか?」の比較を30回やる

■データ区分「A」のデータを処理
　「xか?」の比較を10回やる
　「yか?」の比較を10回やる
　「zか?」の比較を10回やる

■データ区分「その他」の処理
　「xか?」の比較を10回やる
　「yか?」の比較を10回やる
　「zか?」の比較を10回やる

になるので、比較回数は全部で

50＋30×2＋10×3＋10×3＝170回

です。

ということで「ア：170」が正解です。