Задать вопрос

Как решить эту задачу по теории вероятности?

Не смог найти решение, сам решить не в состоянии.

Представим такую ситуацию. В правой руке я держу стопку экзаменационных работ. На каждой проставлен номер билета, от 1 до n. Порядок - случайный. В левой руке у меня пачка этих билетов, тоже n штук, но уже разложенных по порядку. Для проверки экзаменационной работы я достаю из правой пачки случайную работу и по порядку перелистываю билеты в левой пачке пока не найду нужный номер. На следующей итерации я опять должен перелистать билеты с этой позиции, пока не найду нужный, и так до конца. Вопрос: сколько в среднем перелистываний надо совершить для проверки всей пачки? Интерес чисто математический. Переход от перелистывания к например бинарному поиску уменьшит число перелистываний, но принципиально не изменит его зависимость от n.
  • Вопрос задан
  • 2751 просмотр
Подписаться 3 Оценить 9 комментариев
Решения вопроса 1
icelaba
@icelaba
Знаю и умею всё
Решение:
Среднее колво перелистываний до первого билета равно (N-1)/2
Cреднее число перелистываний между двумя равномерно распределенными билетами на отрезке 1..N равно (N-1)/3,
всего после первого перелистывания отсается ровно (N-1) таких пар

Итого среднее число всего перелистываний:
(N-1)/2 + (N-1)*(N-1)/3
Что и является ответом.

Максимум дан в моем предыдущем ответе, он подходит и даже после уточнения условий.
Ответ написан
Пригласить эксперта
Ответы на вопрос 2
icelaba
@icelaba
Знаю и умею всё
Так как условие не полно, а именно не указано изымается ли билет из пачки, да и правила листания тоже нечеткие
то считаю что он остается - имею право :-), а листаю сверху
до каждого билета с номером k надо листать (k-1) раз - просуммировать от Сумма(k= 1 до N, (k-1)) = (N-1)*N/2
Ответ написан
Комментировать
Я бы предположил, что для Вашего вопроса ответ N*N/2, а для бинарного поиска N*log2(N)
Ответ написан
Комментировать
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Похожие вопросы