オリジナル予想問題1 問59

問59

箱の中に1〜20までの数字が書かれたカードがそれぞれ1枚ずつバラバラに入っている。この箱の中からカードを一枚取り出し,"最初に決めておいた任意の数字m(1≦m≦20)でなければ,もう一枚カードを取り出す"という操作を繰り返した場合,数字mが書かれたカードが取り出されたときに,箱から出ているカードの平均枚数は幾つか。

分類

テクノロジ系 » 基礎理論 » 応用数学

正解

解説

期待値と確率を使って解く問題です。

最初に20枚のカードでなく、3枚のカードであると仮定して考えてみます。

カードの総枚数が3枚なので、
  • 1回目で目的のカードを引けると、箱から出ているカードは1枚
  • 2回目で目的のカードを引けると、箱から出ているカードは2枚
  • 3回目で目的のカードを引けると、箱から出ているカードは3枚
となり、それぞれの起こる確率が1/3ずつなので、箱から出ているカード枚数の期待値は、

 (1+2+3)÷3=2

で2枚であることがわかります。

同様にカードの総枚数が20である場合を考えると、
  • 1回目で目的のカードを引けると、箱から出ているカードは1枚
  • 2回目で目的のカードを引けると、箱から出ているカードは2枚
  • 20回目で目的のカードを引けると、箱から出ているカードは20枚
となり、それぞれの起こる確率が1/20ずつなので、箱から出ているカード枚数の期待値は、

 (1+2+…+20)÷20=10.5

で10.5枚であることがわかります。

※この問題は基本情報技術者試験に出題される線形探索法の平均比較回数についての考え方をITパスポート用に書き直してみたものなので、少々難しい問題かもしれません。

線形探索法とは、並びがランダムまたは昇順・降順であるデータの先頭から目的のデータを順番に比較していく方法です。この問題の場合は、中身が見えない箱の中から1枚ずつカードを取り出していく操作を繰り返すので、線形探索法と同様の考え方ができます。
(1+2+…+20)の部分は、(20+1)+(19+2)+(18+3)+…(11+10)と書き直すことができるので、21×10と変換することができます。これを20で割ると

 (21×10)÷20=21÷2=10.5

と、上記と同じ答えにたどりつきます。

一般に線形探索法において、データが1〜nまである場合、目的データが見つかるまでの平均比較回数は、(n+1)/2で表されます。

この問題にこの式を適用した場合 n=20なので、

 (20+1)/2=10.5

というように簡単に答えを求めることができます。

© 2009-2017 ITパスポート試験ドットコム All Rights Reserved.


Pagetop