Пути с условиями: как решать — ЕГЭ по информатике

ЕГЭ Информатика сложность в тренажёре: продвинутая

Схема дорог с односторонним движением между городами А, Б, В, Г, Д, Е, Ж, З: из А — в Б, В, Г; из Б — в В; из В — в Г… Пути с условиями — ЕГЭ по информатике, тема «Пути в графе». Ответ проверяется на странице, разбор — сразу.

Пример 1

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

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

Ответ: 20

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

Ответ: 20.

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

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

23 декабря 1947 года в Bell Labs показали руководству первый работающий точечный транзистор. Бардин и Браттейн добились усиления сигнала ещё 16 декабря. Широкой публике новое устройство представили 30 июня 1948 года.

Разобранный пример

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

Решение

Ответ: 16

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

Ответ: 16.

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

Формулы и приём

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

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

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

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

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

Ещё примеры

Пример 2

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

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

Ответ: 18

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

Ответ: 18.

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

Пример 3

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

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

Ответ: 10

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

Ответ: 10.

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

Пример 4

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

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

Ответ: 18

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

Ответ: 18.

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

Рядом

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

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

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

Родителю

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