Всемирный день риса

ЕГЭ по информатике 2023 - Задания 19-21 (Теория игр на Python)



Продолжаем наш видеокурс по подготовке к ЕГЭ по информатике 2023!


Сегодня разберём задачи из 19, 20 и 21 задания ЕГЭ по информатике. Для этих задач существует спасительный шаблон на Python, который позволяет получить на них правильные ответы и затратить минимум сил и времени.


Приступим к первой серии задач из демоверсии ЕГЭ по информатике 2021 года.





Задание 19 (Демо 2021)

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч (по своему выбору) один камень или увеличить количество камней в куче в два раза. Например, пусть в одной куче 10 камней, а в другой 5 камней; такую позицию в игре будем обозначать (10, 5). Тогда за один ход можно получить любую из четырёх позиций: (11, 5), (20, 5), (10, 6), (10, 10). Для того чтобы делать ходы, у каждого игрока есть неограниченное количество камней.


Игра завершается в тот момент, когда суммарное количество камней в кучах становится не менее 77. Победителем считается игрок, сделавший последний ход, т.е. первым получивший такую позицию, при которой в кучах будет 77 или больше камней.


В начальный момент в первой куче было семь камней, во второй куче – S камней; 1 ≤ S ≤ 69.


Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока – значит описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника. В описание выигрышной стратегии не следует включать ходы играющего по этой стратегии игрока, не являющиеся для него безусловно выигрышными, т.е. не являющиеся выигрышными независимо от игры противника.


Известно, что Ваня выиграл своим первым ходом после неудачного первого хода Пети. Укажите минимальное значение S, когда такая ситуация возможна.





Решение:

Решим задачу с помощью шаблона на языке программирования Python. Если хотите ознакомится с аналитическим решением задач на теорию игр, можете посмотреть мои статьи по 19 Заданию, 20 Заданию, 21 Заданию. Но с помощью шаблонов на экзамене решать быстрее и легче.


Введём параметр p, который будет олицетворять позицию игры (ход).


Начальная позиция Ход Пети Ход Вани Ход Пети Ход Вани Ход Пети
p 1 2 3 4 5 6


def F(x, y, p):
    if x + y >= 77 and p==3: return True
    if x + y < 77 and p==3: return False

    return F(x+1, y, p+1) or F(x*2, y, p+1) or F(x, y+1, p+1) or F(x, y*2, p+1)
  

for s in range(1, 70):
    if F(s, 7, 1):
        print(s)

Заводим функцию F. Она принимает параметры: x - количество камней в одной куче, y - в другой, p-позиция игры.





Дальше описываем победу. Если x+y>=77 и позиция равна 3 (1 Ход Вани), то возвращаем True, что означает победу.


Если, позиция уже равна 3, но сумарное количество камней меньше, чем должно быть для победы, то возвращаем False (проигрыш).


Если мы не вышли на первых двух условиях, то, значит, продолжаем прокручивать ходы, рекурсивно запускаем функцию F.


Т.к. здесь формулировка: "Известно, что Ваня выиграл своим первым ходом после неудачного первого хода Пети.", то между функциями ставим союз ИЛИ (or).


В конце перебираем все возможные значения для s через цикл for, ищём те значения, которые подходят по условию задачи. Значение p всегда увеличиваем на 1.


Ответ: 18



Задание 20 (Демо 2021)

Для игры, описанной в предыдущем задании, найдите два таких значения S, при которых у Пети есть выигрышная стратегия, причём одновременно выполняются два условия:


− Петя не может выиграть за один ход;

− Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.


Найденные значения запишите в ответе в порядке возрастания.


Решение:

Легко переделать из прошлой задачи.


def F(x, y, p):
    if x + y >= 77 and p==4: return True
    if x + y < 77 and p==4: return False
    if x + y >= 77: return False

    if p%2==0:
        return F(x+1, y, p+1) and F(x*2, y, p+1) and F(x, y+1, p+1) and F(x, y*2, p+1)
    else:
        return F(x+1, y, p+1) or F(x*2, y, p+1) or F(x, y+1, p+1) or F(x, y*2, p+1)
  

for s in range(1, 70):
    if F(s, 7, 1):
        print(s)




Теперь должен выигрывать Петя на своём втором ходе. Поэтому в условиях ставим позицию p=4.


