На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К, проходящих через город З?
Алгоритм:
- В стартовой вершине можно оказаться только одним способом. Поэтому для неё количество путей равно 1.
- Б = В = Г = Д = Е = А = ?
- Ж = Б + В = 2
И = Д + Е = ?
З = В + Г + Д + Ж + И = ? - В вершину К можно напрямую попасть из вершин Ж и И, но тогда мы не попадём в вершину З. Поэтому в вершину К мы можем попасть только из З, и тогда:
К = З = ?
Часть текста задания на фото плохо видна, поэтому условие переписано по смыслу и по алгоритму.
Шаг
Шаг
В И приходят пути из Д и Е:
В З приходят пути из В, Г, Д, Ж и И:
Шаг
Число путей в вершину равно сумме чисел путей во все вершины, из которых в неё ведут стрелки. Пути, идущие в К мимо З (из Ж и И напрямую), не учитываются.
Б = В = Г = Д = Е = А =
И = Д + Е =
З = В + Г + Д + Ж + И =
К = З =
Всего
