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




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

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

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

Решение.

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

 

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

 

Аналогично:

 

NП = NН

NР = NП + NН = 2NН

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Т = 3 NН = 3 · (8 + 16 + 8) = 96.

 

Ответ: 96.