Добавляется третье условие. Если кто-то выиграл, но на первых двух условиях мы не вышли из функции, то, значит, выиграл не тот, кто нам нужен, следовательно, возвращаем Fasle.


Здесь вопрос отличается от 19 задания. Здесь Петя должен побеждать при любом ходе соперника, а не при одном неудачном ходе Вани, поэтому добавляется ещё условие.


Для чётных p (это ходы Пети), возвращаем разные ходы через and, т.к. он должен побеждать в любом случае.


Для нечётных p (это ходы Вани), возвращаем ходы через or.


Ответ:
31 34




Задание 21 (Демо 2021)

Для игры, описанной в задании 19, найдите минимальное значение S, при котором одновременно выполняются два условия:


– у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;


– у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.


Решение:

Опять используем прошлый шаблон, но немного модернизируем.


def F(x, y, p):
    if x + y >= 77 and (p==3 or p==5): return True
    if x + y < 77 and p==5: return False
    if x + y >= 77: return False

    if p%2==1:
        return F(x+1, y, p+1) and F(x*2, y, p+1) and F(x, y+1, p+1) and  F(x, y*2, p+1)
    else:
         return F(x+1, y, p+1) or F(x*2, y, p+1) or F(x, y+1, p+1) or  F(x, y*2, p+1)


def F1(x, y, p):
    if x + y >= 77 and p==3: return True
    if x + y < 77 and p==3: return False
    if x + y >= 77: return False

    if p%2==1:
        return F1(x+1, y, p+1) and F1(x*2, y, p+1) and F1(x, y+1, p+1) and  F1(x, y*2, p+1)
    else:
         return F1(x+1, y, p+1) or F1(x*2, y, p+1) or F1(x, y+1, p+1) or  F1(x, y*2, p+1)

for s in range(1, 70):
    if F(s, 7, 1):
        print(s)

print()

for s in range(1, 70):
    if F1(s, 7, 1):
        print(s)




Здесь Ваня должен выигрывать либо на первом своём ходе (p=3), либо на втором своём ходе (p=5).


Т.к. Ваня не должен гарантированно выиграть своим первым ходом, то мы создаём ещё одну функцию F1, похожую на основную функцию F, которая вычисляет, когда Ваня именно гарантированно выигрывает на своём первом ходе (p=3). И, затем, мы из тех чисел, которые получились в первой функции F, исключаем числа, которые получились во второй функции F1.


В первой функции получилось 30,33, а во второй результатов нет. Получается ответ 30.


Ответ: 30

Следущая вариация задач отличается от первой лишь задачей в 19-ом задании. Рассмотрим демоверсию ЕГЭ по информатике 2022. Так же в этой серии задач будет одна куча, но из-за этого шаблон практически никак не меняется.





Задание 19 (Демо 2022)

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один камень или увеличить количество камней в куче в два раза. Для того чтобы делать ходы, у каждого игрока есть неограниченное количество камней.

Игра завершается в тот момент, когда количество камней в куче становится не менее 29. Победителем считается игрок, сделавший последний ход, т.е. первым получивший кучу, в которой будет 29 или больше камней.

В начальный момент в куче было S камней, 1 ≤ S ≤ 28.

Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока – значит описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника. В описание выигрышной стратегии не следует включать ходы играющего по этой стратегии игрока, не являющиеся для него безусловно выигрышными, т.е. не являющиеся выигрышными независимо от игры противника.

Укажите такое значение S, при котором Петя не может выиграть за один ход, но при любом ходе Пети Ваня может выиграть своим первым ходом.



Решение:

Здесь вопрос отличается от прошлой 19-ой задачи. Здесь Петя должен выиграть в любом случае. Мы эту задачу можем воспринимать, как 20-ую из демоверсии 2021. Ведь там тоже игроку нужно обязательно было побеждать. Осталось написать шаблон с соответствующими параметрами.



def F(x, p):
    if x>=29 and p==3: return True
    if x<29 and p==3: return False
    if x>=29: return False

    if p%2==1:
        return F(x+1, p+1) and F(x*2, p+1)
    else:
         return F(x+1, p+1) or F(x*2, p+1)

for s in range(1, 29):
    if F(s, 1):
        print(s)




