Задание 15. Графы и поиск количества путей: Демонстрационный вариант ЕГЭ по информатике 2018; государственный выпускной экзамен 2018; тренировочные варианты ЕГЭ по информатике, тематические тестовые задания и задачи из тренажера по информатике 2018
*** КАНАЛ ЮТЬЮБ ***
ЕГЭ по информатике -> ЕГЭ 2018 -> ЕГЭ 2018 — 15
15 задание. Демоверсия ЕГЭ 2018 информатика:
На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л, М.
По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.
Сколько существует различных путей из города А в город М, проходящих через город Ж?
✍ Показать решение:
Результат: 20
Решение 15 задания ЕГЭ по информатике, вариант 1 (ФИПИ, «ЕГЭ информатика и ИКТ, типовые экзаменационные варианты 2018», С.С. Крылов, Т.Е. Чуркина):
На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л, М. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.
Сколько существует различных путей из города А в город М?
✍ Показать решение:
Стрелка вниз указывает на то, что вычисленное количество мы взяли из вычисления ниже.
Стрелка вверх указывает на то, что вычисленное количество мы подставляем в какую-то сумму, указанную выше.
- Рассмотрим движение по маршруту, начиная с конечного пункта к началу, указывая в скобках рядом с городом количество путей к нему:
М = К(9)↓ + Л(10)↓ = 19
К = Е(1)↓ + И(8)↓ = 9 ↑
Е = Б(1)↓ = 1 ↑
Б = А = 1
И = Б(1) + Ж(5)↓ + З(2)↓ = 8 ↑
Ж = В(2) + Б(1) + З(2) = 5 ↑
В = Б(1) + А(1) = 2 ↑
З = Г(1)↓ + Д(1)↓ = 2 ↑
Г = А = 1
Д = Г = 1
Л = И(8) + З(2) = 10 ↑
Результат: 19
ЕГЭ по информатике -> ЕГЭ 2018 -> ЕГЭ 2018 — 15