Задача
Тема создана 11 марта 2010 года в 12:59
gabber |
Есть набор из N элементов. Они расположены подряд от первого до N-ого. Т.е. это какой-то список элементов. Вопрос, как с одинаковой вероятностью выбрать один элемент за один проход?
Когда я говорю одинаковая вероятность я имею ввиду что распределение должно быть равномерное по элементам. Т.е. вероятность выбрать каждый элемент должна быть 1/N. Когда я гвоорю за один порход, я имею ввиду что я двигаюсь с первого до последнего и я не знаю в самом начале сколько элементов. Т.е. их может быть миллион, может 5 миллинов, а может и вобще миллиард, но что точно известно что их много. Но когда я встречу последний я буду об этом знать что больше элементов нет. Тут некоторые считают что они могут запомнить один миллиард элементов, так вот это сделать нельзя. Т.е. ответ что я пройду по всем элементам и их посчитаю, а потом выберу один не правильный потому что в задаче сказано что большое кол-во элементов и его запомнить не возможно. А тот кто может запомнить миллион элементов пусть решает для миллиарда. Запомнить например 100 элементов впринципе я думаю реально - но надо продемострировать эту возможность. Кто может запомнить 10 - придется пользоваться только 10-ю 
Если вы считаете что нет решения, то надо об этом прямо написать и доказать Я в ответ через 24 часа пришлю решение.
А еще, в вашем распоряжении есть функция которая выдает случайное число, с равномерным распределнием в заданом диапазоне. Нормальное распределение и равномерное разные вещи. ru.wikipedia.org/… ru.wikipedia.org/… А и еще, человек без памяти вобще, задачу решить наверно не сможет. Еще пояснение, можно запомнить один элемент и сказать вот я его выбрал и сидеть смотреть на элементы дальше, а потом взять и скзаать нет я все же выберу другой элемент. Так можно передумывать неограниченое число раз. Элемент надо назвать в самом конце когда все посмотришь. Ладно еще подсказака для тех кто не знает теорию вероятности и математику, хоть это и следует из наличия ф-ии. Можно сказать что я выбираю элемент с такой-то вероятностью. Если я говорю например, я беру элемент с вероятностью 11% это значит что если я сделаю этот тест 100 раз - 11 раз я элемент выбиру, а 89 нет. |
в ЧС
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
 Поднять (1 голосов)
 Опустить (1 голосов)
Рейтинг темы: 3.00 из 5
Проголосовало: 2 человек
(для консилиума не хватает 2 человек)
|
Просмотров: 505
 |
В случае обнаружения ошибок и прочих неприятностей, просим, без стеснения, сообщать.
OpenSource исходтики сайта на github.
Сделано без задней мысли Данилом Письменным по бурной инициативе Антона Подлесного.
OpenSource исходтики сайта на github.
Сделано без задней мысли Данилом Письменным по бурной инициативе Антона Подлесного.
