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

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

Посчитаем количество путей до каждой вершины, двигаясь слева направо. Если в вершину ведут несколько дорог, то число путей в неё равно сумме чисел путей во все вершины, из которых в неё можно попасть.

Обозначим количество путей:

• в город Б — $$1$$;
• в город Д — $$1$$;
• в город Г — $$2$$, так как $$Г = Б + Д$$;
• в город Ж — $$3$$, так как $$Ж = Г + Д$$;
• в город Е — $$5$$, так как $$Е = Г + Ж$$;
• в город И — $$5$$, так как $$И = Е$$;
• в город М — $$10$$, так как $$М = И + Е$$;
• в город К — $$15$$, так как $$К = М + Е$$.

Требуется найти число путей из города А в город К, не проходящих через город В. По полученному подсчёту это число равно $$15$$.

Ответ

15