Ожидание количества ходов в игре

@Angel0k · Регистрация: 15.08.2021

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

https://sun9-71.userapi.com/im... type=album
Не получается написать программу. Все упирается в ряды, потому что игра может зациклиться, если наступить на клетку, которая ведет назад

@rept1d · 18.08.2021, 17:22

Вполне возможно, что существуют более простые (особенно по кол-ву знаний, необходимых для понимания) решения, но самым очевидным мне показалось такое.

Для начала введём вспомогательную величину $https://www.cyberforum.ru/cgi-bin/latex.cgi?s_i$ - номер клетки, в которую мы на самом деле перейдём, если кубик укажет на $https://www.cyberforum.ru/cgi-bin/latex.cgi?i$ :
$https://www.cyberforum.ru/cgi-bin/latex.cgi?s_i = \begin{cases} i & d_i = 0 \\ d_i & d_i \neq 0 \end{cases}$

Теперь с её помощью мы можем легко посчитать вероятность перейти с клетки $https://www.cyberforum.ru/cgi-bin/latex.cgi?i$ на клетку $https://www.cyberforum.ru/cgi-bin/latex.cgi?j$ . Для этого достаточно посмотреть, с каких из 6 клеток, следующих за текущей (именно на эти клетки может указать кубик), мы попадём на клетку $https://www.cyberforum.ru/cgi-bin/latex.cgi?j$ . Попасть на каждую из подходящих клеток вероятность 1/6, поэтому нужно просто умножить 1/6 на их количество. Получаем такую формулу:
$https://www.cyberforum.ru/cgi-bin/latex.cgi?p_{i, j} = \frac{1}{6} \sum_{k=1}^{6}\delta_{s_{i+k}}^j$

Где $https://www.cyberforum.ru/cgi-bin/latex.cgi?\delta$ - символ Кронекера:
$https://www.cyberforum.ru/cgi-bin/latex.cgi?\delta_a^b = \begin{cases} 1 & a = b \\ 0 & a \neq b \end{cases}$

Чтобы продвинуться дальше, нужно понимать что-то про цепи Маркова (гугл в помощь), а также уметь проводить основные операции над матрицами.

Поглощающим состоянием у нас будет конец игры (т.е. последняя клетка или правее). Для того, чтобы найти мат. ожидание кол-ва ходов перед попаданием в поглащающее состояние, я буду использовать фундаментальную матрицу поглощающей Марковской цепи. Чтобы её найти, нужно сначала построить матрицу переходов между непоглощающими состояниями (т.е. между клетками с номерами от 1 до N - 1). Получаем матрицу (N-1)x(N-1), где в клетке на пересечении i-й строки и j-го столбца содержится значение $https://www.cyberforum.ru/cgi-bin/latex.cgi?p_{i, j}$ . Например, для N = 4 матрица будет иметь вид:
$https://www.cyberforum.ru/cgi-bin/latex.cgi? Q = \begin{pmatrix} p_{1,1} & p_{1,2} & p_{1,3}\\ p_{2,1} & p_{2,2} & p_{2,3}\\ p_{3,1} & p_{3,2} & p_{3,3} \end{pmatrix} $

Фундаментальная матрица считается как обратная от разности единичной матрицы и матрицы переходов:
$https://www.cyberforum.ru/cgi-bin/latex.cgi? M = (I - Q)^{-1} = \begin{pmatrix} 1 - p_{1,1} & -p_{1,2} & -p_{1,3}\\ -p_{2,1} & 1 - p_{2,2} & -p_{2,3}\\ -p_{3,1} & -p_{3,2} & 1 - p_{3,3} \end{pmatrix}^{-1} $

Выражать обратную матрицу в общем виде я уже не буду, но в этом и нет смысла, поскольку в Вашей программе на этом моменте все значения $https://www.cyberforum.ru/cgi-bin/latex.cgi?p$ уже давно известны. Поэтому не должно составить труда найти обратную матрицу, используя любой известный Вам метод (ну или погуглите, там не очень сложно).

Ответом на задачу будет сумма чисел в произведении вектора начального распределения вероятностей на получившуюся матрицу M. Поскольку по условию известно, что мы всегда начинаем в 1-й клетке, то этот вектор будет состоять из единицы и кучи нулей, и тогда ответом будет просто сумма чисел в 1-й строке M.

Подводя итог, нужно сделать следующее:

