ЕГЭ по информатике 2023 — Задания 19-21 (Теория игр на Python)
Продолжаем наш видеокурс по подготовке к ЕГЭ по информатике 2023!
Сегодня разберём задачи из 19, 20 и 21 задания ЕГЭ по информатике. Для этих задач существует спасительный шаблон на Python, который позволяет получить на них правильные ответы и затратить минимум сил и времени.
Приступим к первой серии задач из демоверсии ЕГЭ по информатике 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 |
Заводим функцию F. Она принимает параметры: x — количество камней в одной куче, y — в другой, p-позиция игры.
Дальше описываем победу. Если x+y>=77 и позиция равна 3 (1 Ход Вани), то возвращаем True, что означает победу.
Если, позиция уже равна 3, но сумарное количество камней меньше, чем должно быть для победы, то возвращаем False (проигрыш).
Если мы не вышли на первых двух условиях, то, значит, продолжаем прокручивать ходы, рекурсивно запускаем функцию F.
Т.к. здесь формулировка: «Известно, что Ваня выиграл своим первым ходом после неудачного первого хода Пети.», то между функциями ставим союз ИЛИ (or).
В конце перебираем все возможные значения для s через цикл for, ищём те значения, которые подходят по условию задачи. Значение p всегда увеличиваем на 1.
Для игры, описанной в предыдущем задании, найдите два таких значения S, при которых у Пети есть выигрышная стратегия, причём одновременно выполняются два условия:
− Петя не может выиграть за один ход;
− Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.
Найденные значения запишите в ответе в порядке возрастания.
Легко переделать из прошлой задачи.
Теперь должен выигрывать Петя на своём втором ходе. Поэтому в условиях ставим позицию p=4.
Добавляется третье условие. Если кто-то выиграл, но на первых двух условиях мы не вышли из функции, то, значит, выиграл не тот, кто нам нужен, следовательно, возвращаем Fasle.
Здесь вопрос отличается от 19 задания. Здесь Петя должен побеждать при любом ходе соперника, а не при одном неудачном ходе Вани, поэтому добавляется ещё условие.
Для чётных p (это ходы Пети), возвращаем разные ходы через and, т.к. он должен побеждать в любом случае.
Для нечётных p (это ходы Вани), возвращаем ходы через or.
Ответ:
| 31 | 34 |
Для игры, описанной в задании 19, найдите минимальное значение S, при котором одновременно выполняются два условия:
– у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;
– у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.
Опять используем прошлый шаблон, но немного модернизируем.
Здесь Ваня должен выигрывать либо на первом своём ходе (p=3), либо на втором своём ходе (p=5).
Т.к. Ваня не должен гарантированно выиграть своим первым ходом, то мы создаём ещё одну функцию F1, похожую на основную функцию F, которая вычисляет, когда Ваня именно гарантированно выигрывает на своём первом ходе (p=3). И, затем, мы из тех чисел, которые получились в первой функции F, исключаем числа, которые получились во второй функции F1.
В первой функции получилось 30,33, а во второй результатов нет. Получается ответ 30.
Следущая вариация задач отличается от первой лишь задачей в 19-ом задании. Рассмотрим демоверсию ЕГЭ по информатике 2022. Так же в этой серии задач будет одна куча, но из-за этого шаблон практически никак не меняется.
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один камень или увеличить количество камней в куче в два раза. Для того чтобы делать ходы, у каждого игрока есть неограниченное количество камней.
Игра завершается в тот момент, когда количество камней в куче становится не менее 29. Победителем считается игрок, сделавший последний ход, т.е. первым получивший кучу, в которой будет 29 или больше камней.
В начальный момент в куче было S камней, 1 ≤ S ≤ 28.
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока – значит описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника. В описание выигрышной стратегии не следует включать ходы играющего по этой стратегии игрока, не являющиеся для него безусловно выигрышными, т.е. не являющиеся выигрышными независимо от игры противника.
Укажите такое значение S, при котором Петя не может выиграть за один ход, но при любом ходе Пети Ваня может выиграть своим первым ходом.
Здесь вопрос отличается от прошлой 19-ой задачи. Здесь Петя должен выиграть в любом случае. Мы эту задачу можем воспринимать, как 20-ую из демоверсии 2021. Ведь там тоже игроку нужно обязательно было побеждать. Осталось написать шаблон с соответствующими параметрами.
Заводим функцию F. Т.к. у нас одна куча, то она принимает параметры: x — количество камней в куче, p-позиция игры.
Дальше описываем победу. Если x>=29 и позиция равна 3 (1 Ход Вани), то возвращаем True, что означает победу.
Если, позиция уже равна 3, но камней меньше, чем должно быть для победы, то возвращаем False (проигрыш).
Третье условие. Если кто-то выиграл, но на первых двух условиях мы не вышли из функции, то, значит, выиграл не тот, кто нам нужен, следовательно, возвращаем Fasle.
Если мы не вышли на первых трёх условиях, то, значит, продолжаем прокручивать ходы, рекурсивно запускаем функцию F.
Для нечётных p (это ходы Вани), возвращаем разные ходы через and, т.к. он должен побеждать в любом случае. При этом увеличиваем на 1 значение p.
Для чётных p (это ходы Пети), возвращаем ходы через or.
В конце перебираем все возможные значения для s через цикл for, ищём те значения, которые подходят по условию задачи.
Для игры, описанной в задании 19, найдите два таких значения S, при которых у Пети есть выигрышная стратегия, причём одновременно выполняются два условия:
− Петя не может выиграть за один ход;
− Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.
Найденные значения запишите в ответе в порядке возрастания.
Задача точно такая же, как и в 19 задании, только теперь обязательно должен побежать Петя на своём втором ходу (p=4), при любой игре Вани.
Пишем тот же шаблон, немного отредактировав его.
Получается 7 и 13.
Ответ:
| 7 | 13 |
Для игры, описанной в задании 19, найдите значение S, при котором одновременно выполняются два условия:
− у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;
− у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.
Если найдено несколько значений S, в ответе запишите минимальное из них.
Опять используем прошлый шаблон, но немного модернизируем.
Здесь Ваня должен выигрывать либо на первом своём ходе (p=3), либо на втором своём ходе (p=5).
Т.к. Ваня не должен гарантированно выиграть своим первым ходом, то мы создаём ещё одну функцию F1, похожую на основную функцию F, которая вычисляет, когда Ваня именно гарантированно выигрывает на своём первом ходе (p=3). И, затем, мы из тех чисел, которые получились в первой функции F, исключаем числа, которые получились во второй функции F1.
В первой функции получилось 12,14, а во второй 14. Получается ответ 12.
На сегодня всё. Мы рассмотрели самые распространённые вариации задач из 19-21 задания и подобрали к ним «противоядие». До новых встреч!
Рубрика «ЕГЭ Задание 19-21»
ЕГЭ информатика 19-21 задание разбор, теория, как решать.
Теория игр, выигрышная стратегия, 19.(Б) — 1 балл, 20.(П) — 1 балл, 21.(В) — 1 балл
Е19-21.31 когда количество камней в куче становится не менее 129
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один камень или увеличить количество камней в куче в два раза. Для того чтобы делать ходы, у каждого игрока есть неограниченное количество камней. Игра завершается …
Е19-21.31 Игра завершается в тот момент, когда суммарное количество камней в кучах становится не менее 211.
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч (по своему выбору) один камень или увеличить количество камней в куче в два раза. Для того чтобы делать ходы, у каждого игрока …
Е19-21.30 когда количество камней в куче становится не менее 29
Игра завершается в тот момент, когда количество камней в куче становится не менее 29. Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один камень или увеличить количество камней в куче в два раза. …
Е19-21.29 когда суммарное количество камней в кучах становится не менее 44
когда суммарное количество камней в кучах становится не менее 44 Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч (по своему выбору) два камня или увеличить количество камней в куче в …
Е19-21.28 Игра завершается в тот момент, когда количество камней в куче становится не менее 84.
Игра завершается в тот момент, когда количество камней в куче становится не менее 84. Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один или четыре камня или увеличить количество камней в куче в …
Е19-21.27 добавить в кучу один камень, два камня, увеличить количество камней
добавить в кучу один камень, два камня, увеличить количество камней. Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может а) добавить в кучу один камень; б) добавить в кучу два камня; г) увеличить количество камней в куче …
Е19-21.26 добавить в кучу один камень, два камня, три камня; увеличить количество камней
добавить в кучу один камень, два камня, три камня; увеличить количество камней в куче в два раза. Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может а) добавить в кучу один камень; б) добавить в кучу два …
Е19-21.25 добавить в кучу два камня, добавить в кучу три камня или увеличить
добавить в кучу два камня, добавить в кучу три камня или увеличить. Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу два камня, добавить в кучу три камня или увеличить количество камней в куче …
Е19-21.24 добавить в кучу три камня или увеличить количество камней в куче в два раза
добавить в кучу три камня или увеличить количество камней в куче в два раза. Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу три камня или увеличить количество камней в куче в два раза. …
Е19-21.23 когда количество камней в куче становится не менее 25
Игра завершается в тот момент, когда количество камней в куче становится не менее 25. Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу два камня или увеличить количество камней в куче в два раза. …
Задача №19. Работа с массивами.
Массив – это тип или структура данных в виде набора компонентов (элементов массива), расположенных в памяти непосредственно друг за другом. При этом доступ к отдельным элементам массива осуществляется с помощью индексации, то есть ссылки на массив с указанием номера (индекса) нужного элемента. Размерность массива — это количество индексов, необходимое для однозначного доступа к элементу массива
Одномерный массив представляет собой пронумерованную последовательность элементов одного и того же типа, имеющих общее имя. Для обращения к элементу массива используют имя и порядковый номер элемента в квадратных скобках: A[i].
Двумерный массив представляет собой матрицу элементов одного и того же типа в которой элемент, расположенный на пересечении i-й строки и j-го столбца, обозначается A[i,j].
Одномерные массивы
В программе описан одномерный целочисленный массив A с индексами от 0 до 10. Ниже представлен фрагмент этой программы, записанный на разных языках программирования, в котором значения элементов массива сначала задаются, а затем меняются.
Бейсик
Паскаль
NEXT i
FOR i=1 TO 10
NEXT i
for i:=1 to 10 do
Си
Алгоритмический язык
for (i = 1; i <= 10; i++)
кц
нц для i от 1 до 10
кц
Как изменятся элементы этого массива после выполнения фрагмента программы?
1) все элементы, кроме последнего, окажутся равны между собой
2) все элементы окажутся равны своим индексам
3) все элементы, кроме последнего, будут сдвинуты на один элемент вправо
4) все элементы, кроме последнего, уменьшатся на единицу
Выполним последовательно все действия, описанные в программе. После первого цикла массив примет вид:
| Индекс | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| Значение | -1 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
Второй цикл сдвигает элементы массива на один влево:
А затем десятому элементу присваивается значение 10: A[10]:=10:
| Индекс | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| Значение | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
Правильный ответ указан под номером 2.
В программе используется одномерный целочисленный массив A с индексами от 0 до 9. Значения элементов равны 4, 7, 3, 8, 5, 0, 1, 2, 9, 6
соответственно, т.е. A[0] = 4, A[1] = 7 и т.д.
Определите значение переменной c после выполнения следующего фрагмента этой программы (записанного ниже на пяти языках программирования).
Если i-й элемент массива меньше нулевого, то программа меняет их местами и увеличивает значение переменной c на 1.
| Индекс | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| Значение | 4 | 7 | 3 | 8 | 5 | 0 | 1 | 2 | 9 | 6 |
Первый раз условие «i-й элемент массива меньше нулевого» выполнится при i=2. Массив примет вид:
| Индекс | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| Значение | 3 | 7 | 4 | 8 | 5 | 0 | 1 | 2 | 9 | 6 |
А переменная с примет значение 1.
Второй раз условие «i-й элемент массива меньше нулевого» выполнится при i=5. Массив примет вид:
| Индекс | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| Значение | 0 | 7 | 4 | 8 | 5 | 3 | 1 | 2 | 9 | 6 |
А переменная с примет значение 2.
Больше условие «i-й элемент массива меньше нулевого» не выполнится ни разу. Значит, с = 2.
В программе описаны одномерный целочисленный массив А с индексами от 0 до 10 и целочисленные переменные i и t. Ниже представлен фрагмент этой программы, записанный на разных языках программирования.
Бейсик
Паскаль
NEXT i
FOR i = 9 TO 0 STEP -1
NEXT i
for i := 9 downto 0 do
Си
Алгоритмический язык
for (i = 9; i >= 0; i—)
кц
нц для i от 9 до 0 шаг -1
кц
Чему окажутся равны элементы этого массива после выполнения фрагмента программы?
1) 10 0 0 0 0 0 0 0 0 0 0
2) 10 2 3 4 5 6 7 8 9 10 10
3) 10 10 10 10 10 10 10 10 10 10 10
4) 10 0 1 2 3 4 5 6 7 8 9
Выполним последовательно все действия, описанные в программе. После первого цикла массив примет вид:
| Индекс | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| Значение | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
Второй цикл работает в обратном порядке, от 9 до 0:
i = 9: A[10] := A[9] = 9,
А затем нулевому элементу присваивается значение 10 (A[0] := 10):
| Индекс | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| Значение | 10 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
Правильный ответ указан под номером 4.
Двумерные массивы
Значения элементов двумерного массива A размером 5×5 задаются с помощью вложенного цикла в представленном фрагменте программы:
for i:=1 tо 5 do
for j:=1 tо 5 do begin
A[i,j] := i*j;
end;
Сколько элементов массива будут иметь значения больше 10?
Выполним последовательно все действия, описанные в программе:
i=1 (Заполняем первую строку матрицы)
| 1 | 2 | 3 | 4 | 5 | |
| 1 | 1 | 2 | 3 | 4 | 5 |
| 2 | |||||
| 3 | |||||
| 4 | |||||
| 5 |
i=2 (Заполняем вторую строку матрицы)
| 1 | 2 | 3 | 4 | 5 | |
| 1 | 1 | 2 | 3 | 4 | 5 |
| 2 | 2 | 4 | 5 | 8 | 10 |
| 3 | |||||
| 4 | |||||
| 5 |
i=5 (Заполняем пятую строку матрицы)
Значение элементов матрицы равно произведению номеров его строки и столбца
| 1 | 2 | 3 | 4 | 5 | |
| 1 | 1 | 2 | 3 | 4 | 5 |
| 2 | 2 | 4 | 5 | 8 | 10 |
| 3 | 3 | 6 | 9 | 12 | 15 |
| 4 | 4 | 8 | 12 | 16 | 20 |
| 5 | 5 | 10 | 15 | 20 | 25 |
Значение больше 10 имеют 8 элементов матрицы.
Благодарим за то, что пользуйтесь нашими материалами. Информация на странице «Задача №19. Работа с массивами.» подготовлена нашими редакторами специально, чтобы помочь вам в освоении предмета и подготовке к ЕГЭ и ОГЭ. Чтобы успешно сдать нужные и поступить в высшее учебное заведение или техникум нужно использовать все инструменты: учеба, контрольные, олимпиады, онлайн-лекции, видеоуроки, сборники заданий. Также вы можете воспользоваться другими статьями из данного раздела.