従業員番号と氏名の対が n 件格納されている表に線形探索法を用いて，与えら
れた従業員番号から氏名を検索する。この処理における平均比較回数を求める式
はどれか。ここで，検索する従業員番号はランダムに出現し，探索は常に表の先頭
から行う。また，与えられた従業員番号がこの表に存在しない確率を a とする。
ア n + 1 na
─── + ──
2 2
イ (n + 1)(1 - a)
────────
2
ウ (n + 1)(1 - a) n
──────── + ─
2 2
エ (n + 1)(1 - a)
──────── + na
2
■キーワード■ 線形探索法
■解答■
ソフトウェア開発技術者午前平成２０年秋問１２
エ (n + 1)(1 - a)
──────── + na
2
> 解き方が全く分かりません．．．。ボケたか？
宿題メールは，苦手なところを見つけるというのが目的の一つです。
解説で確認しておいてください。
300件あって，その中に従業員番号がない確率を，1/5 として，100回調べると
100回のうち，4/5は存在し，1/5は存在しないことになります。
頭から順に調べる場合，必ずあるとすると，平均比較回数は，半分です。
見つかるとき， 80回。比較回数は，300/2 = 150 比較。
見つからないときは，20回。比較回数は，300 比較(見つからないときは全てみるから)
100回調べると，
150比較が，80回
300比較が，20回
よって，平均は，
150*80 + 300*20 / 100 比較
= 150*(1 - 20/100) + 300*(20/100)
n/2*(1-a) * na
これと似た式は，エ。
違いは，n/2 が，(n+1)/2 となっていることです。頭から順に比較するときに，
見つかる位置は，正確には，n/2 でなくて，(n+1)/2 ということでしょう。
- 1 にはほとんど意味はありません。1万件データがあったときに，必ずあるとき
の比較回数が，平均，5000 か5000.5 の違いです。
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
- -
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
