Разбор задания ОГЭ по информатике. Декабрь 2024. Анализирование информации, представленной в виде схем. Поиск путей из одного города в другой, проходящих или не проходящих через определенный пункт

На рисунке  — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, К, Л, М, Н, П. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.

Сколько существует различных путей из города А в город П, проходящих через город Л?

Решение.

Количество путей до города П равно сумме путей в каждый из тех городов, из которых есть дорога в П. С помощью этого наблюдения посчитаем последовательно количество путей до каждого из городов, кроме тех, которые не проходят через город Л:

А = 1

Б = А = 1

Д = А = 1

Г = А + Б = 1 + 1 = 2

В = Б + Г = 1 + 2 = 3

Е = Г + Д = 2 + 1 = 3

Ж = В + Г + Е = 3 + 2 + 3 = 8

K = Ж = 8

Н = Ж = 8

М = Ж + Н = 16

Л = К + Ж + М = 8 + 8 + 16 = 32

П = Л = 32 (так как ищем пути проходящие через город Л).

Приведем другое решение.

Заметим, что путь из города А в город П обязательно должен проходить через город Ж. По условию задачи путь должен также проходить через город Л. Тогда количество путей из города А в город П, проходящих через город Л, равно произведению количества путей из города А в город Ж, количества путей из города Ж в город Л и количества путей из города Л в город П.

Найдем количество путей из города А в город Ж:

А = 1

Б = А = 1

Д = А = 1

Г = А + Б = 1 + 1 = 2

В = Б + Г = 1 + 2 = 3

Е = Г + Д = 2 + 1 = 3

Ж = В + Г + Е = 3 + 2 + 3 = 8.

Найдем количество путей из города Ж в город Л (при этом Ж - исходный пункт):

Ж = 1

Н = К = Ж = 1

М = Ж + Н = 2

Л = К + Ж + М = 4.

Из города Л в город П есть только один путь.

Тогда количество путей из города А в город П, проходящих через город Л, равно 8 · 4 · 1 = 32.

Ответ: 32.