На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л, М. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Определите количество различных путей, которые начинаются в городе А и заканчиваются в городе М.
Посчитаем последовательно количество путей до каждого из пунктов:
А = 1 (начальный пункт);
Б = А = 1;
В = А + Б = 2;
Г = Б + В = 3;
Д = Г = 3;
Е = Д + Г = 6;
Ж = Г = 3;
З = Е + Г + Ж = 12;
И = Д + Е = 9;
Л = З + Ж = 15;
К = И + Е + З + Л = 42;
М = И + К + Л = 66 (конечный пункт).
Ответ: 66.
Приведём решение Евгения Джобса на языке Python.
Принцип решения (циклическое, от «А»).
1. Описываем все входящие дуги.
2. Определяем значение в А, как 1.
3. Если значения для всех начальных пунктов во входящих дугах определены, то находим значение в текущей вершине.
4. Выполняем алгоритм до тех пор, пока значения для всех вершин не будет подсчитано.
g_str = 'ба вба гвб дг едг жг згеж иде киезл
лзж микл'
g = {c[0]: c[1:] for c in g_str.split()}
r = {'а': 1}
while not all(x in r for x in g):
for v, d in g.items():
if v not in r and all(x in r
for x in d):
r[v] = sum(r[x] for x in d)
print(r['м'])
Приведём решение Евгения Джобса на языке Python.
Принцип решения (рекурсивное, от «А»).
g_str = 'ба вба гвб дг едг жг згеж иде киезл
лзж микл'
g = {c[0]: c[1:] for c in g_str.split()}
def f(v):
if v == 'а':
return 1
return sum(f(x) for x in g[v])
print(f('м'))