平成26年度 春期 午前 問6

✓ これが正解エ(n＋1)(1－a)/2 ＋ na

解説

見つかる場合と見つからない場合を確率で足します。

設問は、線形探索で従業員番号から氏名を探すときの平均比較回数を表す式を選ばせています。期待値を求める問題ですから、場合を分けて、それぞれの回数に確率の重みを付けて足し合わせます。表にある確率は 1 から a を引いた値、表に無い確率は a です。表にあるときは、先頭で当たれば 1 回、二番目なら 2 回、最後まで進めば n 回で、どこにあるかは等しく起こりますから、平均は 1 から n までの総和を n で割った n＋1 の半分になります。表に無いときは、最後の一件まで比べて初めて無いと分かるので、必ず n 回で固定です。重みを付けて足すと、n＋1 の半分に 1－a を掛けたものに na を加えた式が残ります。端の値でも確かめられます。a が 0、つまり必ずある場合は n＋1 の半分になり、a が 1、つまり必ず無い場合は n になって、どちらも場合分けの値と一致します。

ほかの選択肢はなぜ違うのか

• ア(n＋1)/2 ＋ na/2：あるときの回数に 1－a という重みを掛け忘れ、無いときを na の半分と置いた形です。a を 1 にすると n を超えてしまい、件数より多く比べることになります。
• イ(n＋1)(1－a)/2：無いときを表す項が欠けています。a を 1 にすると 0 回になり、一度も比べないうちに無いと分かることになってしまいます。
• ウ(n＋1)(1－a)/2 ＋ n/2：無いときを n の半分と置き、しかもその確率 a を掛けていません。半分だけ調べた時点で無いと断定できる探索は存在しません。