Задача 27021 На рисунке – схема дорог, связывающих...

u2124618121

02.05.2018

На рисунке – схема дорог, связывающих города A, B, C, D, E, F, G и H. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города A в город H?

SOVA

02.05.2018

Начнем счи­тать ко­ли­че­ство путей с конца маршрута — с го­ро­да H.
Пусть N_(X) — ко­ли­че­ство раз­лич­ных путей из го­ро­да А в город X,
N — общее число путей.

В город Н можно при­е­хать из G или F,
по­это­му N = N_(H) = N_(G) + N_(F) (#).

Аналогично,
N_(G) = N_(E) + N_(F) = 2+ 1 = 3;
N_(F) = N_(E)+N_(B)+N_(C) =2+1+1=3;

так как
N_(E)=N_(B)+N_(D)=1+1=2
N_(В) = N_(А) = 1;
N_(C)=N_(A)=1
N_(D)=N_(A)=1

Подставим най­ден­ные зна­че­ния в фор­му­лу (#):
N = 3 + 3 = 6.