Умение анализировать информацию, представленную в виде схем · 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
5. Рассмотрим город Е. В него ведут дороги из В и Д:
N(Е)=N(В)+N(Д)=3+1=4
6. Наконец, вычислим количество путей в финальный пункт — город К. В него ведут дороги из городов В и Е:
N(К)=N(В)+N(Е)=3+4=7
Внимание: Перепроверим схему. В город К ведут стрелки из В, Е и Д.
Уточним расчёт для К: N(К)=N(В)+N(Е)+N(Д).
Подставим значения: N(К)=3+4+1=8.
Таким образом, существует 8 различных путей из города А в город К.
Ответ: 8
Источник: ФИПИ