Задача по теме: "Теория игр (Задания 21)"
67. Теория игр Одна куча
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один или четыре камня либо увеличить количество камней в куче в три раза. Для того чтобы делать ходы, у каждого игрока есть неограниченное количество камней. Игра завершается в тот момент, когда количество камней в куче становится не менее 202.
Победителем считается игрок, сделавший последний ход, т.е. первым получивший кучу, состоящую из 202 или более камней.
В начальный момент в куче было S камней; 1 <= S <= 201.
67. Для игры, описанной в задании 19, найдите минимальное значение S, при котором одновременно выполняются два условия:
- у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;
- у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.
Если найдено несколько значений S, в ответе запишите наименьшее из них.
Решение:
Решим задание через Excel:
Построим таблицу всевозможных ходов Пети и Вани и настроим условное форматирование для наглядности. Нам нужно, чтобы Ваня не выигрывал своим первым ходом гарантировано (но он может выиграть первым ходом), но и не давал выиграть первым или вторым ходом Пете.
Подробное решение представлено в файле.
Решим задачу с помощью программы на языке программирования Python:
def game(s, m):
if s >= 202: return m%2==0
if m == 0: return 0
steps = [game(s+4,m-1), game(s+1,m-1), game(s*3,m-1)]
return any(steps) if m%2!=0 else all(steps)
print('21 задача:', [x for x in range(1,202) if not game(x,2) and game(x,4)])
Данный код решает задачу, используя рекурсивную функцию game(), которая проверяет различные комбинации ходов в игре. Функция game() принимает текущий счет игры s и количество оставшихся ходов m. Если текущий счет s больше или равен 202, функция возвращает True, если m является четным числом, иначе возвращает False. Если количество оставшихся ходов m равно 0, функция возвращает 0. В остальных случаях функция рекурсивно вызывает себя для трех возможных ходов и уменьшает количество оставшихся ходов на 1. Затем функция возвращает True, если хотя бы один из ходов возвращает True (если m нечетное) или если все ходы возвращают True (если m четное).
Ответ: 62
Сообщение об ошибке
Расскажите, в каком месте допущена ошибка, мы как можно быстрее её исправим. Спасибо за обратную связь!
| МГ | Pro | ProMax | |
| Практика на платформе |  |
|
|
| Отслеживание прогресса обучения | |
|
|
| Двухуровневое домашнее задание после каждого вебинара | |
|
|
| Все материалы составлены экспертом ЕГЭ | |
|
|
| Персональный менеджер | |
|
|
| Личный куратор | |
|
|
| Разбор ошибок личным куратором | |
|
|
| Еженедельные созвоны с куратором для закрытия индивидуальных пробелов | |
||
| Составление индивидуального расписания | |
счёта
средств
подтверждено!
Теперь вы можете приступить
к следующему уроку
курса по математике
замены
Для смены номера телефона
мы отправили Вам код по СМС,
введите его в поле ниже.
Электронная почта
На почту придет чек об оплатеНажимая кнопку "купить", Вы выражаете своё согласие с офертой оказания услуг и принимаете их условия
Здравствуйте!
Выберите информацию о себе ниже
Оплата прошла успешно!
