Математический форум Math Help Planet
Обсуждение и решение задач по математике, физике, химии, экономике Теоретический раздел |
Часовой пояс: UTC + 3 часа [ Летнее время ] |
новый онлайн-сервис число, сумма и дата прописью |
|
Часовой пояс: UTC + 3 часа [ Летнее время ] |
Страница 5 из 6 |
[ Сообщений: 54 ] | На страницу Пред. 1, 2, 3, 4, 5, 6 След. |
|
Автор | Сообщение | |
---|---|---|
swan |
|
|
Shadows писал(а): Но мат. ожидание количества бросков у алгоритм swan намного меньше. Для уменьшения матожидания количества бросков можно еще такую штуку придумать. Например, при [math]n=21[/math], каждому участнику присваивается 3 числа и в итоге у нас будет [math]3\cdot 21=63 = 2^6-1[/math]. И всего за один лишний бросок в туре (6 вместо 5) мы уменьшаем вероятность следующего с 11/32 до 1/64. Для [math]n=100[/math] сразу приходит на ум на 5 умножить. Но сначала лучше на 4 поделить. Вроде так стоить поступать со всеми четными - отсеять группу до нечетного. Желающие могут идею развить, оцифровать и оформить. |
||
Вернуться к началу | ||
За это сообщение пользователю swan "Спасибо" сказали: Shadows |
||
Xmas |
|
|
Смех в том, что точного решения может и не существовать. При нужде, доказательство можно устроить по аналогии с проблемой точности чисел с "плавающей точкой", но нужды пока нет. Даже взять желанную вероятность 1/3 - она и в десятичном представлении тянется бесконечно, и в двоичном тоже.
Но можно всё устроить более-менее прилично - если согласиться, что распределение будет не в точности равномерное, но шансы каждого участника будут отличаться от "абсолютно равномерных" не более, чем на [math]\delta[/math], которую можно выбрать сколь угодно малой. Например, при розыгрыше среди 3 участников, можно сделать: 0,333333333333333 - вероятности выигрыша первого или второго 0,333333333333334 - вероятность выигрыша третьего Схема, если не вдаваться в подробности, - берём монетку, кидаем её несколько раз (чем больше, тем лучше), и из нулей-единиц записываем двоичную дробь: 0.100101101101101... Получим число в интервале [0;1) . Умножаем на число участников. Возникшая целая часть будет номером победителя. Для полноты картины сюда нужно приложить выражение "погрешности" из "разрядности дроби" и числа претендентов, но это по мере надобности. |
||
Вернуться к началу | ||
Shadows |
|
|
Конечно, интересны только нечетные n. (уменньшать вдвое до нечетного). Для [math]n=21[/math] действително уличшается умножением на 3, но всш второй пример [math]n=25[/math] умножение на 5 не дае улучшение:
(вероятность успешной игры - [math]p[/math], мат. ожидание количества игр - [math]\frac 1 p[/math]) [math]E_1=\frac{32}{25}\cdot 5[/math] [math]E_2=\frac{128}{125}\cdot 7[/math] [math]Е_1<Е_2[/math] Для каждого конкретного n - как повезет. |
||
Вернуться к началу | ||
Xmas |
|
|
Shadows, я (видимо) несколько другое имел в виду. Надо было пример приложить.
Есть (скажем) 25 участников Бросаем монетку 10 раз, записываем результат. Пусть получилось 0,1110001110. Оно же, в десятичной форме: [math]\frac{1}{2}+\frac{1}{4}+\frac{1}{8}+\ldots+\frac{1}{128}+\frac{1}{256}+\frac{1}{512}=0.888671875(0\ldots)[/math] (и максимальная погрешность 1/2048 < 0,0005) Умножаем на число участников: [math]0.888671875\cdot25=22.216796875[/math] Округляем вверх (так удобнее, будут получаться числа от 1 до N). Получаем "23" - номер победителя. Было бы участников 11 человек - умножали бы на 11, [math]0.888671875\cdot11=9.775390625[/math], победитель - "10". |
||
Вернуться к началу | ||
Shadows |
|
|
Xmas, я о другом алгоритме писал.
Равновероятность выигрыша для всех участников обязательна по условии. Иначе ваш медод - симулировать более-менее приличный генератор случйных чисел в интервале (0;1) при помощи k битов заложен в компютерных библиотеках. Но это другая задача. |
||
Вернуться к началу | ||
Talanov |
|
|
Генерация случайных чисел равномерного дискретного распределения для n=3 при помощи монеты. Монета бросается два раза. Перевод числа из двоичного кода в десятичный даст 4 числа: 0, 1, 2 и 3. При получении числа 0 (две решки подряд) результат аннулируется.
|
||
Вернуться к началу | ||
За это сообщение пользователю Talanov "Спасибо" сказали: Shadows |
||
Xmas |
|
|
Shadows писал(а): Xmas, я о другом алгоритме писал. Равновероятность выигрыша для всех участников обязательна по условии. Иначе ваш медод - симулировать более-менее приличный генератор случйных чисел в интервале (0;1) при помощи k битов заложен в компютерных библиотеках. Но это другая задача. Такое чувство, что Вы ищете спора, а не решения. Вот, ув. Talanov предложил, по сути, безупречный метод. Чем не устраивает? |
||
Вернуться к началу | ||
Shadows |
|
|
Решение давно найдено, сейчас ищется оптимизация.
Против решения Таланова (последнее) ничего против не имею, я и спасибо сказал. Просто он точь в точь повторил алгоритм swan. |
||
Вернуться к началу | ||
Xmas |
|
|
Shadows писал(а): Конечно, правильных алгоритмов можно придумать много. И все они будут иметь недостак Shadows писал(а): Решение давно найдено, сейчас ищется оптимизация. Не стыкуются тезисы, батенька. |
||
Вернуться к началу | ||
Shadows |
|
|
Почему?
|
||
Вернуться к началу | ||
На страницу Пред. 1, 2, 3, 4, 5, 6 След. | [ Сообщений: 54 ] |
Похожие темы | Автор | Ответы | Просмотры | Последнее сообщение |
---|---|---|---|---|
Определить победителя
в форуме Теория вероятностей |
17 |
507 |
17 июн 2019, 13:58 |
|
2 типа выборки победителя из общего пула
в форуме Комбинаторика и Теория вероятностей |
1 |
279 |
21 апр 2023, 02:54 |
|
Выбор дверей
в форуме Комбинаторика и Теория вероятностей |
4 |
453 |
20 ноя 2018, 21:56 |
|
Выбор без возвращения
в форуме Теория вероятностей |
2 |
214 |
17 май 2017, 12:32 |
|
Выбор метода | 0 |
285 |
24 окт 2015, 15:29 |
|
Выбор с возвращением
в форуме Теория вероятностей |
9 |
739 |
08 окт 2014, 18:02 |
|
Выбор с возвращением
в форуме Теория вероятностей |
1 |
273 |
15 апр 2017, 19:13 |
|
Подбрасывание монеты
в форуме Комбинаторика и Теория вероятностей |
30 |
770 |
13 фев 2022, 18:39 |
|
Бросания монеты
в форуме Теория вероятностей |
6 |
509 |
01 мар 2018, 20:00 |
|
Задача. Монеты | 8 |
529 |
01 мар 2018, 22:07 |
Часовой пояс: UTC + 3 часа [ Летнее время ] |
Кто сейчас на конференции |
Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 32 |
Вы не можете начинать темы Вы не можете отвечать на сообщения Вы не можете редактировать свои сообщения Вы не можете удалять свои сообщения Вы не можете добавлять вложения |