本文へスキップ

平成27年度 秋期 ITパスポート試験 問48

この問題の解説と、これまでの解答の記録です。

問48
頻出度★★☆

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

データ区分件数
A10
B30
C50
その他10

流れ図:「開始」→「xか?」(No→「yか?」,Yes→「xの処理」);「yか?」(No→「zか?」,Yes→「yの処理」);「zか?」(No→「その他の処理」,Yes→「zの処理」);各処理後→「終わりか?」(No→「次のデータ」へ戻る,Yes→「終了」)。注記:流れ図中のx,y,zはデータ区分のA,B,Cのいずれかと対応させる。

出典 平成27年度 秋期 ITパスポート試験 問48
解説

問 48逐次判定の流れ図では、上流の条件ほど比較回数が少ない

  • ア

    正解 流れ図では各データを「xか?」→(No なら)「yか?」→(No なら)「zか?」の順に判定するので、比較回数は x に該当すれば1回、y なら2回、z なら3回、どれにも該当しない「その他」は3回すべて実行する。合計を最小にするには、件数の多い区分ほど早い段階(少ない比較回数)で処理すればよい。件数は C=50 が最多、次いで B=30、A=10 なので、x=C、y=B、z=A と対応させるのが最適。すると C:50×1=50、B:30×2=60、A:10×3=30、その他:10×3=30 で、合計 50+60+30+30=170 回。よって最低回数は170、正解はア。

  • 不正解イ

    190 は x=C、y=A、z=B のような対応(50×1+10×2+30×3+その他10×3=190)で得られる値で、件数の多い B を z(3回)に回しているため最小ではない。設問は「最低何回」を問うので不適。

  • 不正解ウ

    230 は x=B、y=A、z=C のような対応(30×1+10×2+50×3+その他10×3=230)で得られる値。最多件数の C を z(3回)に置いており、最小どころか大きい部類の回数となるため不適。

  • 不正解エ

    250 は x=A、y=B、z=C とした場合(10×1+30×2+50×3+その他10×3=250)の値で、件数の少ない区分ほど早く判定するという最悪の対応。これは最大回数であり、最低回数を問う本問の答えにはならない。

ここがポイント
  • 逐次判定の流れ図では、上流の条件ほど比較回数が少ない。合計比較回数を最小化するには「件数の多いデータ区分を早い判定(少ない比較回数)に割り当てる」のが定石。
  • 各区分の比較回数=到達までに実行する判定の数(x=1回、y=2回、z=3回、その他=3回)を件数と掛けて総和を取る、という重み付き合計の考え方。
用語

解答の記録