Заводим функцию F. Т.к. у нас одна куча, то она принимает параметры: x - количество камней в куче, p-позиция игры.


Дальше описываем победу. Если x>=29 и позиция равна 3 (1 Ход Вани), то возвращаем True, что означает победу.


Если, позиция уже равна 3, но камней меньше, чем должно быть для победы, то возвращаем False (проигрыш).


Третье условие. Если кто-то выиграл, но на первых двух условиях мы не вышли из функции, то, значит, выиграл не тот, кто нам нужен, следовательно, возвращаем Fasle.


Если мы не вышли на первых трёх условиях, то, значит, продолжаем прокручивать ходы, рекурсивно запускаем функцию F.


Для нечётных p (это ходы Вани), возвращаем разные ходы через and, т.к. он должен побеждать в любом случае. При этом увеличиваем на 1 значение p.


Для чётных p (это ходы Пети), возвращаем ходы через or.


В конце перебираем все возможные значения для s через цикл for, ищём те значения, которые подходят по условию задачи.


Ответ: 14



Задание 20 (Демо 2022)

Для игры, описанной в задании 19, найдите два таких значения S, при которых у Пети есть выигрышная стратегия, причём одновременно выполняются два условия:

− Петя не может выиграть за один ход;

− Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.

Найденные значения запишите в ответе в порядке возрастания.



Решение:

Задача точно такая же, как и в 19 задании, только теперь обязательно должен побежать Петя на своём втором ходу (p=4), при любой игре Вани.


Пишем тот же шаблон, немного отредактировав его.


def F(x, p):
    if x>=29 and p==4: return True
    if x<29 and p==4: return False
    if x>=29: return False

    if p%2==0:
        return F(x+1, p+1) and F(x*2, p+1)
    else:
         return F(x+1, p+1) or F(x*2, p+1)

for s in range(1, 29):
    if F(s, 1):
        print(s)

Получается 7 и 13.


Ответ:
7 13




Задание 21 (Демо 2022)

Для игры, описанной в задании 19, найдите значение S, при котором одновременно выполняются два условия:

− у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;

− у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.

Если найдено несколько значений S, в ответе запишите минимальное из них.



Решение:

Опять используем прошлый шаблон, но немного модернизируем.


def F(x, p):
    if x>=29 and (p==3 or p==5): return True
    if x<29 and p==5: return False
    if x>=29: return False

    if p%2==1:
        return F(x+1, p+1) and F(x*2, p+1)
    else:
         return F(x+1, p+1) or F(x*2, p+1)


def F1(x, p):
    if x>=29 and p==3: return True
    if x<29 and p==3: return False
    if x>=29: return False

    if p%2==1:
        return F1(x+1, p+1) and F1(x*2, p+1)
    else:
         return F1(x+1, p+1) or F1(x*2, p+1)

for s in range(1, 29):
    if F(s, 1):
        print(s)

print()

for s in range(1, 29):
    if F1(s, 1):
        print(s)




Здесь Ваня должен выигрывать либо на первом своём ходе (p=3), либо на втором своём ходе (p=5).


Т.к. Ваня не должен гарантированно выиграть своим первым ходом, то мы создаём ещё одну функцию F1, похожую на основную функцию F, которая вычисляет, когда Ваня именно гарантированно выигрывает на своём первом ходе (p=3). И, затем, мы из тех чисел, которые получились в первой функции F, исключаем числа, которые получились во второй функции F1.


В первой функции получилось 12,14, а во второй 14. Получается ответ 12.


Ответ: 12

На сегодня всё. Мы рассмотрели самые распространённые вариации задач из 19-21 задания и подобрали к ним "противоядие". До новых встреч!






19-07-2022 в 06:53:40





Поддержать сайт:


Похожая статья:

ЕГЭ по информатике 2021 - Задание 25 (Обработка целочисленной информации)

Всем привет! Пришло время разбора 25 задания из ЕГЭ по информатике 202...

Категория: Информатика  Подкатегория: ЕГЭ
Дата: 12-01-2021 в 15:11:32 9


Комментарии:

В первой 21 задаче в функции F1 только камни x сраниваются с 77. Там надо x + y как в основной функции?
Артём 14-01-2023 в 15:42:19

