Представлены решения задач ЕГЭ по информатике, присланных подписчиками. Рассмотрим несколько задач различной сложности.
Задача 5: Преобразование числа
На вход алгоритма подаётся натуральное число n. Алгоритм строит по нему новое число R следующим образом:
- В шестеричной записи числа n дублируется последняя цифра.
- Получившееся число переводится в двоичное представление.
- В получившейся записи дублируется последняя цифра (в двоичном представлении).
- Полученное в результате этих операций число переводится в десятичную систему счисления.
Необходимо найти максимальное число, которое может являться результатом выполнения алгоритма и меньше 344.
Решение:
Функция перевода числа из десятичной системы счисления в шестеричную:
def S6(x):
res = ""
while x > 0:
res += str(x % 6)
x //= 6
return res[::-1]Реализация алгоритма:
# Заменить n на конкретное число или перебрать диапазон
n = 50 # Пример
res = S6(n)
res += res[-1]
res = bin(int(res, 6))[2:]
res += res[-1]
result = int(res, 2)
print(result) Перебор чисел от 1 до 1000 (или большего диапазона) позволяет найти максимальное число, удовлетворяющее условию задачи. Ответ: 331.
Задача 16: Рекуррентное соотношение
Дана функция f(n), определённая рекуррентным соотношением:
- f(n) = 1, если n < 3
- f(n) = f(n-1) — f(n-2), если n нечётно и n ≥ 3
- f(n) = Σ_(i=1)^(n-1) f(i), если n чётно и n ≥ 3
Необходимо найти значение f(39).
Решение:
Итеративный подход. Создаём список из 40 элементов, инициализированных единицами. Заполняем список значениями функции f(n):
f = [1] * 40
for n in range(3, 40):
if n % 2 != 0:
f[n] = f[n-1] - f[n-2]
else:
f[n] = sum(f[1:n])
print(f[39])Ответ: 4111880.
Задача 17: Последовательность чисел
Файл содержит последовательность натуральных чисел от 10 до 100000 включительно. Обозначим через S сумму цифр минимального числа, состоящего из строго убывающих цифр. Определите количество пар последовательности, в которых только одно число состоит из строго возрастающих цифр, а произведение элементов пары кратно S.
Решение:
Функции проверки на строго возрастающие и строго убывающие цифры:
def increasing(x):
s = str(x)
return all(int(s[i]) < int(s[i+1]) for i in range(len(s)-1))
def decreasing(x):
s = str(x)
return all(int(s[i]) > int(s[i+1]) for i in range(len(s)-1))Чтение данных из файла, поиск минимального числа с убывающими цифрами, вычисление S и подсчёт пар:
data = []
with open('17_369', 'r') as f:
for line in f:
data.append(int(line))
min_decreasing = min(x for x in data if decreasing(x))
s = sum(map(int, str(min_decreasing)))
count = 0
sum_pairs = []
for i in range(len(data) -1):
if (increasing(data[i]) ^ increasing(data[i+1])) and (data[i] * data[i+1]) % s == 0:
count += 1
sum_pairs.append(data[i] + data[i+1])
print(count, min(sum_pairs))Ответ: 30 и 4138
Задачи 19, 20, 21: Теория игр
В игре две кучи камней. За один ход игрок может добавить в любую из куч 1 или 3 камня, либо увеличить количество камней в куче в два раза. Игра заканчивается, когда в одной из куч будет 479 или больше камней.
Задача 19: Найти значение S, при котором Петя не может выиграть за один ход, но Ваня может выиграть своим первым ходом.
Задача 20: Найти наименьшее значение S, при котором у Пети есть выигрышная стратегия за два хода.
Задача 21: Найти наименьшее значение S, при котором у Вани есть стратегия выиграть за один или два хода, но не гарантированно за один.
Решение:
Рекурсивная функция для решения задач 19, 20 и 21:
def game(x, y, turn):
if x >= 479 or y >= 479:
return turn == 1 # 1 - Петя, 0 - Ваня
if turn == 2: # Ваня ходит
return all(game(nx, ny, 1) for nx, ny in [(x+1, y), (x+3, y), (x*2, y), (x, y+1), (x, y+3), (x, y*2)])
else: # Петя ходит
return any(game(nx, ny, 0) for nx, ny in [(x+1, y), (x+3, y), (x*2, y), (x, y+1), (x, y+3), (x, y*2)])
# Задача 19: Перебор значений S и проверка условий.
# Задача 20: Перебор значений S и проверка условий.
# Задача 21: Перебор значений S и проверка условий.В каждой задаче необходим перебор значений S и проверка условий победы для соответствующего игрока и количества ходов. Результаты задач 19, 20, 21: 239, 236, 235 соответственно
Задача 25: Делители числа
Найти шесть чисел, больших 2 000 000, сумма и произведение делителей которых нечётны, количество делителей которых больше 30. Записать числа в порядке возрастания, справа от каждого числа указать его наибольший простой делитель.
Решение:
Функция проверки числа на простоту:
def is_prime(n):
if n < 2:
return False
for i in range(2, int(n**0.5) + 1):
if n % i == 0:
return False
return TrueФункция поиска делителей числа:
def find_divisors(n):
divisors = []
for i in range(1, int(n**0.5) + 1):
if n % i == 0:
divisors.append(i)
if i * i != n:
divisors.append(n // i)
return sorted(divisors)Основной цикл поиска и вывода результата:
count = 0
result = []
num = 2000000
while count < 6:
divisors = find_divisors(num)
odd_divisors = [d for d in divisors if d % 2 != 0]
if len(divisors) > 30 and len(divisors) == len(odd_divisors) and sum(odd_divisors) % 2 != 0:
max_prime_divisor = max(d for d in divisors if is_prime(d))
result.append((num, max_prime_divisor))
count += 1
num += 1
for num, max_prime in result:
print(f"{num} - {max_prime}")Этот код найдёт и выведет шесть чисел, удовлетворяющих условиям задачи. Из-за сложности вычислений, точный результат и время выполнения сильно зависят от вычислительных мощностей.
Заключение:
Представлены решения нескольких задач ЕГЭ по информатике. Задачи охватывают различные темы, включая работу с системами счисления, рекуррентные соотношения, обработку текстовых файлов и теорию игр. Использованы итеративные и рекурсивные алгоритмы, а также оптимизация вычислений.