СДАМ ГИА: РЕШУ ЕГЭ
Образовательный портал для подготовки к экзаменам
Информатика
≡ информатика
сайты - меню - вход - новости




Задания
Версия для печати и копирования в MS Word
Задание 15 № 9801

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

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

Решение.

Начнем считать количество путей с конца маршрута – с города Т. NX — количество различных путей из города А в город X, N — общее число путей.

 

В "Т" можно приехать из П или Р, поэтому N = NТ = NП + NР (1)

 

Аналогично:

 

NП = NР = NН

NН = NК + NМ + NЛ

NК = NЕ + NБ

NМ = NК + NЛ

NЛ = NЕ + NД

NЕ = NБ + NВ + NА + NГ + NД

 

Добавим еще вершины:

 

NВ = NБ + NА = 2

NГ = NД + NА = 2

NБ = NД = 1

 

 

Подставим в формулу (1):

 

N = NТ = 2 NН = 2 · (8 + 16 + 8) = 64.

 

Ответ: 64.