Данное задание ЕГЭ №13 по информатике простое и его решение сводится к обычному подсчёту “путей”. Существует два самых основных способа решения данного задания: графический и аналитический.
Самое важное, на что тут стоит обратить внимание — вид графа. Здесь представлен ориентированный граф, то есть любое передвижение возможно только по направлению стрелки. Если был бы неориентированный граф (без стрелок), то направление могло бы быть любое.
Разберём для начала графический способ решения данной задачи, он более наглядный.
Задание
Сколько существует различных путей из города А в город Т, проходящих через город Н?
Для начала стоит избавиться от лишних линий — путей, которые не проходят через город “Н”.
Отметили обязательное прохождение города “Н” и зачеркнули лишние линии, на которые уже не будем обращать внимание (так как они не проходят через город “Н”). После этого можно приступить к подсчёту количества путей. Для этого возле каждого города подпишем число — количество путей до него.
Стартовый путь (А), также включается в себя уже один путь. При вхождении в город предыдущие пути суммируются.
Например, в город “Г” приходят два пути, один из города “А”, второй из “Б”. Эти города содержат по одному пути, при сложении получаем количество путей в город “Г” — 2. Такая же ситуация обстоит со всеми городами.
Как видно, зачёркнутые пути попросту были проигнорированы. Подсчёт производился, будто их и не было вовсе. Останется просуммировать пути в городе “Т” и получить ответ — 32.
Аналитический способ похож на графический, но есть одно некоторое отличие — НЕ надо перерисовывать граф. То есть, всё то же самое, но уже просто выписываем города и рядом ставим количество путей, смотря при этом на граф.
Ниже пример, как это можно было бы записать в табличной форме (для удобства).
Но важно, внимательно смотреть, не посчитать случайно ненужный путь или же, наоборот, пропустить нужный. Иногда в условии задачи, наоборот, сказано: “посчитайте количество путей, НЕ проходящих через определённый город”.
Сколько, кстати, будет количество путей, если изменим условие задачи? Если нужно будет найти количество путей, НЕ проходящих через город “Н”?
Понравилась статья? Хочешь разбираться в информатике, программировании и уметь работать в разных программах? Тогда ставь лайк, подпишись на канал и поделись статьей с друзьями! Остались или появились вопросы — спроси в комментариях!
Читайте также:
- Информатика ЕГЭ №12 — методы find, count, replace при работе со строками в языке программирования Python
- Информатика ЕГЭ №11 — нахождение объёма информации в текстовом файле или в фрагменте текста
- Информатика ЕГЭ №10 — нахождение нужных слов в тексте, функция "найти и заменить" в текстовых препроцессорах Write/Word