ЕГЭ по информатике 2022 — Задание 2 (Ай да Питон!)
Продолжаем наш видеокурс по подготовке к ЕГЭ по информатике 2022. Сегодня разоблачим второе задание!
Кто незнаком с основными логическими операциями, можете посмотреть прошлогоднюю статью по заданию 2 из ЕГЭ по информатике.
В этой статье будут раскрыты методики решения 2 задания через язык программирования Питон.
Будем перебирать для каждой логической переменной все возможные варианты в программе. А логическая переменная всего два значения может принимать: 1 или 0 (истину или ложь). Таким образом, если к примеру у нас 4 переменные, мы получим 2 4 =16 различных комбинаций.
Кто знаком с мощнейшим методом для 2 задания из ЕГЭ по информатике, о котором я рассказывал в прошлогодней статье, тот поймёт, что мы будем применять тот же самый мощнейший метод, но автоматизированный с помощью питона.
Нам нужно будет запрограммировать логическую функцию на языке Питон. Вот таблица, которая поможет это сделать.
| Логическая операция | Представление в Питоне |
| Отрицание ¬ | not() |
| Логическое умножение ∧ | and |
| Логическое сложение ∨ | or |
| Следование A ⟶ B | not(A) or B |
| Равносильность ≡ | == |
Перейдём к практике решения задач задания 2 с помощью языка программирования Python.
Миша заполнял таблицу истинности логической функции F
но успел заполнить лишь фрагмент из трёх различных её строк, даже не указав, какому столбцу таблицы соответствует каждая из переменных w, x, y, z.
Определите, какому столбцу таблицы соответствует каждая из переменных w, x, y, z.
В ответе напишите буквы w, x, y, z в том порядке, в котором идут соответствующие им столбцы (сначала буква, соответствующая первому столбцу; затем буква, соответствующая второму столбцу, и т.д.). Буквы в ответе пишите подряд, никаких разделителей между буквами ставить не нужно.
Пример. Функция F задана выражением ¬x \/ y, зависящим от двух переменных, а фрагмент таблицы имеет следующий вид.
В этом случае первому столбцу соответствует переменная y, а второму столбцу – переменная x. В ответе следует написать: yx.
Решать задачу будем с помощью шаблона на языке Python (Питон).
В задаче у нас 4 переменные, значит, формируем 4 вложенных цикла. В каждом цикле перебираем все возможные значения для конкретной переменной. Мы перебираем значения 0 и 1.
Функция должна выдавать всегда 1 (единицу, истину). Внутри всех циклов прописываем условие, которое срабатывает как раз на истину. В этом условии прописываем нашу функцию. Если наша функция будет выдавать истину, то мы распечатаем значения переменных, при которых это произошло. Если функция будет выдавать ложь, значит, ничего распечатано не будет.
Четыре вложенных цикла проверяют все возможные варианты (2 4 = 16 вариантов), и мы получим таблицу истинности, почти такую же, как нам и дали в условии задачи.
Так же вверху печатаем названия переменных, чтобы знать, какие значения каким переменным принадлежат.
Запустим программу, и на экране распечатается табличка:
В получившийся табличке может быть больше строчек, чем в условии. Так же при поиске переменных нельзя опираться на порядок, в котором идут нули и единицы в нашей табличке. А можно опираться лишь на количество нулей и единиц в строчках или столбцах.
Можно вычеркнуть первую строчку и последнюю, потому что в таблице, которую дали в условии, в каждой строчке есть хотя бы один ноль и хотя бы одна единица.
Сразу видно, что первый столбец принадлежит переменной x, только там могут быть все единицы.
Второй столбец принадлежит переменной w, только там могут быть все нули.
У нас остались две пустые клеточки в самой таблице. Нам нужно где-то поставить единицу, а где-то ноль, потому что у нас остались столбцы с двумя единицами и одним нулём, а так же с двумя нулями и одной единицей. Если мы в третий столбец поставим единицу, а в четвёртый ноль, то первая строчка и вторая будут совпадать.
А в условии сказано, что строки не должны повторяться. Поэтому нужно ноль и единицу расставить наоборот.
Получается, что в третий столбец идёт z, а в четвёртый y
Ответ: xwzy
Посмотрим, как решать задачи второго задания из ЕГЭ по информатике, когда функция выдаёт нули в таблице истинности.
Задача (Классическая, закрепление)
Миша заполнял таблицу истинности функции (x ≡ ¬y) → ((x ∧ w) ≡ z), но успел заполнить лишь фрагмент из трёх различных её строк, даже не указав, какому столбцу таблицы соответствует каждая из переменных w, x, y, z.
Определите, какому столбцу таблицы соответствует каждая из переменных w, x, y, z.
В ответе напишите буквы w, x, y, z в том порядке, в котором идут соответствующие им столбцы (сначала буква, соответствующая первому столбцу; затем буква, соответствующая второму столбцу, и т.д.). Буквы в ответе пишите подряд, никаких разделителей между буквами ставить не нужно.
Пример. Функция F задана выражением ¬x \/ y, зависящим от двух переменных, а фрагмент таблицы имеет следующий вид.
В этом случае первому столбцу соответствует переменная y, а второму столбцу – переменная x. В ответе следует написать: yx.
Воспользуемся программой на языке Python.
От прошлой программы эта программа отличается только функцией!
В таблице видим, что функция должна выдавать ноль. Поэтому в условии мы функцию «оборачиваем» в not().
После == операцию not() мы заключили в скобки, чтобы не было синтаксической ошибки.
Получаем следующую таблицу истинности:
Разгадаем, где какая переменная находится.
Последнюю строку из нашей таблицы можно вычеркнуть, потому что, если мы вычеркнем другую строку, то не получится столбца, где все три единицы, а он должен быть.
Получается, что второй столбец достаётся переменной z.
В первом столбце должно быть две единицы. На эту роль подходит переменная y.
В нашей таблице нет строчки, где все единицы, значит, во второй строчке в пустом окошке выставляем ноль. И в этой строчке нулём обладает переменная x. Следовательно, в третьем столбце будет находится x.
А в последний столбец идёт переменная w по остаточному принципу.
Ответ: yzxw
А как Питон справится с более сложной функцией из примерного варианта ЕГЭ по информатике?
Задача (Сложная функция)
Логическая функция F задаётся выражением ((x → y ) ∧ (y → w)) ∨ (z ≡ ( x ∨ y)).
Дан частично заполненный фрагмент, содержащий неповторяющиеся строки таблицы истинности функции F. Определите, какому столбцу таблицы истинности соответствует каждая из переменных x, y, z, w.
В ответе напишите буквы x, y, z, w в том порядке, в котором идут соответствующие им столбцы (сначала — буква, соответствующая первому столбцу; затем — буква, соответствующая второму столбцу, и т. д.). Буквы в ответе пишите подряд, никаких разделителей между буквами ставить не нужно.
Пример. Пусть задано выражение x → y, зависящее от двух переменных x и y, и фрагмент таблицы истинности:
Тогда первому столбцу соответствует переменная y, а второму столбцу соответствует переменная x. В ответе нужно написать: yx.
Запрограммируем функцию на языке Python.
Запустим программу и расставим переменные по своим местам.
Переменная z может быть только в третьем столбце.
Во второй столбец идёт переменная w, только этот столбец может иметь одну единицу.
Посмотрим на строчку, где у w стоит единица. В этой же строчке и у x единица. Значит, x идёт в последний столбец, а y в первый столбец.
Ответ: ywzx
Тот же шаблон работает, когда у нас во втором задании три переменные.
(№ 1608) Логическая функция F задаётся выражением (¬x ∧ z) ∨ (¬x ∧ ¬y ∧ ¬z)
На рисунке приведён фрагмент таблицы истинности функции F, содержащий все наборы аргументов, при которых функция F истинна. Определите, какому столбцу таблицы истинности функции F соответствует каждая из переменных x, y, z.
Для трёх переменных шаблон на Питоне отлично работает.
Здесь и так понятно, куда какая переменная идёт.
Ответ: yxz
Посмотрим, как решать задачи из второго задания ЕГЭ по информатике, когда в таблице истинности разные значения у функции F.
Задача (Разные значения функции)
Логическая функция F задаётся выражением (¬a ∨ b ∨ ¬c) ∧ (b ∨ ¬c). Определите, какому столбцу таблицы истинности функции F соответствует каждая из переменных a, b, c.
В ответе напишите буквы a, b, c в том порядке, в котором идут соответствующие им столбцы (без разделителей).
Источник задачи сайт К. Ю. Полякова: https://kpolyakov.spb.ru/
Когда такая ситуация, что функция имеет различные значения в таблице, мы можем проверить, какие значения переменных дают единицу у всей функции. А потом проверить, какие значения выдают ноль у всей функции, если это потребуется.
В таблице 6 строчек, в которых главная функция превращается в единицу. Далее эти строчки и будем рассматривать. У нас тоже получилось 6 строчек.
Переменная a имеет три единицы. Это второй столбец, потому что там три единицы.
Переменная b имеет четыре единицы, значит, она расположена в первом столбце.
Переменной c достаётся последний столбец.
Ещё одна интересная задача для подготовки к ЕГЭ по информатике 2022.
Логическая функция F задаётся выражением a ≡ b ∨ b → c.
На рисунке приведён частично заполненный фрагмент таблицы истинности функции F, содержащий неповторяющиеся строки. Определите, какому столбцу таблицы истинности функции F соответствует каждая из переменных a, b, c.
Источник задачи группа Евгения Джобса: https://vk.com/inform_web
Подвох заключается в том, что если мы переведём бездумно функцию на язык Питон, то получится a==b or not (b) or c. Но у нас существуют приоритеты для логических операций, которые описаны в прошлогодней статье по подготовке к ЕГЭ по информатике.
В начале должно обрабатываться или, которое было изначально. Затем должно обработаться следование, а потом равносильность. А если мы переведём формулу бездумно, порядок будет не правильный.
Операцию b ∨ b можно представить, как просто b. Ведь, если b принимает значение 0, тогда будет 0 ∨ 0 = 0. Если значение будет 1, то 1 ∨ 1 = 1. Поэтому формулу можно переписать следующим образом:
a ≡ b → c
a == ( not (b) or c)
В предыдущих задачах нам не приходилось думать над приоритетами, потому что везде были расставлены скобки. И в основном они уже расставлены в задачах второго задания из ЕГЭ по информатике.
Дальше решаем как обычно.
Последнюю строчку можно вычеркнуть из нашей таблицы, т.к. у нас в каждой строчке есть хотя бы один ноль.
Последний столбец занимает переменная a, т.к. только в последний столбец может влезть две единицы.
В строчке, где у a ноль, так же ноль и у переменной c. Значит, во второй столбец идёт переменная c. Если мы ноль поставим в первой строчке в первом столбце, то получится первый столбец из всех нулей. А такого у нас в таблице истинности нет.
Задание 17 ЕГЭ по информатике и примеры решения на Python (задания _ Евич Информатика Подготовка к ЕГЭ 2023 14 тренировочных варианта по демоверсии 2023 г)
f=open(’17_1.txt’)
a=[int(x) for x in f]
minimum=min(a)
k=0
max_summa=0
s1=0
k1=0
for i in range(len(a)):
if a[i]%4==0:
s1+=a[i]
k1+=1
sr_ar=s1/k1
for i in range(len(a)-1):
if (a[i]%minimum==0 and a[i]+a[i+1]or (a[i+1]%minimum==0 and a[i]+a[i+1] k=k+1
max_summa=max(max_summa,a[i]+a[i+1])
print(k,max_summa)
Ответ: 1428 829
f=open(’17_2.txt’)
a=[int(x) for x in f]
maximum=max(a)
k=0
min_summa=10000000000000
s1=0
k1=0
for i in range(len(a)):
if a[i]%10==3:
s1+=a[i]
k1+=1
sr_ar=s1/k1
for i in range(len(a)-1):
if (maximum%a[i]==0 and a[i]+a[i+1]sr_ar) or (maximum%a[i+1]==0 and a[i]+a[i+1]sr_ar):
k=k+1
min_summa=min(min_summa,a[i]+a[i+1])
print(k,min_summa)
Ответ: 72 795
f=open(’17_3.txt’)
a=[int(x) for x in f]
k=0
max_summa=0
for i in range(len(a)-1):
if a[i]%5==0 and a[i+1]%5==0:
k=k+1
max_summa=max(max_summa,a[i]+a[i+1])
print(k,max_summa)
Ответ: 213 965
f=open(’17_4.txt’)
a=[int(x) for x in f]
k=0
min_summa=10000000000000
for i in range(len(a)-1):
if a[i]%20 or a[i+1]%20:
k=k+1
min_summa=min(min_summa,a[i]+a[i+1])
print(k,min_summa)
Ответ: 3741 -973
def h(ch):
k6 = 0
while ch0:
ost=ch%10
if ost==6:
k6=k6+1
ch=ch//10
return k6
f=open(’17_5.txt’)
a=[int(x) for x in f]
k=0
m=1000000000000000
for i in range(len(a)):
if h(abs(a[i]))0:
k=k+1
m=min(a[i],m)
print(k,m)
Ответ: 935 -496
def h(ch):
k4 = 0
while ch0:
ost=ch%10
if ost==4:
k4=k4+1
ch=ch//10
return k4
f=open(’17_6.txt’)
a=[int(x) for x in f]
k=0
m=0
for i in range(len(a)):
if h(abs(a[i]))0:
k=k+1
m=max(a[i],m)
print(k,m)
Ответ: 1753 499
f=open(’17_7.txt’)
a=[int(x) for x in f]
k=0
max_razn=0
for i in range(len(a)-1):
if a[i]a[i+1]:
k=k+1
max_razn=max(max_razn,a[i]-a[i+1])
print(k,max_razn)
Ответ: 2514 963
f=open(’17_8.txt’)
a=[int(x) for x in f]
k=0
min_razn_kv=100000000000
for i in range(len(a)-1):
if a[i]0 and a[i+1]0 and a[i+1]a[i]:
k=k+1
min_razn_kv=min(min_razn_kv,a[i+1]**2-a[i]**2)
print(k,min_razn_kv)
Ответ: 670 171
f=open(’17_9.txt’)
a=[int(x) for x in f]
m=0
k=0
for i in range(len(a)):
if a[i]%4==0 and a[i]%5!=0 and a[i]%8!=0 and a[i]%31!=0 and a[i]%41!=0:
k=k+1
m=max(m,a[i])
print(m,k)
Ответ: 9572 381
f=open(’17_10.txt’)
a=[int(x) for x in f]
m=100000000000
k=0
for i in range(len(a)):
if a[i]%7==0 and a[i]%5==0 and a[i]%2!=0 and a[i]%11!=0 and a[i]%91!=0:
k=k+1
m=min(m,a[i])
print(m,k)
Ответ: -8785 43
f=open(’17_11.txt’)
a=[int(x) for x in f]
k=0
b=[]
for i in range(len(a)):
if a[i]%2==0 and a[i]%30:
k=k+1
b.append(a[i])
b.sort(reverse=True)
print(k,b[1])
Ответ: 1299 9664
f=open(’17_12.txt’)
a=[int(x) for x in f]
k=0
b=[]
for i in range(len(a)):
if a[i]%3==0 and a[i]%20:
k=k+1
b.append(a[i])
b.sort()
print(k,b[1])
Ответ: 669 -9777
f=open(’17_13.txt’)
a=[int(x) for x in f]
k=0
m=100000000000000000
a=a[1:]
a=a[:-1]
for i in range(len(a)-2):
if a[i+1]a[i] and a[i+1]a[i+2]:
k=k+1
m=min(m,a[i+1])
print(k,m)
Ответ: 1335 -8615
f=open(’17_14.txt’)
a=[int(x) for x in f]
k=0
m=0
a=a[1:]
a=a[:-1]
for i in range(len(a)-2):
if a[i+1]or a[i+1]2] or a[i+1]and a[i+1]2]:
k=k+1
m=max(m,a[i+1])
print(k,m)
Теория игр, информатика и питон. Задачи ЕГЭ 19-21.
В задачах 19-21 ЕГЭ по информатике требуется проанализировать некую простую игру. Однако хотя игра и проста, её анализ может оказаться достаточно хитрым делом. Поэтому приходит мысль: а нельзя ли, чтобы этот анализ выполнил компьютер? (Спойлер: Можно!)
Немного теории.
Основную идею, лежащую в основе теории игр, подобных описанным в задачах ЕГЭ, можно выразить в двух словах: игроки умные. Это означает, что если у кого-то из игроков в текущей позиции есть возможность сделать выигрышный ход, то он этот ход сделает.
Таким образом, если в текущей позиции у игрока есть хотя бы один ход, ведущий к выигрышу, то это — выигрышная позиция для данного игрока.
Если же в ответ на любой ход текущего игрока его противник выигрывает, то для текущего игрока такая ситуация — проигрышная.
Теперь более-менее понятно, как должна выглядеть программа, анализирующая ход игры. Прежде всего она должна проверить, не выиграл ли уже кто-то из игроков. Если это так — то дальнейший анализ позиции не требуется.
Затем нужно просмотреть все возможные ходы текущего игрока. Если них есть хоть один выигрышный для него — в данной позиции он выиграл. Если же при любом его ходе выигрывает его противник — то можно считать, что данный игрок уже проиграл.
Если же неверно ни первое, ни второе — то ситуация неопределенная.(Вообще-то для игр из задач ЕГЭ всегда можно сказать, кто из игроков выиграет, такая неопределенность возникает только из-за ограничения на число ходов.)
Данную процедуру следует рекурсивно применять к позициям, возникающим по ходу игры.
А теперь — практика.
Решим программно задачи 19-21 из 8 варианта с сайта Полякова. Условие выглядит следующим образом:
Приведем текст рекурсивной функции hod на языке Питон, которая по сути и решает данную задачу.
def hod(number,limit,s):
player = (number+1)%2 + 1 # номер текущего игрока (1 или 2)
rival = 3 — player # Номер его противника (2 или 1)
#Анализ позиции
if s >= 43 and s <= 72: return rival # текущий игрок проиграл
if s > 72 : return player # проиграл противник
if number > limit: return 0 # ситуация неопределенная из-за ограничений на количество ходов
# Делаем ходы и проверяем результаты
rc1 = hod(number+1,limit,3*s)
if rc1 == player: return player
rc2 = hod(number+1,limit,2*s)
if rc2 == player: return player
rc3 = hod(number+1,limit,s+1)
if rc3 == player: return player
if rc1 == rival and rc2 == rival and rc3 == rival: return rival
Функция имеет три параметра: number (номер хода), limit (ограничение на количество ходов) и s (количество камней в куче). При первом обращении следует задавать значение number, равное 1 (т.е. ходы мы нумеруем с единицы).
Переменная player принимает значение 1 для нечетных номеров ходов (т.е. ходы 1, 3 и т.д. совершает первый игрок) и значение 2 — для четных номеров. Переменная rival, наоборот, равна 2 для нечетных номеров ходов и 1 — для четных. Таким образом, player — это номер игрока, который делает текущий ход, а rival — номер его противника.
Прежде всего функция проверяет, не завершилась ли игра. Если число камней S не менее 43 и не более 72, то это означает, что текущий игрок проиграл: перед этим его противник сделал победный ход. Функция завершается, вернув значение rival. Если же число камней более 72, то соперник текущего игрока только что сделал проигрышный для себя ход, и выиграл текущий игрок. Программа возвращает значение player.
Далее проверяется ограничение на число ходов. Если это ограничение превышено (number>limit), то дальнейшие ходы не выполняются и программа возвращает значение 0 (т.е. победитель не определён).
Далее осуществляются рекурсивные вызовы функции hod с параметром number+1 (т.е. номер хода увеличен на единицу), с тем же самым значением limit и числом камней в куче 3S, 2S и S+1 (согласно условиям задачи).
Рекомендую сначала проверять значения, как можно сильнее отличающиеся от исходного (т.е. 3S и 2S) и потом S+1. Это позволяет уменьшить число вершин «дерева игры», которые анализирует программа. С этой же целью программа, обнаружив выигрышный для текущего игрока ход (т.е. результат вызова функции равен player), немедленно возвращает значение player и не выполняет дальнейших проверок ходов.
Если все три результата ходов равны rival, то в данной позиции все ходы текущего игрока приводят к его проигрышу, и программа возвращает значение rival.
Если же для текущего игрока нет ни одного выигрышного хода, но у него есть ходы, не приводящие к его проигрышу, то ситуация неопределённая, и программа возвращает 0.
Теперь проведем анализ данной игры и получим ответы на заданные в задаче вопросы.
Первый вопрос: каково минимальное значение S, при котором второй игрок выигрывает своим первым ходом? Для ответа на него достаточно вызвать функцию для всех значений S таких, что 1<=S<=42, с ограничением на количество ходов, равным 2 (т.е. игроки делают по одному ходу). Если функция hod вернет значение, равное 2, то при данном начальном значении S второй игрок выигрывает в любом случае.
Второй вопрос: сколько имеется значений S, при которых первый игрок не может выиграть своим первым ходом, но гарантированно выигрывает вторым?
Для этого надо запустить программу два раза, первый раз с ограничением на число ходов 1, а второй раз — с ограничением 3. Если в первом случае программа вернет значение 0 (нет победителя), а второй — 1, то при данном S первый игрок не может гарантированно выиграть своим первым ходом, но непременно выигрывает вторым. Вместо ограничений 1 и 3 можно взять 2 и 4: дополнительный ход второго игрока (если он возможен) ничего не меняет.
Наконец, последний вопрос: при каких значениях S второй игрок не может гарантированно выиграть первым ходом, но обязательно выиграет вторым? Для этого надо опять запустить функцию дважды, с ограничением на число ходов 2 и 4. Если в первом случае функция вернет 0, а во втором — 2, то это искомое значение.
Вот программа, которая выполняет данные проверки:
for s in range(1,43):
h2 = hod(1,2,s)
h4 = hod(1,4,s)
rez = »
if h2 == 2: rez = ‘*** 19 ***’
if h2 == 0:
if h4 == 1: rez = ‘*** 20 ***’
if h4 == 2: rez = ‘*** 21 ***’
print(s,h2, h4, rez)
Результат выполнения программы следующий (из него исключены строки, которые не дают ответов не поставленные вопросы):
7 0 1 *** 20 ***
12 0 2 *** 21 ***
13 0 1 *** 20 ***
14 2 2 *** 19 ***
39 0 2 *** 21 ***
40 0 1 *** 20 ***
41 2 2 *** 19 ***
Следовательно, ответы на вопросы задачи таковы:
Вопрос 1: такие значения — 14 и 41, минимальное — 14.
Вопрос 2: такие значения — 7, 13 и 40, всего их 3.
Вопрос 3: такие значения — 12 и 39. Минимальное — 12, а максимальное — 39.
А теперь решим задачи 19-21 из демонстрационного варианта ФИПИ 2022 г.
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один камень или увеличить количество камней в куче в два раза. Для того чтобы делать ходы, у каждого игрока есть неограниченное количество камней.
Игра завершается в тот момент, когда количество камней в куче становится не менее 29. Победителем считается игрок, сделавший последний ход, т.е. первым получивший кучу, в которой будет 29 или больше камней.
В начальный момент в куче было S камней, 1 ≤ S ≤ 28.
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника.
19. Укажите такое значение S, при котором Петя не может выиграть за один ход, но при любом ходе Пети Ваня может выиграть своим первым ходом.
20. Для игры, описанной в задании 19, найдите два таких значения S, при которых у Пети есть выигрышная стратегия, причём одновременно выполняются два условия:
− Петя не может выиграть за один ход;
− Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.
Найденные значения запишите в ответе в порядке возрастания.
21. Для игры, описанной в задании 19, найдите значение S, при котором одновременно выполняются два условия:
− у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;
− у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.
Если найдено несколько значений S, в ответе запишите минимальное из них.
Вопросы по сути те же, что и в задаче с сайта Полякова, однако правила игры другие.
Перепишем функцию hod для данных правил:
def hod(number,limit,s):
player = (number+1)%2 + 1 # номер текущего игрока (1 или 2)
rival = 3 — player # Номер его противника (2 или 1)
#Анализ позиции
if s >= 29: return rival # текущий игрок проиграл
if number > limit: return 0 # ситуация неопределенная из-за ограничений на количество ходов
# Делаем ходы и проверяем результаты
rc1 = hod(number+1,limit,2*s)
if rc1 == player: return player
rc2 = hod(number+1,limit,s+1)
if rc2 == player: return player
if rc1 == rival and rc2 == rival: return rival
Основная программа выглядит так же, как и в предыдущем случае. Единственное изменение — вместо range(1,43) в ней записано range(1,29).
Результат выполнения программы следующий (в нём опять-таки опущены несущественные строки):
7 0 1 *** 20 ***
12 0 2 *** 21 ***
13 0 1 *** 20 ***
14 2 2 *** 19 ***
Отсюда видно, что ответ на задачу 19 — 14, на задачу 20 — 7 и 13, а на задачу 21 — 12. Это совпадает с приведенными в варианте ответами.
Если Петя глуповат.
При составлении программы мы предполагали, что игроки — умные и ошибочных ходов не делают. Но на сайте «Решу ЕГЭ» очень часто встречаются задачи, где один из игроков дает маху. Вот пример задачи 19 (задача 27416):
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч (по своему выбору) один камень или увеличить количество камней в куче в два раза. Например, пусть в одной куче 10 камней, а в другой 5 камней; такую позицию в игре будем обозначать (10, 5). Тогда за один ход можно получить любую из четырёх позиций: (11, 5), (20, 5), (10, 6), (10, 10). Для того чтобы делать ходы, у каждого игрока есть неограниченное количество камней.
Игра завершается в тот момент, когда суммарное количество камней в кучах становится не менее 77. Победителем считается игрок, сделавший последний ход, т. е. первым получивший такую позицию, при которой в кучах будет 77 или больше камней.
В начальный момент в первой куче было семь камней, во второй куче — S камней; 1 ≤ S ≤ 69.
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока — значит, описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника. В описание выигрышной стратегии не следует включать ходы играющего по этой стратегии игрока, не являющиеся для него безусловно выигрышными, т. е. не являющиеся выигрышными независимо от игры противника.
Известно, что Ваня выиграл своим первым ходом после неудачного первого хода Пети. Укажите минимальное значение S, когда такая ситуация возможна.
Сначала напишем нашу функцию hod для данной задачи: она всё равно потребуется для задач 20 и 21. Впрочем, отличий от первого варианта не так много. Во-первых, так как у нас теперь две кучи, у функции есть два параметра s1 и s2: число камней в первой и второй кучах. Условие завершения игры теперь выглядит так: s1+s2>=77. Так как теперь у каждого игрока есть четыре возможных хода, то проверяется не три, а четыре альтернативы.
def hod(number,limit,s1,s2):
player = (number+1)%2 + 1 # номер текущего игрока (1 или 2)
rival = 3 — player # Номер его противника (2 или 1)
#Анализ позиции
if s1+s2 >= 77: return rival # текущий игрок проиграл
if number > limit: return 0 # ситуация неопределенная из-за ограничений на количество ходов
# Делаем ходы и проверяем результаты
rc1 = hod(number+1,limit,2*s1,s2)
if rc1 == player: return player
rc2 = hod(number+1,limit,s1,2*s2)
if rc2 == player: return player
rc3 = hod(number+1,limit,s1+1,s2)
if rc3 == player: return player
rc4 = hod(number+1,limit,s1,s2+1)
if rc4 == player: return player
if rc1 == rival and rc2 == rival and rc3 == rival and rc4 == rival: return rival
Но как быть с тем, что наша функция предполагает безошибочную игру, а условие задачи подразумевает, что первый игрок сделал ошибочный ход? А очень просто: надо вызвать функцию четыре раза с позициями, которые могут получиться после первого хода Пети. В параметрах функции надо указать, что это — второй ход, и задать ограничение на количество ходов, равное двум. Если хотя бы в одном случае функция даст ответ, что выиграл второй игрок, то это и будет ответом на вопрос задачи.
Таким образом, основная программа выглядит так:
s1=7
for s2 in range(1,70):
if hod(2,2,s1*2,s2)==2 or hod(2,2,s1,s2*2)==2 or hod(2,2,s1+1,s2)==2 or hod(2,2,s1,s2+1)==2:
print(s2)
break
Она дает правильный ответ: 18 камней.
Когда основная функция написана, не представляет сложности решить задачи 20 и 21. Вот их вопросы (правила игры, естественно, те же самые):
20: Найдите два таких значения S, при которых у Пети есть выигрышная стратегия, причём одновременно выполняются два условия:
— Петя не может выиграть за один ход;
— Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.
21: Найдите минимальное значение S, при котором одновременно выполняются два условия:
— у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;
— у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.
Основная программа опять-таки похожа на первый вариант, отличия незначительные:
s1=7
for s2 in range(1,70):
h2 = hod(1,2,s1,s2)
h4 = hod(1,4,s1,s2)
rez = »
if h2 == 0:
if h4 == 1: rez = ‘*** 20 ***’
if h4 == 2: rez = ‘*** 21 ***’
print(s2,h2, h4, rez)
Результат работы программы (опять-таки опущены несущественные строки):
30 0 2 *** 21 ***
31 0 1 *** 20 ***
33 0 2 *** 21 ***
34 0 1 *** 20 ***
Таким образом, ответ на вопрос задачи 20 — это 31 и 34, а на вопрос задачи 21 — 30 (напомню, что там требуется минимальное значение из двух ответов: 30 и 33).
Итак, мы убедились, что задачи 19-21 ЕГЭ по информатике можно решить программно, и решение — не слишком сложное.
Name already in use
If nothing happens, download GitHub Desktop and try again.
Launching GitHub Desktop
If nothing happens, download GitHub Desktop and try again.
Launching Xcode
If nothing happens, download Xcode and try again.
Launching Visual Studio Code
Your codespace will open once ready.
There was a problem preparing your codespace, please try again.
Latest commit
Git stats
Files
Failed to load latest commit information.
README.md
Решение заданий ЕГЭ по информатике на языке программирования Python. Задания взяты отсюда:
About
Решение заданий егэ по информатике на языке программирования Python. Задания взяты отсюда: https://www.kpolyakov.spb.ru/school/ege/generate.htm https://inf-ege.sdamgia.ru/
Resources
Stars
Watchers
Forks
Releases
Packages 0
Contributors 2
Languages
Footer
© 2023 GitHub, Inc.
You can’t perform that action at this time.
You signed in with another tab or window. Reload to refresh your session. You signed out in another tab or window. Reload to refresh your session.