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

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

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

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

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

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

Ответ

15