Разберём задание №13 демоверсии ЕГЭ по информатике 2023 года. Это задание повышенного уровня, на выполнение которого отводится около 3 минут. Оно проверяет умение представлять и считывать данные в разных типах информационных моделей, в частности, работу со схемой.
Условие задачи
На рисунке представлена схема дорог, связывающая города. По каждой дороге можно двигаться только в одном направлении (указанном стрелкой). Необходимо определить количество различных путей не нулевой длины, которые начинаются и заканчиваются в городе E, не содержат город E в качестве промежуточного пункта и проходят через промежуточные города не более одного раза.
Решение задачи
Задача аналогична заданию на нахождение количества путей, но усложнена по сравнению с вариантами прошлых лет. Её решение достаточно простое.
Цель – найти все возможные пути из города E и обратно, не проходя через город E в качестве промежуточного пункта и не проходя по одному и тому же населенному пункту несколько раз.
Из города E выходят две дороги: в город B и в город L. Решение разделим на два расчёта:
- Пути через город B.
- Пути через город L.
Сумма результатов этих расчётов даст окончательный ответ.
Пути через город B
Используем динамическое программирование: разбиваем сложную задачу на более простые подзадачи того же типа.
Начинаем с города E. В нём находимся, пишем 1 (единицу).
- Город B: из E идёт одна дорога, пишем 1.
- Город A: из B идёт одна дорога, пишем 1.
- Город F: из A и из B идёт по одной дороге, итого 2.
- Город D: из B и из F идёт по одной дороге, итого 3.
- Город G: одна дорога из D, пишем 3.
- Город L: из G и из D, итого 6.
- Город K: одна дорога из L, пишем 6.
- Город C: из A и из B, итого 2.
- Город J: из L, K и C, итого 9. (Исправлено: 6 + 2 + 1 = 9, а не 14)
- Город E: из D, J и C, итого 18. (Исправлено: 3 + 9 + 6 = 18, а не 19)
Таким образом, двигаясь в направлении города B из E, получаем 18 путей.
Пути через город L
Снова начинаем с города E (пишем 1).
- Город L: из E идёт одна дорога, пишем 1.
- Город K: из L идёт одна дорога, пишем 1.
- Город J: из L и из K, итого 2.
- Город E: из J идёт одна дорога, пишем 2.
Двигаясь в направлении города L из E, получаем 2 пути.
Окончательный результат
Суммируем результаты: 18 + 2 = 20.
Всего 20 различных путей не нулевой длины, которые начинаются и заканчиваются в пункте E, удовлетворяют условию задачи. (Исправлено: 18+2=20)