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

u2124618121

5 февраля 2018 г. в 00:00

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

SOVA

5 февраля 2018 г. в 00:00

Начнем счи­тать ко­ли­че­ство путей с конца маршрута — с го­ро­да 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.