Что нового
  • Что бы вступить в ряды "Принятый кодер" Вам нужно:
    Написать 10 полезных сообщений или тем и Получить 10 симпатий.
    Для того кто не хочет терять время,может пожертвовать средства для поддержки сервеса, и вступить в ряды VIP на месяц, дополнительная информация в лс.

  • Пользаватели которые будут спамить, уходят в бан без предупреждения. Спам сообщения определяется администрацией и модератором.

  • Гость, Что бы Вы хотели увидеть на нашем Форуме? Изложить свои идеи и пожелания по улучшению форума Вы можете поделиться с нами здесь. ----> Перейдите сюда
  • Все пользователи не прошедшие проверку электронной почты будут заблокированы. Все вопросы с разблокировкой обращайтесь по адресу электронной почте : info@guardianelinks.com . Не пришло сообщение о проверке или о сбросе также сообщите нам.

Построить Алгоритм Выбора Случайного Элемента Из Последовательности, Чтобы Каждый Элемент...

Sascha

Заместитель Администратора
Команда форума
Администратор
Регистрация
9 Май 2015
Сообщения
1,071
Баллы
155
Возраст
51
Пусть у нас есть некоторая конечная последовательность чисел и мы имеем итератор, указывающий на первый элемент. Мы можем при помощи итератора посмотреть значение текущего элемента и перейти к следующему элементу. Требуется построить такой алгоритм выбора случайного элемента из этой последовательности, чтобы каждый элемент мог оказаться выбранным с равной вероятностью.

Ограничения: мы можем использовать O(1) дополнительной памяти и не можем создавать новый итератор. Можно пользоваться функцией генерации случайного числа от [0;1).

Решение:


Создадим некоторую переменную, обозначим ее — x. Будем идти по последовательности и по ходу хранить номер элемента последовательности. Пусть мы сейчас находимся на элементе номер i, нумерация с 1. С вероятностью 1/i присвоим переменной x значение текущего элемента. Чтобы сделать действие с вероятностью p можем сгенерировать случайное число в диапазоне [0;1) и если сгенерированное число меньше p, то делаем действие, иначе не делаем.

Почему это работает?


Осталось доказать несложное утверждение: в переменной x после выполненных действий может оказаться любой элемент последовательности равновероятно, то есть каждый с вероятностью 1/n, где n число элементов последовательности.

Доказательство:


Будем доказывать по индукции. Для n=1 утверждение очевидно. Предположим, что утверждение верно для n=k, докажем его для n=k+1. После того, как мы выполним указанные действия для k первых элементов в переменной x находится одно из k чисел равновероятно, то есть с вероятностью 1/k каждое, по предположению индукции. После обработки (k+1)-го элемента вероятность того что в переменной x находится (k+1)-й элемент — 1/(k+1). Следовательно, вероятность того что в переменной x находится не (k+1)-й элемент — k/(k+1), а поскольку все k первых элементов были сохранены в переменной x равновероятно до обработки (k+1)-го элемента, то вероятность появления в переменной x любого из первых k элементов 1/(k+1). Таким образом утверждение доказано.

Если вам понравилась эта задачка, возможно, вам также понравится:

  • Вы должны выбрать одну из двух ставок. При первом варианте вы должны забросить баскетбольный мяч в корзину. Если попадёте, то получите 50 тыс. рублей. Во втором варианте вам надо попасть два раза из трёх бросков, и тогда вы также получите те же 50 тыс. рублей. Какой из этих вариантов вы предпочтёте?

    Пожалуйста Авторизируйтесь или Зарегистрируйтесь для просмотра скрытого текста.



Пожалуйста Авторизируйтесь или Зарегистрируйтесь для просмотра скрытого текста.

.
 
Вверх