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

@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)

Новые блоги и статьи Все статьи Все блоги /
Переходник USB-CAN-GPIO Eddy_Em 20.03.2026 Достаточно давно на работе возникла необходимость в переходнике CAN-USB с гальваноразвязкой, оный и был разработан. Однако, все меня терзала совесть, что аж 48-ногий МК используется так тупо: просто. . .	Оттенки серого Argus19 18.03.2026 Оттенки серого Нашёл в интернете 3 прекрасных модуля: Модуль класса открытия диалога открытия/ сохранения файла на Win32 API; Модуль класса быстрого перекодирования цветного изображения в оттенки. . .	SDL3 для Desktop (MinGW): Рисуем цветные прямоугольники с помощью рисовальщика SDL3 на Си и C++ 8Observer8 17.03.2026 Содержание блога Финальные проекты на Си и на C++: finish-rectangles-sdl3-c. zip finish-rectangles-sdl3-cpp. zip	Символические и жёсткие ссылки в Linux. algri14 15.03.2026 Существует два типа ссылок — символические и жёсткие. Ссылка в Linux — это запись в каталоге, которая может указывать либо на inode «файла-ИСТОЧНИКА», тогда это будет «жёсткая ссылка» (hard link),. . .
[Owen Logic] Поддержание уровня воды в резервуаре количеством включённых насосов: моделирование и выбор регулятора ФедосеевПавел 14.03.2026 Поддержание уровня воды в резервуаре количеством включённых насосов: моделирование и выбор регулятора ВВЕДЕНИЕ Выполняя задание на управление насосной группой заполнения резервуара,. . .	делаю науч статью по влиянию грибов на сукцессию anaschu 13.03.2026 прикрепляю статью	SDL3 для Desktop (MinGW): Создаём пустое окно с нуля для 2D-графики на SDL3, Си и C++ 8Observer8 10.03.2026 Содержание блога Финальные проекты на Си и на C++: hello-sdl3-c. zip hello-sdl3-cpp. zip Результат:	Установка CMake и MinGW 13.1 для сборки С и C++ приложений из консоли и из Qt Creator в EXE 8Observer8 10.03.2026 Содержание блога MinGW - это коллекция инструментов для сборки приложений в EXE. CMake - это система сборки приложений. Здесь описаны базовые шаги для старта программирования с помощью CMake и. . .

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

Решение

Решение

@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