Умение анализировать информацию, представленную в виде схем · 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. Покаждой дороге можно двигаться только в одном направлении, указанном стрелкой. С…
Графы
На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К иЛ. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А вгород Л?
Правильный ответ
27
Пояснение
Решение. Для решения этой задачи мы воспользуемся методом динамического программирования. Суть метода заключается в том, что количество путей в текущий город равно сумме количеств путей во все города, из которых в него ведут прямые дороги.
Обозначим через N(X) количество различных путей из города А в город X. Начнем последовательный расчет для каждого города:
1. Для начального пункта А принимаем: N(А)=1.
2. Город Б: в него ведет только одна дорога из А. N(Б)=N(А)=1.
3. Город Г: в него ведет только одна дорога из А. N(Г)=N(А)=1.
4. Город В: в него ведут дороги из А, Б и Г. N(В)=N(А)+N(Б)+N(Г)=1+1+1=3.
5. Город Д: в него ведут дороги из Б и В. N(Д)=N(Б)+N(В)=1+3=4.
6. Город Е: в него ведут дороги из В и Г. N(Е)=N(В)+N(Г)=3+1=4.
7. Город Ж: в него ведут дороги из Д, В и Е. N(Ж)=N(Д)+N(В)+N(Е)=4+3+4=11.
8. Город З: в него ведет только одна дорога из Д. N(З)=N(Д)=4.
9. Город И: в него ведет только одна дорога из Е. N(И)=N(Е)=4.
10. Город К: в него ведут дороги из З, Ж и И. N(К)=N(З)+N(Ж)+N(И)=4+11+4=19.
11. Город Л: в него ведут дороги из З, К и И. N(Л)=N(З)+N(К)+N(И)=4+19+4=27.
Таким образом, общее количество различных путей из города А в город Л составляет 27.
Ответ: 27
Источник: ФИПИ