кроссворды, задачки, головоломки

Сборник задач разного уровня сложности по математике, информатике, физике, химии, программированию, экономике etc. Логические задачи, SQL задачи, решение задач. Задачи с ответами, а также нерешённые задачи.

Petruchek.Info

Функция, возвращающая случайный элемент из потока неизвестной длины

Добавлено: 18.03.08 в 09:35
Метки: информатика

Есть некий поток элементов. Вызывая снова и снова функцию getnext(), вы получаете каждый раз следующий элемент из потока, и так до тех пор, пока функция не вернет EOF, что означает, что поток закончился. Гарантировано, что все элементы, полученные таким образом, будут отличаться друг от друга. Вернуться к началу потока, или получать элементы в каком-то другом порядке, кроме как один за другим с помощью getnext(), невозможно.

Известно, что поток когда-нибудь кончается, но заранее про количество элементов ничего не известно.

Требуется: написать функцию, которая, когда ее вызывают (а вызывают ее один раз), возвращает выбранный случайным образом один из элементов потока, притом у каждого из элементов потока одинаковая вероятность быть возвращенным этой функцией.

Функция должна использовать фиксированное количество памяти (иными словами, O(1) памяти).

СПРЯТАТЬ РЕШЕНИЕ/ОТВЕТ

Перебираем весь поток по одному, параллельно храним кандидата (значение, которое мы собираемся вернуть) в переменной $result.

Каждый новый претендент может побить кандидата с вероятностью 1/m, где m - количество претендентов, уже прочитанных из потока.

Схема-код решения (на php):

function getrandom()
{
$m 0//thread counter
$result null//candidate to return
while ($current getnext())
    {
    
$m++;
    if ( 
1/$m >= random() ) //check if pretendent wins candidate
        
$result $current
    }
return 
$result;
}


N.B. random() — несуществующая в php функция, возвращающая случайное действительное число из интервала [0,1]
источник

Комментарии
Google says:
Комментарий от новенького:
Новенький является
Новенький не робот
Знаки на картинке: латинские буквы, арабские цифры


Есть на сайте: Онлайн кроссворды Задачи Онлайн игры Блог
Все работы, опубликованные на сайте — авторские, если не указано иное. Перепечатка возможна только с письменного разрешения владельцев ресурса, с обязательной ссылкой на сайт petruchek.info. Пишите нам: . Сайт должен работать в IE, FF, Opera, Safari.

Реклама:

Разработано в студии "Webous"о проектесайта карта

Реклама: