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

Сколько существует различных путей, ведущих из города А в город М и не проходящих через город Ж?
Б(1); Д(1); Г(2); В(3)=Г+Б; Е(5)=В+Г;
И(8)=Е+В; М(13)=Е+И
Ответ: 13

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

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

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

Далее:

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

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

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

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

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

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

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

Ответ

13