Динамическое программирование

@motya65100 · Регистрация: 18.09.2021

Студворк — интернет-сервис помощи студентам

Две команды проводят серию игр до 10 побед одной из команд. Первая команда
побеждает вторую с вероятностью 3/5. Возможна ничья с вероятностью 1/10. Найти
вероятность, что при счете 2:2 первая команда победит вторую в серии игр.

Подскажите чего не хватает пожалуйста и что подправить.

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
import random
 
firstTeamWins = 0
secondTeamWins = 0
Counts = 10000
for i in range(0, Counts):
    firstTeam = 2
    secondTeam = 2
 
flag = True
while flag:
    if random.randint(3, 5) == 1:
        secondTeam += 1
else:
    firstTeam += 1
    if firstTeam==10 or secondTeam==10:
        flag = False;
    if firstTeam == 10:
        firstTeamWins+=1
    else:
        secondTeamWins+=1
 
 
    if (firstTeamWins>=secondTeamWins):
        out = firstTeamWins/Counts
        print("firstTeamWin:")
        print(out)
    else:
        out = secondTeamWins/Counts
        print("secondTeamWin:")
        print(out)

@anton78spb · 21.12.2022, 20:11

Сообщение от motya65100

Найти
вероятность, что при счете 2:2 первая команда победит вторую в серии игр.

Так у вас же в условии уже есть ответ.

Сообщение от motya65100

Первая команда
побеждает вторую с вероятностью 3/5.

Счет 2:2, т.е. по сути они начинают "с нуля". Соответственно вероятность победы первой команды в серии 3/5, или 60%.

@motya65100 · 21.12.2022, 20:24 **[ТС]**

И правда, даже не подумал об этом, но все равно надо как-то решение оформить кодом

@anton78spb · 21.12.2022, 20:41

motya65100, Эмпирически получается примерно 71% вероятность выигрыша первой команды.

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
from random import randint
 
n = 10000
 
s = 0
 
for _ in range(n):
    w1 = 0
    w2 = 0
    for _ in range(6):
        r = randint(1, 10)
        if r < 7:
            w1 += 1
        if r > 7:
            w2 += 1
    if w1 > w2:
        s += 1
        
print(s / n * 100)

@motya65100 · 21.12.2022, 20:48 **[ТС]**

А почему именно 6 в for _ in range(6)???

Добавлено через 3 минуты
и эту строку объясни пожалуйста r = randint(1, 10)

@anton78spb · 21.12.2022, 20:52

Сообщение от motya65100

А почему именно 6 в for _ in range(6)???

Серия из 10 игр. Счет 2:2, т.е. четыре уже сыграли. Соответственно осталось 6.

Сообщение от motya65100

и эту строку объясни пожалуйста r = randint(1, 10)

Случайное число от 1 до 10 включительно.

@motya65100 · 21.12.2022, 21:03 **[ТС]**

Всё понял, огромное тебе спасибо!

Добавлено через 9 минут
anton78spb, если в сокетах разбираетесь, отпишите в лс пожалуйста, одну функцию не могу сделать

@Red white socks · 21.12.2022, 22:17

Сообщение от anton78spb

Счет 2:2, т.е. по сути они начинают "с нуля". Соответственно вероятность победы первой команды в серии 3/5, или 60%.

Это распространенное заблуждение.
Вероятность выигрыша более мастеровитого игрока в серии увеличивается с ростом длины серии.

Добавлено через 15 минут
И судя по названию темы, требовалось точное решение.
Оно находится с помощью рекуррентной формулы:

Code
1
m(p,q)= 10/9*(m(p-1,q)*3/5 + m(p,q-1)*1/2)

@anton78spb · 21.12.2022, 22:18

Red white socks, Вы правы.
К сожалению, сейчас я с ходу не могу нормальную формулу написать, чтобы точно посчитать вероятность.
Поздно уже, устал, мысли путаются. Не врубаюсь как учесть фактор ничьи. Возможно завтра днем, если время будет на работе попробую для себя вычислить.

@Red white socks · 21.12.2022, 22:26

anton78spb, понимаю, сам такой)
Вон формулу написал и допустил ошибку)
Правильно

Code
1
m(p,q)= 10/9*(m(p-1,q)*3/5 + m(p,q-1)*3/10)

Сообщение от anton78spb

Не врубаюсь как учесть фактор ничьи

По Байесу. Считаем вероятности победы, а дальше просто делим на вероятность ничьи

@anton78spb · 21.12.2022, 22:33

Red white socks, Если бы не было ничьих, то для выигрыша в серии первой команде надо было бы выиграть 4 матча из 6-ти.
Соответственно при условии что вероятность победы в матче первой команды 0,6, вероятность выиграть серию будет 0,6^4 + 0,4^2 и все это умножить на кол-во сочетаний из 4-х по 6-ти. Плюс к этому надо добавить вариант для счета 5-1, и 6-0 соответственно.
Но как сюда добавить вариант где например 3 победы, 2 поражения и одна ничья, да еще так, чтобы это красиво выглядело с ходу не соображу.

