≡ информатика
сайты - меню - вход - новости




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

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

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

Пояснение.

Количество путей до города Т равно сумме путей в каждый из тех городов, из которых есть дорога в T. С помощью этого наблюдения посчитаем последовательно количество путей до каждого из городов, кроме тех, которые не проходят через город Л:

А = 1

Б = А = 1

Д = А = 1

Г = А + Б = 1 + 1 = 2

В = А + Г = 1 + 2 = 3

Е = Г + Д = 2 + 1 = 3

Ж = В + Г + Е = 3 + 2 + 3 = 8

K = Ж = 8

Н = Ж = 8

М = Ж + Н = 16

Л = К + Ж + М = 8 + 8 + 16 = 32

П = Л = 32 (так как ищем пути проходящие через город Л)

Р = П = 32

С = П = 32

Т = 32 + 32 = 64

 

Ответ: 64.

Источник: СтатГрад: Тре­ни­ро­воч­ная ра­бо­та 28.11.2017 ИН10203