Question

На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.




Сколько существует различных путей из города А в город К?

Answer 1

Ответ:

17

Объяснение:

АБВДЖК, АБВДИК, АБВЕЖК, АБВЕК, АБВЕЛК, АБВЖК, АБДЖК, АБДИК, АГВДЖК, АГВДИК, АГВЕЖК, АГВЕК, АГВЕЛК, АГВЖК, АГЕЖК, АГЕК, АГЕЛК.

Исходный код программы, выполнявшей вычисления (С++) дан во вложении.

UPD: Выше был также представлен алгоритм рекурсивного обхода. Автор вводит $N_x$ как количество способов доехать из города A в город X.  Посмотрим на город К. В него можно приехать из городов И, Ж, Е и Л. Таким образом, Nк = Nи + Nж + Nе + Nл. В свою очередь, в город И можно приехать только из города Д, значит, Nи = Nд, Nд = Nб + Nв и так далее до города А, для которого Nа = 1.

fd8e23af4aec9c3f01d0fd24b5c6428a.cpp