Умение анализировать информацию, представленную в виде схем · 52 задания
- Задание №9№9
На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Ско…
Графы
- Задание №9№9
На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж и К. Покаждой дороге можно двигаться только в одном направлении, указанном стрелкой.…
Графы
- Задание №9№9
На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Ско…
Графы
- Задание №9№9
На рисунке – схема дорог, связывающих города A , B , C , D , E , F , G , H . По каждой дороге можно двигаться только в одном направлении, указанном ст…
Графы
- Задание №9№9
На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Ско…
Графы
- Задание №9№9
На рисунке – схема дорог, связывающих города А, B, C, D, E, G, H, F. Покаждой дороге можно двигаться только в одном направлении, указанном стрелкой. С…
Графы
- Задание №9№9
На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж и К. Покаждой дороге можно двигаться только в одном направлении, указанном стрелкой.…
Графы
- Задание №9№9
На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж и К. Покаждой дороге можно двигаться только в одном направлении, указанном стрелкой.…
Графы
- Задание №9№9
На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Ско…
Графы
- Задание №9№9
На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К иЛ. По каждой дороге можно двигаться только в одном направлении, указанном с…
Графы
- Задание №9№9
На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж и К. Покаждой дороге можно двигаться только в одном направлении, указанном стрелкой.…
Графы
- Задание №9№9
На рисунке – схема дорог, связывающих города А, B, C, D, E, F, G, H. Покаждой дороге можно двигаться только в одном направлении, указанном стрелкой. С…
Графы
На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К?
Правильный ответ
8
Пояснение
Решение. Для решения этой задачи воспользуемся методом динамического программирования. Мы будем последовательно вычислять количество путей, ведущих в каждый город, суммируя количество путей из тех городов, из которых в него ведут стрелки.
Обозначим через N(X) количество различных путей из города А в город X.
1. Начнём с начального пункта. Для города А существует только один путь (начальная точка):
N(A)=1
2. Теперь найдём значения для городов, в которые можно попасть напрямую из А:
В город Б ведёт только одна стрелка из А:
N(Б)=N(A)=1
В город Г ведёт только одна стрелка из А:
N(Г)=N(A)=1
3. Перейдём к городу В. В него ведут стрелки из Б, А и Г:
N(В)=N(Б)+N(A)+N(Г)=1+1+1=3
4. Теперь определим количество путей для городов Д и Е:
В город Д ведёт стрелка только из Б:
N(Д)=N(Б)=1
В город Е ведёт стрелка только из Г:
N(Е)=N(Г)=1
5. Наконец, вычислим количество путей в конечный пункт — город К. В него ведут стрелки из Д, В и Е:
N(К)=N(Д)+N(В)+N(Е)
Подставим уже найденные значения:
N(К)=1+3+1=5
Стоп! Перепроверим схему дорог внимательно.
На рисунке видно, что из города В также идут дороги в Д и Е, а не только в К. Пересчитаем:
N(А)=1
N(Б)=N(А)=1
N(Г)=N(А)=1
N(В)=N(Б)+N(А)+N(Г)=1+1+1=3
Теперь Д: в него ведут стрелки из Б и В:
N(Д)=N(Б)+N(В)=1+3=4
Теперь Е: в него ведут стрелки из В и Г:
N(Е)=N(В)+N(Г)=3+1=4
Теперь К: в него ведут стрелки только из Д и Е:
N(К)=N(Д)+N(Е)=4+4=8
Таким образом, общее количество путей из города А в город К равно 8.
Ответ: 8
Источник: ФИПИ