Re: Программа


Автор сообщения: Roger
Дата и время сообщения: 25 October 2004 at 20:12:38:

В ответ на сообщение: Еще один алгоритм и вопрос Roger'у и просьба

> Roger'у -а не расскажете как считали матожидание? Можно по почте. vpapkov песик mteb.ru

Для начала, я посчитал мат. ожидание того дня, когда в карцер впервые сядет один из M разбойников (размер шайки - N). Выглядит сложно, но получается просто - N/M (если надо, могу рассказать как получить). Для водилы мат. ожидание попасть в каталажку равно N дней (M=1).

Отсюда, если осталось M неподсчитанных (и знающих, что они неподсчитаны) разбойников, мат. ожидание времени отсидки равно
N/M + N + N/(M-1) + N + N/(M-2) + N + ... + N/2 + N + N/1 + N

Для модифицированного варианта я считал вероятность того, что на начальном (1..K) этапе первый "рецидивист" окажется в карцере в определённый день. Для второго дня она равна 1/N, для третьего - ((N-1)/N)*(1/N), для четвёртого - ((N-1)/N)*((N-2)/N)*(2/N) и так далее. Эта вероятность домножается на мат. ожидание подсчёта с водилой при соответственно уменьшенном количестве тех, кого необходимо подсчитать - естественно, к времени отсидки прибавляется K. Если все K дней разбойники не повторялись, водилой становится тот, кто приходит в карцер в день (K+1) - при этом теряется один день, но с вероятностью (N-K)/N число тех, кого нужно считать, уменьшается на 1 (что даёт выигрыш N/(N-K) + N дней).

Оптимальное K определял перебором.

А здесь текст программы (извините, без комментариев), которая печатает табличку из 38680.html.


1811. Mihael'ю еще одна задачка! - Заметил-Просто 11:14 21.10.04 (61)
К списку тем на странице