Вопрос 14 из 25

Практика: методы алгоритмов: углубление

Резервуарная выборка: как один слот остаётся равномерным

От чтения к действию

А теперь — вы

В слоте выбран элемент на третьем шаге. Поток завершился после пятого. Какова вероятность, что он переживёт следующие два шага?

Разберёмся в теме

Чтобы равномерно выбрать одну позицию из потока неизвестной длины, сохраняют первый элемент, а элемент с номером i принимает его место с вероятностью 1/i. После n шагов каждая из n позиций находится в слоте с вероятностью 1/n.

Объяснение и примеры

Частые вопросы

Где найти подробное решение?

Перейдите по ссылке «Объяснение и примеры» над этим блоком. Там разобрана тема текущего вопроса.

Можно ли попробовать снова?

Да. После проверки можно изменить ответ. Переход к следующему вопросу не блокируется результатом, а личный счёт не сохраняется.