ЕГЭ Задание 23
Анализ графов
Штана Альберт Игоревич
УСТАРЕЛИ Типы заданий № 23 (Актуально для задания № 13)
В этой статье будет разобрано задание 23.
Рассмотрим типовые задачи из двадцать третьего задания ЕГЭ по информатике.
Данное задание относится к повышенному уровню сложности.
Время выполнения задания ≈ 8 минут.
Данное задание проверяет умение анализировать ход исполнения алгоритма. Решение программируется на Python.
Задача 1 (Демоверсия 2024)
Исполнитель преобразует число на экране. У исполнителя есть две команды:
- Вычти 2
- Найди целую часть от деления на 2
Программа для исполнителя – это последовательность команд.
Сколько существует программ, для которых при исходном числе 38 результатом является число 2 и при этом траектория вычислений содержит число 16?
Траектория вычислений программы – это последовательность результатов выполнения всех команд программы. Например, для программы ABB при исходном числе 13 траектория состоит из чисел 11, 5, 2.
Решение:
Решение на Python
# Функция которая вызывает сама себя сделает всю работу
def f(in_num, out_num): # in_num исходное число, out_num результат
if in_num == out_num: # если из исходного числа получился результат
return 1
if in_num > out_num or 11 == in_num: # Если получилось исходное число больше результата или число 11
return 0
if in_num < out_num: # Если исходное число меньше результат продолжаем выполнять команды
# Вызываем рекурсивно команды исполнителя, чтобы получить траекторию вычислений со всеми вариантами чисел
# Чтобы понять как это будет работать - запустите пример в режиме отладки
return f(in_num + 1, out_num) + f(in_num * 2, out_num) + f(in_num * in_num, out_num)
# Выводим результат
print(f(2, 20)) # по условию задачи исходное число 2, результат 20
Ответ: 37
Задача 2
У исполнителя Удвоитель две команды, которым присвоены номера:
- прибавить 3,
- умножить на 2.
Первая из них увеличивает число на экране на 3, вторая - удваивает его.
Программа для Удвоителя - это последовательность команд.
Сколько есть программ, которые число 1 преобразуют в число 25 ?
Решение:
Решение на Python
def f(x, y):
if x == y:
return 1
if x > y:
return 0
if x < y:
return f(x + 3, y) + f(x * 2, y)
print(f(1, 25))
Ответ: 9
Задача 3
Исполнитель НечетМ преобразует число на экране. У исполнителя НечетМ две команды, которым присвоены номера:
- прибавь 1
- сделай нечётное
Первая из этих команд увеличивает число x на экране на 1, вторая переводит число x в число 2x+1. Например, вторая команда переводит число 10 в число 21. Программа для исполнителя НечетМ — это последовательность команд.
Сколько существует таких программ, которые число 1 преобразуют в число 25, причём траектория вычислений не содержит число 24?
Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Например, для программы 121 при исходном числе 7 траектория будет состоять из чисел 8, 17, 18.
Решение:
Решение на Python
def f(x, y):
if x == y:
return 1
if x > y or x == 24:
return 0
if x < y:
return f(x + 1, y) + f(x * 2 + 1, y)
print(f(1, 25))
Ответ: 10
Задача 4
У исполнителя есть три команды, которым присвоены номера:
- Прибавить 1
- Умножить на 3
- Прибавить 2
Первая команда увеличивает число на экране на 1, вторая умножает его на 3, третья увеличивает его на 2.
Сколько существует программ, которые преобразуют исходное число 2 в число 12 и при этом траектория вычислений содержит число 9 и число 11?
Траектория вычислений программы - это последовательность результатов выполнения всех команд программы. Например, для программы 132 при исходном числе 7 траектория будет состоять из чисел 8, 10, 30.
Решение:
Решение на Python
def f(x, y):
if x == y:
return 1
if x > y:
return 0
if x < y:
return f(x + 1, y) + f(x * 3, y) + f(x + 2, y)
print(f(2, 9) * f(9, 11) * f(11, 12))
Ответ: 50
Задача 5
Исполнитель Май17 преобразует число на экране. У исполнителя есть две команды, которым присвоены номера:
- Прибавить 1
- Прибавить 3
Первая команда увеличивает число на экране на 1, вторая увеличивает его на 3. Программа для исполнителя Май17 — это последовательность команд.
Сколько существует программ, для которых при исходном числе 1 результатом является число 17 и при этом траектория вычислений содержит число 9?
Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Например, для программы 12 при исходном числе 7 траектория будет состоять из чисел 8, 11, 12.
Решение:
Решение на Python
def f(x, y):
if x == y:
return 1
if x > y:
return 0
if x < y:
return f(x + 1, y) + f(x + 3, y)
print(f(1, 9) * f(9, 17))
Ответ: 169
Задача 6 (Демоверсия 2025)
Исполнитель преобразует число на экране. У исполнителя есть две команды:
- Вычти 2
- Найди целую часть от деления на 2
Программа для исполнителя – это последовательность команд.
Сколько существует программ, для которых при исходном числе 38 результатом является число 2 и при этом траектория вычислений содержит число 16?
Траектория вычислений программы – это последовательность результатов выполнения всех команд программы.
Например, для программы ABB при исходном числе 13 траектория состоит из чисел 11, 5, 2.
Решение:
Решение на Python
def f(in_num, out_num): # in_num исходное число, out_num результат
if in_num == out_num: # Если из исходного числа получился результат
return 1
if in_num < out_num: # Если получилось исходное число меньше результата, решения нет
return 0
if in_num > out_num: # Если исходное число больше результата продолжаем выполнять команды
# Вызываем рекурсивно команды исполнителя, чтобы получить траекторию вычислений со всеми вариантами чисел
# Чтобы понять как это будет работать - запустите пример в режиме отладки
return f(in_num - 2, out_num) + f(in_num // 2, out_num)
# Выводим результат
# по условию задачи исходное число 38, результат 2 и трактория вычислений содержит число 16
print(f(38, 16) * f(16, 2))
Если бы в условии говорилось что траектория вычислений не должна содержать число 16: тогда условие if in_num < out_num заменили бы на if in_num < out_num or 16 == in_num:. И вызов функции бы был print(f(38, 2).
А так решение такое как в коде выше. И само собой если Исполнитель уменьшает число исходное то вызов рекурсии должен быть в условии, где исходное число больше результата и должно быть прописано всегда последним условием. И наоборот если увеличивает то меняем знак на противоположный в двух последних условиях.
Ответ: 36
Задача 7 (Демоверсия 2026)
Исполнитель преобразует число на экране. У исполнителя есть три команды, которые обозначены латинскими буквами:
A. Вычесть 1
B. Вычесть 4
C. Найти целую часть от деления на 3
Программа для исполнителя – это последовательность команд. Сколько существует программ, для которых при исходном числе 19 результатом является 2, при этом траектория вычислений не содержит числа 7 и содержит 13?
Траектория вычислений программы – это последовательность результатов выполнения всех команд программы. Например, для программы СBА при исходном числе 22 траектория состоит из чисел 7, 3, 2.
Решение:
Решение на Python
def f(in_num, out_num): # in_num исходное число, out_num результат
if in_num == out_num: # Если из исходного числа получился результат
return 1
if in_num < out_num or 7 == in_num: # Если получилось исходное число больше результата или число 7
return 0
if in_num > out_num: # Если исходное число больше результата продолжаем выполнять команды
# Вызываем рекурсивно команды исполнителя, чтобы получить траекторию вычислений со всеми вариантами чисел
# Чтобы понять как это будет работать - запустите пример в режиме отладки
return f(in_num - 1, out_num) + f(in_num - 4, out_num) + f(in_num // 3, out_num)
# Выводим результат
# по условию задачи исходное число 19, результат 2 и трактория вычислений содержит число 13
print(f(19, 13) * f(13, 2))
Если бы в условии не говорилось, что траектория вычислений не должна содержать число 7: Тогда условие if in_num < out_num or 7 == in_num: заменили бы на if in_num < out_num: Если бы в условии не говорилось, что траектория вычислений должна содержать число 13, вызов функции бы был print(F(19, 2)). А так решение такое как код выше. И само собой если исполнитель уменьшает число исходное то вызов рекурсии должен быть в условии, где исходное число больше результата и должно быть прописано всегда последним условием. И наоборот если увеличивает то меняем знак на противоположный в двух последних условиях.
Ответ: 68
Типы заданий № 23
Задача 1 (Демоверсия 2027)
В текстовом файле содержится описание ациклического ориентированного взвешенного графа.
В каждой строке файла записаны два натуральных числа(L, M) и одно положительное вещественное число (W).
L и M – номера вершин графа, W – вес ребра, ведущего из вершины L в вершину M.
Таким образом, количество строк в файле равно количеству рёбер в графе.
Две вершины графа не могут быть соединены более чем одним ребром.
Найдите и запишите в ответе целую часть длины кратчайшего пути из вершины с номером 1 в вершину с номером 100.
Существование хотя бы одного такого пути гарантируется.
Под длиной кратчайшего пути понимается минимальная сумма весов рёбер, составляющих путь.
Для выполнения этого задания следует написать программу.
Вершины графа могут быть пронумерованы не подряд. L ≤ 1000, M ≤ 1000; W ≤ 10 000.
Количество строк в файле не превосходит 200.
Числа в строках разделены произвольным ненулевым количеством пробелов и/или табуляций.
Типовой пример организации данных во входном файле для графа на рисунке
100 12 1.0
6 7 7.0
6 1 1.0
1 7 5.5
7 100 2.0
4 100 8.0
1 100 12.0
1 4 2.5
Для приведённого примера верным ответом будет 7.
Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемого файла.
Решение:
Задача решается с помощью алгоритма Дейкстры. Подробнее об этом алгоритме можно прочитать в моей статье Алгоритм Дейкстры.
Решение на Python
# Чтение файла и построение графа
graph = {} # Словарь с ключём вершины L и значением как кортеж из вершины M и весом W
with open('23_2027.txt', 'r', encoding='utf-8') as f:
for line in f:
parts = line.split()
if len(parts) < 3:
continue
L = int(parts[0]) # вершина-источник L
M = int(parts[1]) # вершина-приёмник M
W = float(parts[2]) # вес ребра W
if L not in graph:
graph[L] = []
graph[L].append((M, W))
# Собираем множество всех вершин графа
nodes = set(graph.keys()) # Добавляем вершины L в множество
for L in graph:
for M, _ in graph[L]:
nodes.add(M) # Добавляем вершины M в множество
# Инициализация расстояний: все вершины бесконечно далеки, кроме стартовой (1)
INF = float('inf')
dist = {} # Словарь расстояний
for n in nodes:
dist[n] = INF
dist[1] = 0 # Стартовая вершина 1 растояние до неё 0 потому что с неё начинается путь.
visited = set() # множество посещённых вершин
# Алгоритм Дейкстры
while len(visited) < len(nodes):
# Ищем непосещённую вершину с минимальным расстоянием
L = None
min_dist = INF
for n in nodes:
if n not in visited and dist[n] < min_dist:
min_dist = dist[n]
L = n
if L is None: # все оставшиеся вершины недостижимы
break
visited.add(L) # Добавляем вершину в множество посещённых вершин
if L == 100: # достигли целевой вершины — можно остановиться
break
if L in graph: # обновляем расстояния до соседей
for M, W in graph[L]:
if dist[L] + W < dist[M]:
dist[M] = dist[L] + W
# Выводим целую часть кратчайшего пути от 1 до 100
print(int(dist[100]))
Ответ: 10971
Попробуйте сами запустить код в окне ниже с интерпретатором Python и повторите примеры из статьи чтобы самим увидеть и понять как всё это работает. Для этого в ячейке с кодом нажмите клавиши на клавиатуре Shift+Enter или запустите код через кнопку Run по значку ▶.