Продолжаем подготовку к ЕГЭ по информатике 2023 года. Разбираем задания, присланные подписчиками. Ссылки для отправки собственных заданий находятся в описании.
Задание 19: Теория игр (две кучи камней)
Условие: Два игрока, Петя и Ваня, играют в игру с двумя кучами камней. В начальный момент в первой куче 2 камня, во второй – S камней. За один ход игрок может добавить в одну из куч 2 камня или удвоить количество камней в куче. Игра заканчивается, когда суммарное количество камней в кучах ≥ 142. Побеждает игрок, сделавший последний ход. Ваня выиграл своим первым ходом после неудачного первого хода Пети. Необходимо найти минимальное значение S, при котором такая ситуация возможна.
Решение: Задачи на теорию игр с двумя кучами камней удобнее решать программно, используя рекурсию. Ход Пети – нечётные ходы (1, 3, 5…), а ход Вани – чётные (2, 4, 6…). Необходимо написать рекурсивную функцию, моделирующую игру.
Рекурсивная функция:
Функция f(x, y, h) принимает на вход:
- x – количество камней в первой куче;
- y – количество камней во второй куче;
- h – номер хода.
def f(x, y, h):
if x + y >= 142:
return h == 2 # Ваня выиграл своим первым ходом (ход №2)
if h > 2:
return False # Превышен необходимый ход
return (f(x + 2, y, h + 1) or f(x * 2, y, h + 1) or
f(x, y + 2, h + 1) or f(x, y * 2, h + 1))Функция проверяет все возможные ходы и возвращает True, если Ваня выиграл своим первым ходом, и False в противном случае.
Поиск минимального S:
min(i for i in range(1, 139) if f(2, i, 1))Перебираем значения S от 1 до 138 и находим минимальное, при котором функция f(2, S, 1) возвращает True. Результат – 35.
Задание 20: Теория игр (два наименьших значения S)
Условие: Найти два наименьших значения S, при которых Петя имеет выигрышную стратегию, но не может выиграть за один ход. Петя должен выиграть своим вторым ходом (ход №3 в игре).
Решение: Модифицируем рекурсивную функцию:
def f(x, y, h):
if x + y >= 142:
return h == 3 # Петя выигрывает на третьем ходе
if h % 2 != 0: # Ход Пети
return f(x + 2, y, h + 1) and f(x * 2, y, h + 1) and f(x, y + 2, h + 1) and f(x, y * 2, h + 1)
else: # Ход Вани
return f(x + 2, y, h + 1) or f(x * 2, y, h + 1) or f(x, y + 2, h + 1) or f(x, y * 2, h + 1)Результат: 67 и 68.
Задание 21: Теория игр (минимальное значение S)
Условие: Найти минимальное значение S, при котором Ваня имеет выигрышную стратегию, позволяющую ему выиграть первым или вторым ходом (ход №2 или №4) при любой игре Пети.
Решение: Модифицируем рекурсивную функцию:
def f(x, y, h):
if x + y >= 142:
return h == 2 or h == 4 # Ваня выигрывает на втором или четвёртом ходе
if h % 2 == 0: # Ход Вани
return f(x + 2, y, h + 1) and f(x * 2, y, h + 1) and f(x, y + 2, h + 1) and f(x, y * 2, h + 1)
else: # Ход Пети
return f(x + 2, y, h + 1) or f(x * 2, y, h + 1) or f(x, y + 2, h + 1) or f(x, y * 2, h + 1)Результат: 66.
Задание 24: Подсчёт символов в файле
Условие: Определить максимальное количество подряд идущих символов в файле, среди которых символ ‘a’ встречается не более трёх раз.
Решение: Алгоритм предполагает считывание содержимого файла в строку s и нахождение индексов всех вхождений символа ‘a’ в список a_indices. Далее ищется максимальная длина последовательности, проверяя количество ‘a’ в подстроках. Представленный код неполный и требует доработки для считывания файла и нахождения индексов ‘a’. Поэтому результат (5001) приведён без подтверждающего кода.
Задание 25: Делители числа
Условие: Найти первые пять чисел, больших 860000, разность максимального и минимального делителей которых (исключая 1 и само число) оканчивается на 18.
Решение:
k = 0
i = 860001
while k < 5:
divs = set()
for j in range(2, int(i**0.5) + 1):
if i % j == 0:
divs.add(j)
divs.add(i // j)
if divs:
m = max(divs) - min(divs)
if m % 100 == 18:
print(i, m)
k += 1
i += 1Программа перебирает числа, начиная с 860001, находит их делители, вычисляет разность между максимальным и минимальным делителями и проверяет, оканчивается ли она на 18. Выводит первые пять найденных чисел и соответствующие значения M.
Приведенные решения демонстрируют применение рекурсии и итераций для решения задач на теорию игр и обработку данных. Знание программирования существенно упрощает решение подобных задач на ЕГЭ по информатике.