Посчитать значения $https://www.cyberforum.ru/cgi-bin/latex.cgi?s_i$ - O(N)
Посчитать значения $https://www.cyberforum.ru/cgi-bin/latex.cgi?p_{i,j}$ - O(N^2)
Построить матрицу $https://www.cyberforum.ru/cgi-bin/latex.cgi?I - Q$ - O(N^2)
Найти обратную ей - O(N^3)
Посчитать сумму чисел в первой строке - O(N)

Шаги 2 и 3 можно объединить в один, немного поменяв формулу $https://www.cyberforum.ru/cgi-bin/latex.cgi?p$ .

@alexu_007 · 19.08.2021, 08:18

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

если наступить на клетку, которая ведет назад

Что мешает пометить клетку, из которой был совершён ход - что-бы исключить ходы назад?

@rept1d · 19.08.2021, 15:36

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

Что мешает пометить клетку, из которой был совершён ход - что-бы исключить ходы назад?

То что их нельзя исключать. Циклы в том числе разрешены, и решение должно быть к ним готово.

@alexu_007 · 20.08.2021, 07:02

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

То что их нельзя исключать.

В чём проблема то? Помечаешь клетку, из которой был сделан ход и стираешь пометки у всех остальных - делая их доступными для хода.

@rept1d · 20.08.2021, 23:31

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

В чём проблема то? Помечаешь клетку, из которой был сделан ход и стираешь пометки у всех остальных - делая их доступными для хода.

Это бы работало, если б действительно нельзя было ходить назад. Но где в условии это запрещено? Спокойно может возникнуть бесконечный цикл между посещёнными клетками, но это не мешает определить мат. ожидание кол-ва ходов.

Новые блоги и статьи Все статьи Все блоги /
Оптимизация кода на разграничение прав доступа к элементам формы Maks 13.04.2026 Алгоритм из решения ниже реализован на нетиповом документе, разработанного в конфигурации КА2. Задачи, как таковой, поставлено не было, проделанное ниже исключительно моя инициатива. Было так:. . .	Контроль заполнения и очистка дат в зависимости от значения перечислений Maks 12.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеПерсонала", разработанного в конфигурации КА2. Задача: реализовать контроль корректности заполнения дат назначения. . .	Архитектура слоя интернета для сервера-слоя. Hrethgir 11.04.2026 В продолжение https:/ / www. cyberforum. ru/ blogs/ 223907/ 10860. html Знаешь что я подумал? Раз мы все источники пишем в голове ветки, то ничего не мешает добавить в голову такой источник, который сам. . .	Подстановка значения реквизита справочника в табличную часть документа Maks 10.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеПерсонала", разработанного в конфигурации КА2. Задача: при выборе сотрудника (справочник Сотрудники) в ТЧ документа. . .
Очистка реквизитов документа при копировании Maks 09.04.2026 Алгоритм из решения ниже применим как для типовых, так и для нетиповых документов на самых различных конфигурациях. Задача: при копировании документа очищать определенные реквизиты и табличную. . .	модель ЗдравоСохранения 8. Подготовка к разному выполнению заданий anaschu 08.04.2026 https:/ / github. com/ shumilovas/ med2. git main ветка * содержимое блока дэлэй из старой модели теперь внутри зайца новой модели 8ATzM_2aurI	Блокировка документа от изменений, если он открыт у другого пользователя Maks 08.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа, разработанного в конфигурации КА2. Задача: запретить редактирование документа, если он открыт у другого пользователя. / / . . .	Система безопасности+живучести для сервера-слоя интернета (сети). Двойная привязка. Hrethgir 08.04.2026 Далее были размышления о системе безопасности. Сообщения с наклонным текстом - мои. А как нам будет можно проверить, что ссылка наша, а не подделана хулиганами, которая выбросит на другую ветку и. . .

@Angel0k 0 / 0 / 0 Регистрация: 15.08.2021 Сообщений: 1

	Ожидание количества ходов в игре 15.08.2021, 15:32. Показов 3386. Ответов 5 Метки математическое ожидание, программирование, ряды, с++ (Все метки) https://sun9-71.userapi.com/im... type=album Не получается написать программу. Все упирается в ряды, потому что игра может зациклиться, если наступить на клетку, которая ведет назад 0

