Пути в графе: задания с разбором — ЕГЭ по информатике

ЕГЭ Информатика

ЕГЭ по информатике, тема «Пути в графе»: Пути с условиями, Число программ с условиями. Формулы темы. Ответ проверяется на странице, разбор открывается сразу.

Пример 1

Между городами А, Б, В, Г, Д, Е построены дороги с односторонним движением: из А — в Б, В, Е; из Б — в В; из В — в Д; из Д — в Е. По каждой дороге можно двигаться только в указанном направлении. Сколько существует различных путей из города А в город Е?

Ответ и разбор

Ответ: 3

Считаем число путей до каждого города по порядку: в А ведёт один путь (начало), а в каждый следующий город — сумма путей до всех городов, из которых в него есть дорога. Для города Е эта сумма равна 3.

Нашли ошибку? Напишите нам, код задания: ege-informatics-graf-puti-3xmhdm

Ещё задания — ниже. Открыть тренажёр

Две программы могут застрять, если каждая удерживает ресурс, нужный другой, и ждёт его освобождения. Такое взаимное ожидание называется тупиком, или deadlock. Быстрый процессор сам по себе его не устраняет: нужно изменить порядок захвата или освободить ресурс.

Формулы темы

Подсчёт путей в графе

Как быстро посчитать все пути из А в К по стрелкам?

путей в вершину = сумма путей во все вершины, откуда ведёт стрелка · путей в старт = 1

Подписывай у каждой вершины число путей до неё: у старта единица, у любой другой — сумма чисел всех вершин, из которых в неё идёт стрелка. Если в Г ведут стрелки из Б (3 пути) и В (2 пути), то до Г ровно 3 + 2 = 5 путей. Обходи вершины по направлению стрелок, пока не дойдёшь до конечной.

Пути «через вершину Д» — перемножь число путей от старта до Д и от Д до финиша. Пути «не через Д» — из общего числа путей вычти проходящие через Д.

Все карточки предмета — в разделе «Формулы»

Ещё задания

Пример 2

Схема дорог с односторонним движением между городами А, Б, В, Г, Д, Е, Ж, З, И: из А — в Б, В, Г; из Б — в В, Ж; из В — в Г, Е; из Г — в Д, Ж; из Д — в Е, Ж; из Е — в Ж, З; из Ж — в З; из З — в И. Других дорог нет. Сколько существует различных путей из города А в город И, которые проходят хотя бы через один из городов В и Е?

Ответ и разбор

Ответ: 14

Удобнее сосчитать пути, которые не проходят ни через В, ни через Е, и вычесть их из всех путей.
Число путей в город — сумма чисел путей в города, из которых в него ведёт дорога.
Все пути: А — 1, Б — 1, В — 2, Г — 3, Д — 3, Е — 5, Ж — 12, З — 17, И — 17.
В обход В и Е: А — 1, Б — 1, В — 0 (запрещён), Г — 1, Д — 1, Е — 0 (запрещён), Ж — 3, З — 3, И — 3.
Хотя бы через один из них: 17 − 3 = 14.

Ответ: 14.

Нашли ошибку? Напишите нам, код задания: ege-informatics-puti-s-usloviyami-1yv6nb3

Пример 3

Исполнитель работает с числом на экране и умеет выполнять команды:
1. Прибавить 1
2. Умножить на 2
3. Умножить на 3
Программа — любая последовательность этих команд, её траектория — числа, которые появляются на экране после каждой команды. Сколько существует программ, которые из числа 1 получают число 30, если траектория должна содержать число 7 и не должна содержать числа 24?

Ответ и разбор

Ответ: 70

