Новая Школа - онлайн-школа подготовки к ЕГЭ
Задача Задача №3838024
А
Аноним
12 часов назад · публичный вопрос
А
Аноним

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

Запрос пользователя

Реши задание на изображении

Ответ нейросети
12 часов назад

Я решил все пять задач на подсчёт путей в графах. В основе решения лежит метод динамического программирования: количество путей в каждый город равно сумме количеств путей во все города, из которых в него ведут стрелки. Для стартового города \(A\) количество путей равно 1.

1. Схема 1 (из \(A\) в \(Л\))

Считаем последовательно:

  • \(Б = 1\), \(Г = 1\)
  • \(В = 1 (Б) + 1 (Г) = 2\)
  • \(Е = 1 (Б) + 1 (Г) = 2\)
  • \(Ж = 2 (В) + 1 (Г) = 3\)
  • \(Д = 2 (В) + 2 (Е) = 4\)
  • \(К = 2 (Е) + 3 (Ж) = 5\)
  • \(Л = 4 (Д) + 2 (Е) + 3 (Ж) + 5 (К) = \mathbf{14}\)

Ответ: 14

2. Схема 2 (из \(A\) в \(К\))

  • \(Б = 1\), \(Г = 1\)
  • \(В = 1 (А) + 1 (Б) + 1 (Г) = 3\)
  • \(Д = 1 (Г) + 3 (В) = 4\)
  • \(Е = 1 (Г) + 3 (В) = 4\)
  • \(К = 3 (В) + 4 (Д) + 4 (Е) = \mathbf{11}\)

Ответ: 11

3. Схема 3 (из \(A\) в \(Л\))

  • \(Б = 1\), \(Г = 1\)
  • \(В = 1 (А) + 1 (Б) + 1 (Г) = 3\)
  • \(Е = 1 (Б) + 3 (В) = 4\)
  • \(З = 1 (Г) + 3 (В) = 4\)
  • \(Д = 3 (В) + 4 (Е) = 7\)
  • \(Ж = 7 (Д) + 4 (Е) + 4 (З) = 15\)
  • \(И = 7 (Д) + 4 (Е) + 15 (Ж) = 26\)
  • \(К = 4 (З) + 15 (Ж) = 19\)
  • \(Л = 15 (Ж) + 26 (И) + 19 (К) = \mathbf{60}\)

Ответ: 60

4. Схема 4 (из \(A\) в \(Л\))

Здесь есть дополнительная дорога из \(В\) в \(Ж\) по сравнению с предыдущей схемой.

  • \(Б = 1\), \(Г = 1\)
  • \(В = 1 (А) + 1 (Б) + 1 (Г) = 3\)
  • \(Е = 1 (Б) + 3 (В) = 4\)
  • \(З = 1 (Г) + 3 (В) = 4\)
  • \(Д = 3 (В) + 4 (Е) = 7\)
  • \(Ж = 3 (В) + 7 (Д) + 4 (Е) + 4 (З) = 18\)
  • \(И = 7 (Д) + 4 (Е) + 18 (Ж) = 29\)
  • \(К = 4 (З) + 18 (Ж) = 22\)
  • \(Л = 18 (Ж) + 29 (И) + 22 (К) = \mathbf{69}\)

Ответ: 69

5. Схема 5 (из \(A\) в \(D\))

  • \(B = 1\), \(G = 1\)
  • \(H = 1 (A) + 1 (B) + 1 (G) = 3\)
  • \(C = 1 (B) = 1\)
  • \(E = 1 (B) + 1 (G) + 3 (H) + 1 (C) = 6\)
  • \(F = 1 (G) + 6 (E) = 7\)
  • \(D = 1 (C) + 6 (E) + 7 (F) = \mathbf{14}\)

Ответ: 14

Главный принцип: всегда записывай для каждого города сумму путей тех городов, от которых к нему идут стрелки, и двигайся слева направо.