Задание 23. Графы. Подсчёт количества программ. ЕГЭ 2027 по информатике
Средний процент выполнения: 52%
Ответом к заданию 23 по информатике может быть цифра (число) или слово.
Алгоритм решения задания 23:
- Прочитай алгоритм и зафиксируй начальные значения переменных.
- Определи порядок выполнения команд.
- Выполняй алгоритм пошагово, фиксируя изменения после каждой команды.
- Если есть условия или циклы, проверяй их выполнение на каждом шаге.
- Веди таблицу трассировки для контроля значений переменных.
- Доведи выполнение до конца алгоритма.
- Сформулируй ответ по полученному результату.
Подпишись на суперполезные материалы
Задачи для практики
Задача 1
В текстовом файле содержится описание ациклического ориентированного
взвешенного графа. В каждой строке файла записаны два натуральных числа
(L, M) и одно положительное вещественное число
(W). L и M — номера вершин графа,
W — вес ребра, ведущего из вершины L в вершину
M. Таким образом, количество строк в файле равно количеству
рёбер в графе. Две вершины графа не могут быть соединены более чем одним
ребром.
Найдите и запишите в ответе целую часть длины кратчайшего пути из вершины с номером 1 в вершину с номером 975. Существование хотя бы одного такого пути гарантируется. Под длиной кратчайшего пути понимается минимальная сумма весов рёбер, составляющих путь.
Для выполнения этого задания следует написать программу.
Вершины графа могут быть пронумерованы не подряд: 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.
Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемого файла.
Решение
Читаем рёбра графа из файла, затем используем упрощённый алгоритм Беллмана-Форда: 200 раз подряд проходим по всем рёбрам и обновляем («релаксируем») расстояние до конца каждого ребра через его начало. Такого числа повторов достаточно, чтобы кратчайшее расстояние «дошло» до любой вершины, даже если путь состоит из длинной цепочки рёбер, а рёбра в файле идут не по порядку.
a = []
for l in open('23.txt'):
u, v, w = l.split()
a.append((int(u), int(v), float(w)))
d = [0, 0] + [float('inf')] * 1000
for _ in range(200):
for u, v, w in a:
d[v] = min(d[v], d[u] + w)
print(int(d[975]))
d — массив расстояний от вершины 1, индекс — номер вершины.
d[1] = 0 (расстояние до самой себя), остальные изначально
inf (недостижимы). На каждой из 200 итераций для каждого ребра
u → v весом w проверяем: если добраться до
v через u получается короче, чем то, что мы знали
раньше — обновляем d[v]. В конце в d[975] лежит
кратчайшее расстояние до искомой вершины; int(...) берёт целую
часть, как требует условие.
Задача 2
В текстовом файле содержится описание ациклического ориентированного
взвешенного графа. В каждой строке файла записаны два натуральных числа
(L, M) и одно положительное вещественное число
(W). L и M — номера вершин графа,
W — вес ребра, ведущего из вершины L в вершину
M. Таким образом, количество строк в файле равно количеству
рёбер в графе. Две вершины графа не могут быть соединены более чем одним
ребром.
Найдите и запишите в ответе целую часть длины кратчайшего пути из вершины с номером 1 в вершину с номером 529. Существование хотя бы одного такого пути гарантируется. Под длиной кратчайшего пути понимается минимальная сумма весов рёбер, составляющих путь.
Для выполнения этого задания следует написать программу.
Вершины графа могут быть пронумерованы не подряд: 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.
Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемого файла.
Решение
Читаем рёбра графа из файла, затем используем упрощённый алгоритм Беллмана-Форда: 200 раз подряд проходим по всем рёбрам и обновляем («релаксируем») расстояние до конца каждого ребра через его начало. Такого числа повторов достаточно, чтобы кратчайшее расстояние «дошло» до любой вершины, даже если путь состоит из длинной цепочки рёбер, а рёбра в файле идут не по порядку.
a = []
for l in open('23.txt'):
u, v, w = l.split()
a.append((int(u), int(v), float(w)))
d = [0, 0] + [float('inf')] * 1000
for _ in range(200):
for u, v, w in a:
d[v] = min(d[v], d[u] + w)
print(int(d[529]))
d — массив расстояний от вершины 1, индекс — номер вершины.
d[1] = 0 (расстояние до самой себя), остальные изначально
inf (недостижимы). На каждой из 200 итераций для каждого ребра
u → v весом w проверяем: если добраться до
v через u получается короче, чем то, что мы знали
раньше — обновляем d[v]. В конце в d[529] лежит
кратчайшее расстояние до искомой вершины; int(...) берёт целую
часть, как требует условие.
Рекомендуемые курсы подготовки
- 🔥 Изучишь одни из самых фундаментальных тем информатики
- 🔥 Научишься решать 6 задач формата ЕГЭ руками
- 🔥 Начнёшь свой путь в проге
- 🔥 Учёба на Турбо: познакомишься с преподавателями и личным кабинетом
Что тебя ждет?
- 8 вебинаров (1 веб в неделю по 1 часу)
- Тестовые Д/З после каждого занятия
- Конспекты и скрипты к урокам
- Доступ к личному кабинету
- Возможность отрабатывать задания ЕГЭ в любое время
- Чат с единомышленниками
- Поддержка препа 24/7
на бесплатном курсе Турбо ЕГЭ