@rept1d 0 / 0 / 0 Регистрация: 18.08.2021 Сообщений: 4
	18.08.2021, 17:22
	Вполне возможно, что существуют более простые (особенно по кол-ву знаний, необходимых для понимания) решения, но самым очевидным мне показалось такое. Для начала введём вспомогательную величину $https://www.cyberforum.ru/cgi-bin/latex.cgi?s_i$ - номер клетки, в которую мы на самом деле перейдём, если кубик укажет на $https://www.cyberforum.ru/cgi-bin/latex.cgi?i$ : $https://www.cyberforum.ru/cgi-bin/latex.cgi?s_i = \begin{cases} i & d_i = 0 \\ d_i & d_i \neq 0 \end{cases}$ Теперь с её помощью мы можем легко посчитать вероятность перейти с клетки $https://www.cyberforum.ru/cgi-bin/latex.cgi?i$ на клетку $https://www.cyberforum.ru/cgi-bin/latex.cgi?j$ . Для этого достаточно посмотреть, с каких из 6 клеток, следующих за текущей (именно на эти клетки может указать кубик), мы попадём на клетку $https://www.cyberforum.ru/cgi-bin/latex.cgi?j$ . Попасть на каждую из подходящих клеток вероятность 1/6, поэтому нужно просто умножить 1/6 на их количество. Получаем такую формулу: $https://www.cyberforum.ru/cgi-bin/latex.cgi?p_{i, j} = \frac{1}{6} \sum_{k=1}^{6}\delta_{s_{i+k}}^j$ Где $https://www.cyberforum.ru/cgi-bin/latex.cgi?\delta$ - символ Кронекера: $https://www.cyberforum.ru/cgi-bin/latex.cgi?\delta_a^b = \begin{cases} 1 & a = b \\ 0 & a \neq b \end{cases}$ Чтобы продвинуться дальше, нужно понимать что-то про цепи Маркова (гугл в помощь), а также уметь проводить основные операции над матрицами. Поглощающим состоянием у нас будет конец игры (т.е. последняя клетка или правее). Для того, чтобы найти мат. ожидание кол-ва ходов перед попаданием в поглащающее состояние, я буду использовать фундаментальную матрицу поглощающей Марковской цепи. Чтобы её найти, нужно сначала построить матрицу переходов между непоглощающими состояниями (т.е. между клетками с номерами от 1 до N - 1). Получаем матрицу (N-1)x(N-1), где в клетке на пересечении i-й строки и j-го столбца содержится значение $https://www.cyberforum.ru/cgi-bin/latex.cgi?p_{i, j}$ . Например, для N = 4 матрица будет иметь вид: $https://www.cyberforum.ru/cgi-bin/latex.cgi?<br /> Q = \begin{pmatrix}<br /> p_{1,1} & p_{1,2} & p_{1,3}\\<br /> p_{2,1} & p_{2,2} & p_{2,3}\\<br /> p_{3,1} & p_{3,2} & p_{3,3}<br /> \end{pmatrix}<br />$ Фундаментальная матрица считается как обратная от разности единичной матрицы и матрицы переходов: $https://www.cyberforum.ru/cgi-bin/latex.cgi?<br /> M = (I - Q)^{-1} = \begin{pmatrix}<br /> 1 - p_{1,1} & -p_{1,2} & -p_{1,3}\\<br /> -p_{2,1} & 1 - p_{2,2} & -p_{2,3}\\<br /> -p_{3,1} & -p_{3,2} & 1 - p_{3,3}<br /> \end{pmatrix}^{-1}<br />$ Выражать обратную матрицу в общем виде я уже не буду, но в этом и нет смысла, поскольку в Вашей программе на этом моменте все значения $https://www.cyberforum.ru/cgi-bin/latex.cgi?p$ уже давно известны. Поэтому не должно составить труда найти обратную матрицу, используя любой известный Вам метод (ну или погуглите, там не очень сложно). Ответом на задачу будет сумма чисел в произведении вектора начального распределения вероятностей на получившуюся матрицу M. Поскольку по условию известно, что мы всегда начинаем в 1-й клетке, то этот вектор будет состоять из единицы и кучи нулей, и тогда ответом будет просто сумма чисел в 1-й строке M. Подводя итог, нужно сделать следующее: Посчитать значения $https://www.cyberforum.ru/cgi-bin/latex.cgi?s_i$ - O(N) Посчитать значения $https://www.cyberforum.ru/cgi-bin/latex.cgi?p_{i,j}$ - O(N^2) Построить матрицу $https://www.cyberforum.ru/cgi-bin/latex.cgi?I - Q$ - O(N^2) Найти обратную ей - O(N^3) Посчитать сумму чисел в первой строке - O(N) Шаги 2 и 3 можно объединить в один, немного поменяв формулу $https://www.cyberforum.ru/cgi-bin/latex.cgi?p$ . 0