Как приблизиться к этому вопросу об алгоритме?
- Веб-сайт имеет базу данных n вопросов.
- Вы нажимаете кнопку и показаны один случайный вопрос на щелчок. Вероятность конкретного вопроса, обнаруживающегося в событии щелчка, является 1/n.
В среднем, сколько щелчков потребовалось бы, чтобы видеть все вопросы в базе данных?
Что подход требуется для таких вопросов?
3 ответа
Почему бы нам не запустить симуляцию и не выяснить?
<?php
function simulate($size) {
$range = range(1, $size);
$hits = 0;
$hit = array();
while(count($hit) != $size) {
$rand = array_rand($range);
$hit[$rand] = 1;
$hits++;
}
return $hits;
}
for ($j=10; $j<101; $j+=10) {
$res = array();
for ($i=0; $i<10; $i++) {
$res[] = simulate($j);
}
echo "for size=$j, avg=" . array_sum($res)/10 . "<br />";
}
Выход:
for size=10, avg=35.9
for size=20, avg=68.8
for size=30, avg=123.3
for size=40, avg=176.9
for size=50, avg=205.9
for size=60, avg=276.8
for size=70, avg=304.9
for size=80, avg=401.9
for size=90, avg=371
for size=100, avg=617.7
Это скорее математический вопрос, чем алгоритмический. Как сказал sdcvvc, это знаменитая проблема сборщика купонов.
Предположим, у вас есть n вопросов, которые нужно "собрать". Пусть X - случайная переменная, обозначающая необходимое количество кликов. Если мы определим Xi как количество кликов с момента, когда у нас есть (i-1) вопросов до момента, когда у нас есть i вопросов, то:
X = X1 + X2 + ... + Xn
В силу линейности ожидаемого значения:
E(X) = E(X1 + X2 + ... + Xn) = EX1 + EX2 + ... + EXn
Если мы проверим Xi, то увидим, что на самом деле оно имеет геометрическое распределение с p=(n-i+1)/n, следовательно, среднее значение равно n/(n-i+1). Поэтому:
EX = n * (1/n + 1/(n-1) + ... + 1/2 + 1/1) = n * Hn
Где Hn - n-ое гармоническое число, которое можно аппроксимировать через ln n:
EX ~= n * ln n
Вы можете провести простую симуляцию и проверить это приближение.