Автор: Досрочная волна 2025
Уровень: Базовый
Условие задачи:
Перед игроками лежит куча камней.
− убрать из кучи два камня,
− уменьшить количество камней в куче в два раза (количество камней, полученное при делении, округляется до меньшего).
Победителем считается игрок, сделавший последний ход, т.е. первым получивший в куче 87 камней или меньше. В начальный момент в куче было S камней; S > 88.
Теоретическая справка:
Весьма классическое условие для Теории игр, а это значит, что можно написать удобный и типовой код решения для всех трех задач.
Обратите внимание на 8 пункт в решении! Тут функция all() пишется для 20 и 21 номеров, а вот с 19 номером все сложнее. Если мы имеем условие "при любой игре Пети", то ставим all(), если же условие звучит как "после неудачного первого хода Пети", то будем писать функцию any()
Код решения:
Комментарии к коду:
- from math import ceil, floor
Импортирует функции округления вверх (ceil) и вниз (floor) из модуля math. - def F(s, n):
Определяет функцию F с двумя параметрами: s (текущее значение камней в куче) и n (количество оставшихся ходов игры). - if s <= 87:
Проверяет, не достигнуто ли пороговое значение 87 или меньше для завершения игры. - return n % 2 == 0
Если достигнуто пороговое значение, то возвращает True, если n четное (победил Ваня), и False, если n нечетное (победил Петя). - if n == 0:
Проверяет, не закончились ли ходы. - return 0
Если ходы закончились, возвращает 0 (что эквивалентно False), чтобы не зациклить нашу рекурсию. - h = [F(s-2, n-1), F(floor(s/2), n-1)]
Создает список возможных ходов: уменьшение s на 2 или деление s на 2 с округлением вниз. - return any(h) if (n - 1) % 2 == 0 else all(h)
Если следующий ход четный (n-1 четное), возвращает True, если хотя бы один из ходов выигрышный (any).
Если следующий ход нечетный, возвращает True, только если все ходы выигрышные (all). - print([s for s in range(89, 1000) if F(s, 2)])
Выводит список значений s от 89 до 999, для которых F(s, 2) возвращает True (выигрышные позиции при 2 ходе - победа Вани первым ходом). - print([s for s in range(89, 1000) if F(s, 3) and not F(s, 1)])
Выводит список значений s, для которых F(s, 3) истинно, а F(s, 1) ложно (выигрышные позиции при 3 ходе, но не при 1 - победа Пети вторым, но не первым ходом). - print([s for s in range(89, 1000) if F(s, 4) and not F(s, 2)])
Выводит список значений s, для которых F(s, 4) истинно, а F(s, 2) ложно (выигрышные позиции при 4 ходах, но не при 2 - победа Вани вторым или первым, но не только лишь первым ходом).
Больше разборов на эту и другие задачи вы можете найти в нашем Телеграм канале: Информатика ЕГЭ | itpy 👨💻
Подписывайтесь на наш канал по теории Python: Азим вкатывается в IT | itpy 💻 Вы найдете тут много полезного!