Число программ, получающих число y, равно сумме чисел программ для чисел, из которых y получается одной командой: y − 1, y : 2 (если y чётно), y : 3 (если y делится на 3). Команды только увеличивают число, поэтому считаем по возрастанию.
Траектория проходит через 7: программа делится на участки 1 → 7 и 7 → 30, и число программ равно произведению чисел программ на участках.
Число 24 больше 7 — оно может встретиться только на втором участке: там считаем для него 0 программ.
Участок 1 → 7: 1 — 1, 2 — 2, 3 — 3, 4 — 5, 5 — 5, 6 — 10, 7 — 10.
Участок 7 → 30: 7 — 1, 8 — 1, 9 — 1, 10 — 1, 11 — 1, 12 — 1, 13 — 1, 14 — 2, 15 — 2, 16 — 3, 17 — 3, 18 — 4, 19 — 4, 20 — 5, 21 — 6, 22 — 7, 23 — 7, 24 — 0 (запрет), 25 — 0, 26 — 1, 27 — 2, 28 — 4, 29 — 4, 30 — 7.
Всего: 10 · 7 = 70.

Ответ: 70.

Нашли ошибку? Напишите нам, код задания: ege-informatics-puti-s-usloviyami-16yaetb

Пример 4

Между городами А, Б, В, Г, Д, Е, Ж, З, И, К, Л заданы дороги с односторонним движением.
Ниже перечислены все дороги. Число в скобках — стоимость проезда по дороге в условных единицах.

Из А — в Б (1), В (1), И (2).
Из Б — в В (1), Г (2).
Из В — в Г (2).
Из Г — в Д (1), Е (4), Л (4).
Из Д — в Е (1), Ж (2).
Из Е — в Ж (1), З (1).
Из Ж — в З (4), И (3), Л (3).
Из З — в И (1).
Из И — в К (1), Л (1).
Из К — в Л (2).

Других дорог нет. По дороге можно двигаться только в указанном направлении. Все дороги ведут к городам, стоящим правее в приведённом списке, поэтому циклов нет.
Стоимость пути равна сумме стоимостей его дорог. Два пути считаются различными, если различаются последовательности посещённых городов.

Сколько существует путей из А в Л, которые проходят через Е и имеют стоимость ровно 12?

Ответ и разбор

Ответ: 9

Разобьём путь в обязательном городе Е. В ациклическом графе он встречается не более одного раза: любой подходящий путь однозначно состоит из участка А → Е и участка Е → Л.

Одних общих чисел путей на участках недостаточно: их стоимости должны в сумме дать ровно 12. Сохраняем отдельный счётчик для каждой стоимости.

F(v, s) — число путей из А в v со стоимостью ровно s. База F(А, 0) = 1: это единственный пустой путь в начальный город, без дорог и затрат. Остальные начальные состояния равны 0.

Считаем вершины в приведённом порядке. Для каждой входящей дороги u → v стоимости c прибавляем F(u, s − c) к F(v, s). Каждое продолжение имеет единственную последнюю дорогу, поэтому такой подсчёт не теряет и не дублирует пути; при отрицательной стоимости значение равно 0.

В списках запись «стоимость → количество» означает число путей именно этой стоимости. Показаны все ненулевые состояния, без отсечения по бюджету; не перечисленные стоимости имеют количество 0.

Первый участок: А → Е, распределения F:

  • Город А: 0 → 1.
  • Город Б: 1 → 1.
  • Город В: 1 → 1; 2 → 1.
  • Город Г: 3 → 2; 4 → 1.
  • Город Д: 4 → 2; 5 → 1.
  • Город Е: 5 → 2; 6 → 1; 7 → 2; 8 → 1.

Проверка: F(Г, 3) = F(Б, 1) + F(В, 1) = 1 + 1 = 2 — клетка сходится.

Второй участок: Е → Л, распределения G. Начинаем заново с G(Е, 0) = 1 (пустой путь); переход тот же.

  • Город Е: 0 → 1.
  • Город Ж: 1 → 1.
  • Город З: 1 → 1; 5 → 1.
  • Город И: 2 → 1; 4 → 1; 6 → 1.
  • Город К: 3 → 1; 5 → 1; 7 → 1.
  • Город Л: 3 → 1; 4 → 1; 5 → 2; 7 → 2; 9 → 1.

Проверка: G(Л, 5) = G(И, 4) + G(К, 3) = 1 + 1 = 2 — клетка сходится.

