Python-сообщество

Помогите написать на Питоне программу, решающую задачу. Если что, я довольно неплохо понимаю её математику и уже решил её упрощённый вариант на Java. Но хотелось бы посмотреть, как она решается на Питоне, с его возможностями функционального программирования. Как я понимаю, они будут особенно полезны. Решение на Джаве пока не даю, потому что не хочу сковывать вас рамками решения в императивном стиле. Но если возникнут вопросы чисто по математике задачи - конечно, опубликую.

Собственно задача. На полигоне расположены несколько ОБВМ. У каждого из них некое количество единиц здоровья и некий боезапас. Числа не важны и могут выбираться случайно. Каждый из ОБВМ стреляет по очереди. Жертва выбирается случайно. Промахов не бывает. Каждый выстрел уменьшает на единицу боезапас выстрелившего и здоровье того, в кого выстрелили. Когда боезапас кончается у всех, игра останавливается. Побеждает тот из оставшихся в живых ОБВМ, у кого больше здоровья (видимо, потому что победит в рукопашной). Требуется вычислить вероятность победы для каждого из ОБВМ (или хотя бы для одного заранее выбранного, тогда можно будет просто зациклить алгоритм, но что-то мне подсказывает, что можно решить за один раз).

Условие не понятно:
1 Вы точно хотите посчитать вероятности?
2 В дохлых роботов стреляют?
3 Сами дохлые роботы стреляют?
4 Робот в себя тоже может выстрелить?
5 что означает аббревиатура ОБВМ?

Отредактировано (Янв. 28, 2012 10:40:12)

doza_and
Условие не понятно:
1 Вы точно хотите посчитать вероятности?

Да, именно так. Причём в идеале - всех возможных исходов сражения. То есть результатом должна быть двумерная таблица N*N, где N - количество роботов. Соответственно, в ячейке - вероятность того, что i-ый робот займёт j-ое место в сражении.

2 В дохлых роботов стреляют?
3 Сами дохлые роботы стреляют?
4 Робот в себя тоже может выстрелить?

Нет на все вопросы.

5 что означает аббревиатура ОБВМ?

Ой, оговорка по Фрейду. Я имел в виду ОБЧР (Огромные Боевые Человекоподобные Роботы). А ОБВМ - это… lurkmore.to/ОБВМ

Решил переформулировать задачу более ясно и строго. Есть несколько не зависящих друг от друга устройств, для каждого известна вероятность выхода из строя. Выяснить, каковы вероятности того, что устройства будут выходит из строя в том или ином порядке. Таким образом, результатом работы программы может быть, например, двумерный массив размерностью N*N, где N - количество устройств, а в каждой ячейке - вероятность того, что i-ое устройство сломается j-ым по счёту. Я решаю сейчас эту задачу на императивном языке (Java), но получается коряво и неудобочитаемо. Уверен, что функциональное программирование подходит лучше.

Объясню принцип алгоритма. Пусть у нас три устройства, вероятности поломки каждого из них соответственно 37%, 43% и 20%. Сколько существует вариантов развития событий? Очевидно, 3! = 6.

Вариант 1. Последовательность выхода из строя: 1, 2, 3. Вероятность того, что сначала выйдет из строя первое устройство, равна 37/(37+43+20) = 0.37. Потом должно выйти из строя второе. Так как первое уже вышло из строя, то вероятность выхода из строя второго равна 43/(43+20) = 0,68. Вероятность того, что третьим выйдет из строя третье, равна 20/20 = 1. Вполне логично, ведь первые два уже вышли из строя, больше выходить нечему. Вероятность самой этой последовательности = 0.37*0.68*1 = 0.25.

2. Последовательность 1, 3, 2. Считаем точно так же, получаем 0.37; 0.32; 1. Вероятность = 0.12;

3. Последовательность 2, 1, 3. Вероятности поломок 0.43; 0.65; 1. Вероятность варианта = 0.28;

4. Последовательность 2, 3, 1. Вероятности поломок 0.43; 0.35; 1. Вероятность варианта = 0.15;

5. Последовательность 3, 1, 2. Вероятности поломок 0.2; 0.46; 1. Вероятность варианта = 0.09;

6. Последовательность 3, 2, 1. Вероятности поломок 0.2; 0.54; 1. Вероятность варианта = 0.11.

Отмечу, что сумма вероятностей всех вариантов = 0.25 + 0.12 + 0.28 + 0.15 + 0.09 + 0.11 = 1.0.
А теперь можно получить искомую таблицу, ячейку за ячейкой. Например, нас интересует, какова вероятность того, что второе устройство сломается вторым по счёту. Такое возможно в вариантах 1 и 6. Вероятность вариантов 0.25 и 0.11, вероятности интересующего нас события в каждом из вариантов - 0.68 и 0.54 соответственно. Таким образом, искомая вероятность = 0.25 * 0.68 + 0.11 * 0.54 = 0.23.

Меня не оставляет ощущение, что алгоритм неоправданно громоздкий, можно как-то сделать гораздо проще и лучше. По идее, должна получится одна рекурсивная функция, которая сразу строит искомый массив, а не две процедуры, одна из которых строит трёхмерный массив последовательностей, а вторая ищет подходящие последовательности и строит двухмерный массив устройство * очередность поломки.

Если есть функция, которая генерирует последовательности(варианты) и их вероятности, то построить таблицу легко.
Изначально таблица заполнена нулями.
Далее, для каждой последовательности надо к предыдущему значению в нужных ячейках прибавлять вероятность текущей последовательности.
Вероятность события в варианте не имеет смысла - условная вероятность всегда 1. Например, второе устройство сломается вторым с вероятностью 0.25 + 0.11, т.е. 0.36, а не 0.23. Что оно сломается первым и третьим - 0.43 и 0.21 соответственно. В сумме 1.0.

agalen
Если есть функция, которая генерирует последовательности(варианты) и их вероятности, то построить таблицу легко.
Изначально таблица заполнена нулями.
Далее, для каждой последовательности надо к предыдущему значению в нужных ячейках прибавлять вероятность текущей последовательности.
Вероятность события в варианте не имеет смысла - условная вероятность всегда 1. Например, второе устройство сломается вторым с вероятностью 0.25 + 0.11, т.е. 0.36, а не 0.23. Что оно сломается первым и третьим - 0.43 и 0.21 соответственно. В сумме 1.0.

Это гениально! Я понимал, что где-то перемудрил, но не думал, что в таких базовых вещах. Я считал, что неплохо знаю тервер…