Да, Вы правы, нужно x+y писать. Исправил, спасибо!
Калужский Александр 14-01-2023 в 19:07:24

Почему начальная позиция p=1? Нельзя ли её сделать р=0? Дабы избежать у учеников путаницы в голове по нумерации ходов. Или в этом скрывается ошибка? Извините хотел оперативный ответ от Мастера, т.к. нет времени на эксперименты.
Александр Литвиненко 27-01-2023 в 06:53:14

На мой взгляд, можно, поменяв соответствующие параметры тоже. Но не будет ли путаницы, если ваши ученики будут находить решения в интернете, где начинается p c 1.
Калужский Александр 27-01-2023 в 08:34:26

В первом 19ом задании в функции def мне кажется, что не хватает строки if x + y >= 77: return False Спасибо за Ваш труд!
Александр Литвиненко 27-01-2023 в 08:49:45

Нет, там всё в порядке. В формулировке, когда "после неудачного первого хода Пети", можно писать два условия.
Калужский Александр 27-01-2023 в 08:55:54

Спасибо чел, помогло
Илья 09-02-2023 в 06:41:28

я не понимаю почему вы в первых задачах пишите в конце программы строку " if F1(s, 7, 1):"
Андрей Иванов 15-02-2023 в 17:45:23

Проверяем подходит ли значение s под условие задачи. Семёрка - это количество каменей в первой куче.
Калужский Александр 16-02-2023 в 18:39:06

Спасибо, за последовательность объяснения. все очень понятно.
Фатима 27-02-2023 в 12:44:18

почему то в 20 задании находит только одно значение, уже несколько вариантов КИМа так, код написан правильно. В чём причина может быть?
ZryV1 01-03-2023 в 18:25:05

Пришлите ссылку на задание.
Калужский Александр 01-03-2023 в 18:48:53

Задание 21 из КИМа ЕГЭ 2023 по информатике 17 вариант(к примеру). Можно положить 1 камень или умножить количество на 2, Если больше или равно 144 в сумме двух куч, то победа.В первой куче 3 камня, во второй 1
ZryV1 05-03-2023 в 17:55:56

от 1 до 140(включительно). Условия те же. Также неверные ответы получаются в 19 и 20 заданиях. Код правильный
Загир Гаджиев 05-03-2023 в 19:07:28

Не очень понял, с какого сайта этот КИМ ??
Калужский Александр 05-03-2023 в 19:10:09

КИМ это оффициальный сборник вариантов в виде книжки. Могу условия на почту скинуть(хотя вроде расписал всё), тут ограничение символов
Загир Гаджиев 05-03-2023 в 19:17:34

Кто автор у данной книги ?
Калужский Александр 05-03-2023 в 19:32:42

Крылов и Чуркина
Загир Гаджиев 05-03-2023 в 19:35:22

Понятно, тогда посмотрю и напишу здесь, что думаю.
Калужский Александр 05-03-2023 в 19:36:30

Решил 17 вариант (задания 19-21) из сборника 2023 года Крылова, Чуркиной по схеме из этой статьи. Ответы сошлись. Могу вам прислать решения, если вы напишите в группе в вк.
Калужский Александр 06-03-2023 в 09:47:04

Добрый вечер, можете сказать, что необходимо добавить в код, если в условии есть такое: "При этом нельзя повторять ход, который только что сделал второй игрок"
Figh 19-03-2023 в 15:23:24

Добрый вечер! Над этим нужно думать отдельно.
Калужский Александр 19-03-2023 в 15:35:00

Здравствуйте,можете сказать, пожалуйста, а зачем в конкретном случае нужно менять or на and,не совсем понятно просто. Почему нельзя оставить or и не менять ничего, мы же как бы делаем выбор из ходов? Тут получается они будут срабатывать одновременно при логическом умножении? Или нет?
AppleJuice 01-05-2023 в 12:13:25

Чтобы ответить на этот вопрос, нужно полностью разобрать, как работает шаблон.
Калужский Александр 01-05-2023 в 13:58:08



Оставить коментарий:



Напишите email, чтобы получать сообщения о новых комментариях (необязательно):


Задача против робота. Расположите картинки горизонтально:




Нажимая кнопку Отправить, Вы соглашаетесь с политикой конфиденциальности сайта.