Сочетаем только дополняющие стоимости: если первый участок стоит s, второй должен стоить 12 − s. Для фиксированной пары любой первый путь можно соединить с любым вторым: ранние и поздние вершины не пересекаются, кроме Е. Разные пары стоимостей не смешиваются.

  • 5 + 7 = 12: 2 · 2 = 4.
  • 7 + 5 = 12: 2 · 2 = 4.
  • 8 + 4 = 12: 1 · 1 = 1.

Другие пары не дают нужной суммы или имеют нулевое количество путей. Всего: 4 + 4 + 1 = 9.

Частая ошибка

Ловушка: произведение общих чисел путей учитывает и другие стоимости; подсчёт всех путей нужной стоимости дополнительно захватил бы пути в обход Е.

Ответ: 9.

Нашли ошибку? Напишите нам, код задания: stg-ege-informatics-paths-high-10

Пример 5

Схема дорог с односторонним движением между городами А, Б, В, Г, Д, Е, Ж, З, И, К: из А — в Б, В, Г, З; из Б — в В, Г, Д, Е, З, И; из В — в Г; из Г — в Д, К; из Д — в Е, З; из Е — в Ж, З, И, К; из Ж — в З; из З — в И, К; из И — в К. Других дорог нет. Сколько существует различных путей из города А в город К, которые проходят через город Е и не проходят через город И?

Ответ и разбор

Ответ: 18

Путь через город Е состоит из двух участков — из А в Е и из Е в К, — и число путей равно произведению чисел путей на участках (на втором участке счёт начинается в Е с единицы).
Дороги ведут только к городам, стоящим дальше по алфавиту, поэтому город И (он позже Е) может встретиться только на втором участке — там считаем, что путей в него нет.
Число путей в город — сумма чисел путей в города, из которых в него ведёт дорога.
Участок А → Е: А — 1, Б — 1, В — 2, Г — 4, Д — 5, Е — 6.
Участок Е → К: Е — 1, Ж — 1, З — 2, И — 0 (запрещён), К — 3.
Всего: 6 · 3 = 18.

Ответ: 18.

Нашли ошибку? Напишите нам, код задания: ege-informatics-puti-s-usloviyami-166y0gr

Пример 6

Исполнитель работает с числом на экране и умеет выполнять команды:
1. Прибавить 1
2. Прибавить 3
Программа — любая последовательность этих команд, её траектория — числа, которые появляются на экране после каждой команды. Сколько существует программ, которые из числа 3 получают число 19, если траектория должна содержать число 10 и не должна содержать числа 16?

Ответ и разбор

Ответ: 63

Число программ, получающих число y, равно сумме чисел программ для чисел, из которых y получается одной командой: y − 1, y − 3. Команды только увеличивают число, поэтому считаем по возрастанию.
Траектория проходит через 10: программа делится на участки 3 → 10 и 10 → 19, и число программ равно произведению чисел программ на участках.
Число 16 больше 10 — оно может встретиться только на втором участке: там считаем для него 0 программ.
Участок 3 → 10: 3 — 1, 4 — 1, 5 — 1, 6 — 2, 7 — 3, 8 — 4, 9 — 6, 10 — 9.
Участок 10 → 19: 10 — 1, 11 — 1, 12 — 1, 13 — 2, 14 — 3, 15 — 4, 16 — 0 (запрет), 17 — 3, 18 — 7, 19 — 7.
Всего: 9 · 7 = 63.

Ответ: 63.

Нашли ошибку? Напишите нам, код задания: ege-informatics-puti-s-usloviyami-1c1ips

Виды заданий темы

Разборы отдельных заданий

Рядом

Продолжить тренировку

Откройте тренажёр, чтобы решать похожие задания и отслеживать прогресс по темам. Для тренажёра нужен вход; на этой странице вход не нужен.

Задание в формате экзамена с разбором

Родителю

Приложение — для ученика. Родителю ставить его не нужно: кабинет родителя открывается в браузере. Родитель видит фактическую активность, регулярность и повторяющиеся ошибки. Проверять решения самостоятельно не требуется.