@Red white socks · 21.12.2022, 22:58

Итоговая вероятность получилась 91.17684%
Несмотря на отличие от

Сообщение от anton78spb

Эмпирически получается примерно 71% вероятность выигрыша первой команды.

исходя из опыта оценивал эту вероятность в 90%. Поэтому, скорее всего, верно. Но Монте-Карло тоже можно написать, да

Добавлено через 10 минут
anton78spb, уже писал - здесь делается рекуррентным расчетом с помощью формулы Байеса.
Пусть у нас счет m:n.
Из этого состояния он может перейти либо в m+1:n либо в m:n+1
Вероятности победы p=0.6, q=0.3. Вероятность победы, при условии что не было ничьи:
p* = 0.6/(0.6+0.3)
q* = 0.3/(0.6+0.3)

Новые блоги и статьи Все статьи Все блоги /
Отчёт о затраченных материалах за определенный период с макетом печатной формы Maks 21.04.2026 Отчёт из решения ниже размещен в конфигурации КА2. Задача: показать затраченные материалы за определенный период, с возможностью вывода печатной формы отчёта с шапкой и подвалом. В качестве. . .	Отчёт о спецтехнике находящейся в ремонте Maks 20.04.2026 Отчёт из решения ниже размещен в конфигурации КА2. Задача: отобразить спецтехнику, которая на данный момент находится в ремонте. Есть нетиповой документ "Заявка на ремонт спецтехники" который. . .	Памятка для бота и "визитка" для читателей "Semantic Universe Layer (Слой семантической вселенной)" Hrethgir 19.04.2026 Сгенерировано для краткого описания по случаю сборки и компиляции скелета серверного приложения. И пусть после этого скажут, что статьи сгенерированные AI - туфта и не интересно. И это не реклама -. . .	Запрет удаления строк ТЧ документа при определённом условии Maks 19.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "Аккумуляторы", разработанного в конфигурации КА2. У данного документа есть ТЧ, в которой в зависимости от прав доступа. . .
Модель заражения группы наркоманов alhaos 17.04.2026 Условия задачи сформулированы тут Суть: - Группа наркоманов из 10 человек. - Только один инфицирован ВИЧ. - Колются одной иглой. - Колются раз в день. - Колются последовательно через. . .	Мысли в слух. Про "навсегда". kumehtar 16.04.2026 Подумалось тут, что наверное очень глупо использовать во всяких своих установках понятие "навсегда". Это очень сильное понятие, и я только начинаю понимать край его смысла, не смотря на то что давно. . .	My Business CRM MaGz GoLd 16.04.2026 Всем привет, недавно возникла потребность создать CRM, для личных нужд. Собственно программа предоставляет из себя базу данных клиентов, в которой можно фиксировать звонки, стадии сделки, а также. . .	Знаешь почему 90% людей редко бывают счастливыми? kumehtar 14.04.2026 Потому что они ждут. Ждут выходных, ждут отпуска, ждут удачного момента. . . а удачный момент так и не приходит.

Динамическое программирование

Решение

Решение

@motya65100 0 / 0 / 0 Регистрация: 18.09.2021 Сообщений: 52
	21.12.2022, 20:24 [ТС]
	И правда, даже не подумал об этом, но все равно надо как-то решение оформить кодом 0

@motya65100 0 / 0 / 0 Регистрация: 18.09.2021 Сообщений: 52
	21.12.2022, 20:48 [ТС]
	А почему именно 6 в for _ in range(6)??? Добавлено через 3 минуты и эту строку объясни пожалуйста r = randint(1, 10) 0

@motya65100 0 / 0 / 0 Регистрация: 18.09.2021 Сообщений: 52
	21.12.2022, 21:03 [ТС]
	Всё понял, огромное тебе спасибо! Добавлено через 9 минут anton78spb, если в сокетах разбираетесь, отпишите в лс пожалуйста, одну функцию не могу сделать 0

@anton78spb 1956 / 874 / 352 Регистрация: 05.09.2021 Сообщений: 1,387
	21.12.2022, 22:18
	Red white socks, Вы правы. К сожалению, сейчас я с ходу не могу нормальную формулу написать, чтобы точно посчитать вероятность. Поздно уже, устал, мысли путаются. Не врубаюсь как учесть фактор ничьи. Возможно завтра днем, если время будет на работе попробую для себя вычислить. 0

@anton78spb 1956 / 874 / 352 Регистрация: 05.09.2021 Сообщений: 1,387
	21.12.2022, 22:33
	Red white socks, Если бы не было ничьих, то для выигрыша в серии первой команде надо было бы выиграть 4 матча из 6-ти. Соответственно при условии что вероятность победы в матче первой команды 0,6, вероятность выиграть серию будет 0,6^4 + 0,4^2 и все это умножить на кол-во сочетаний из 4-х по 6-ти. Плюс к этому надо добавить вариант для счета 5-1, и 6-0 соответственно. Но как сюда добавить вариант где например 3 победы, 2 поражения и одна ничья, да еще так, чтобы это красиво выглядело с ходу не соображу. 0