Нужен эмулятор следующей ситуации:
В корзине лежит Y шаров, X из которых белого цвета.
Игрок наугад вытаскивает N шаров.
Требуется определить сколько белых шаров игрок вытащил.
Что-то я уперся в стенку никак не найду подходящую формулу расчета
может быть кто-нибудь сталкивался с подобной задачей?
Неактивен
ASBer написал:
В корзине лежит Y шаров, X из которых белого цвета.
Игрок наугад вытаскивает N шаров.
Требуется определить сколько белых шаров игрок вытащил.
Хм. Это не к теории вероятностей. Это простые дроби.
Соотношение в среднем не меняется.
M - число вытащенных белых шаров
X/Y = M/N, следовательно, M = N * X/Y
Домашнее задание делаешь?
Неактивен
2 fireton: дробями решается только в случае равномерного распределения камней.
2 Korwin: мне нужна техническая реализация. желательно на с, но и basic тоже устроит.
Неактивен
пример: в корзине 10 камней, из них 3 белых.
как примерно должно быть:
1 попытка 3 камня - вытащено 0 белых, осталось 7 камней, из них 3 белых. //не повезло
2 попытка 1 камень - вытащен 1 белый, осталось 6 камней, из них 2 белых. //повезло
3 попытка 3 камня - вытащено 2 белый, осталось 3 камней, из них 0 белых. //повезло
при повторении каждый раз должна быть другая последовательность вытащенных камней.
для одного камня вероятность определяется простым соотношением белых камней к камням в корзине.
можно конечно сделать цикл от 1 до N и таскать камни по одному, но некрасиво...
Неактивен
дробями решается только в случае равномерного распределения камней.
Ну, ты же не указал распределение вероятности. По умолчанию - всегда нормальное.
Неактивен
ASBer написал:
...
2 Korwin: мне нужна техническая реализация. желательно на с, но и basic тоже устроит.
Соглашусь, если это имеет отношение к ИФ. В противном случае - злостный флейм.
Неактивен
2 Korwin: к ИФ отношение непосредственное - решение нужно для реализации рандома на моей ИФ платформе.
Неактивен
ASBer :
при повторении каждый раз должна быть другая последовательность вытащенных камней.
для одного камня вероятность определяется простым соотношением белых камней к камням в корзине.
можно конечно сделать цикл от 1 до N и таскать камни по одному, но некрасиво...
Я бы сделал так:
#include <stdio.h> #include <stdlib.h> #include <time.h> int takeWhiteCount( int takeTotal, int m, int n ) { int res = 0; int i; for ( i = 0; i < takeTotal; i++ ) { if ( (rand() % n) < m ) { res++; m--; } n--; } return res; } int main() { int takeTotal, m = 5, n = 10; printf("Сколько шаров вы хотите взять: "); scanf("%d", &takeTotal); srand( (unsigned)time(NULL) ); printf("Вытащено белых шаров: %d\n", takeWhiteCount(takeTotal, m, n)); return 0; }
Неактивен
2 tadsloser: спасибо за содействие
Взял Ваше решение в качестве временного чернового варианта.
Только ограничил takeTotal<=100, т.к. при takeTotal=1000000 даже современные компы зависают на недопустимо длительное время.
И всеже очень надеюсь что существуют решения без использования циклов.
Отредактировано ASBer (12.02.2008 19:21)
Неактивен
Дроби неслучайны.
Мне же по сути нужен генератор случайных чисел с 3мя параметрами и вышеописанным принципом действия
Код tadsloser-а абсолютно точно решает поставленную задачу, но к сожалению неоптимален.
Отредактировано ASBer (12.02.2008 20:10)
Неактивен
ASBer написал:
Только ограничил takeTotal<=100, т.к. при takeTotal=1000000 даже современные компы зависают на недопустимо длительное время.
И всеже очень надеюсь что существуют решения без использования циклов.
Не знаю даже, у меня при takeTotal = 10^7 (m=10^7 и n=2*10^7) за секунду посчитал (реультат = 5011437).
Только, если тебе нужны такие порядки, то в takeWhiteCount() функцию rand() нужно заменить на следующую:
int bigrand() { return RAND_MAX*rand() + rand(); }
А поповоду "формульного" решения не знаю, я в математике, в том числе в ТВ, не силен. Можно спросить на мат. форумах (в случае ответа не забудь отписаться
З.Ы.
В каком контексте возникли эти замечательные монохромные шары? Возможно, ты решаешь немного не ту задачу.
З.З.Ы
Очень не советую браться за написание своей платформы.
Отредактировано tadsloser (19.03.2008 00:45)
Неактивен
tadsloser написал:
Не знаю даже, у меня при takeTotal = 10^7 (m=10^7 и n=2*10^7) за секунду посчитал (реультат = 5011437).
Только, если тебе нужны такие порядки...
Ну вообщето не нужны это я из-за любви к чистому искусству. Для практических целей takeTotal=100 более чем достаточно.
tadsloser написал:
А поповоду "формульного" решения не знаю, я в математике, в том числе в ТВ, не силен. Можно спросить на мат. форумах (в случае ответа не забудь отписаться
Если в этом топике "формульного" решение никто не предложит, оставлю до лучших времен как есть Ну не так уж я и люблю это самое искусство...
tadsloser написал:
З.Ы.
В каком контексте возникли эти замечательные монохромные шары? Возможно, ты решаешь немного не ту задачу.
Задача про корзину с монохромными шарами родилась как наиболее наглядно описывающая требующийся алгоритм.
На самом деле мне просто необходим удобный механизм управления шансами.
Вот пара примеров применения:
1. Случайные взаимосвязанные события.
Допустим в какой-то момент времени могут случайно произойти события А, Б, С.
Заряжаем корзину шарами и начинаем последовательно проверять шансы для каждого события.
Свершившееся событие снижает шанc для последующих событий, не свершившееся событие наоборот этот шанс увеличивает. При этом все пересчеты шансов происходят автоматически.
2. Расчет повреждения от удара (или размер полученной награды..).
В зависимости от различных параметров накидываем в корзину белые и черные шары.
Тянем N шаров, получаем размер повреждения (или награды).
Отредактировано ASBer (13.02.2008 10:19)
Неактивен
Dimouse написал:
Если N<<X+Y, то тут биномиальное распределение.
Прошу простить за темность, но хотелось бы формулу вычисления бинома, или алгоритм в идеальном случае.
Неактивен
Функция плотности вероятности p(k)=n!/(n-k)!/k! p^k q^(n-k)
где p=X/(X+Y) - вероятность вытащить белый шар, q=1-p. Это действует в случае независимых событий только, т.е. число белых шаров мало уменьшается в ходе опыта.
Чтобы узнать сколько белых шаров вытащено можно действовать по Монте-Карло - написать функцию распределения F(k) (интеграл p(k)) и разыгрывая случайно число от 0 до 1 считать k=f(rand), где f - обратная функция к F.
В случае дискретного распределения все это по-моему страшный гемморой, так что видимо не стоит так считать.
P.S. В случае n>>1 будет нормальное распределение.
P.P.S. Конечно в данном случае такое решение есть бред и стрельба по воробьям из пушки, но в сложных задачках это универсальный метод решения на компьютере.
Неактивен
Dimouse написал:
Функция плотности вероятности p(k)=n!/(n-k)!/k! p^k q^(n-k)
Спасибо! постараюсь осмыслить.
Неактивен