Задание 2 Вариант 3 Контрольная работа 2 ГДЗ Рабочая тетрадь Босова 11 класс (Информатика)

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

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

Из города А можно попасть в Б и Д:

$$Б=1,\quad Д=1$$

Далее:

$$Г=Б+Д=1+1=2$$

$$В=Б+Г=1+2=3$$

$$Ж=Д+Г=1+2=3$$

$$Е=В+Г=3+2=5$$

$$И=В+Е=3+5=8$$

Город Ж в пути не должен встречаться, поэтому учитываем только пути, проходящие через вершины Е и И к городу М:

$$М=Е+И=5+8=13$$

Ответ

13