B9 (повышенный уровень, время – 3 мин)
Тема: Графы. Поиск путей Что нужно знать: · если в город R можно приехать только из городов X, Y, и Z, то число различных путей из города A в город R равно сумме числа различных путей проезда из A в X, из A в Y и из A в Z, то есть , где обозначает число путей из вершины A в некоторую вершину Q · число путей конечно, если в графе нет циклов – замкнутых путей Пример задания: На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К?
Решение (1 вариант, подстановки): 1) начнем считать количество путей с конца маршрута – с города К 2) будем обозначать через NX количество различных путей из города А в город X 3) общее число путей обозначим через N 4) по схеме видно, что NБ = NГ = 1 5) очевидно, что если в город X можно приехать только из Y, Z, то NX = NY + NZ, то есть нужно сложить число путей, ведущих из A во все города, откуда можно приехать в город X 6) поскольку в K можно приехать из Е, Д, Ж или И, поэтому N = NК = NД + NЕ + NЖ + NИ 7) в город И можно приехать только из Д, поэтому NИ = NД 8) в город Ж можно приехать только из Е и В, поэтому NЖ = NЕ + NВ 9) подставляем результаты пп. 6 и 7 в формулу п. 5: N = NВ + 2NЕ + 2NД 10) в город Д можно приехать только из Б и В, поэтому NД = NБ + NВ так что N = 2NБ + 3NВ + 2NЕ 11) в город Е можно приехать только из Г, поэтому NЕ = NГ так что N = 2NБ + 3NВ + 2NГ 12) по схеме видно, что NБ = NГ = 1, кроме того, NВ = 1 + NБ + NГ = 3 13) окончательно N = 2NБ + 3NВ + 2NГ = 2·1 + 3·3 + 2·1 = 13 14) Ответ: 13. Решение (2 вариант, удобная форма записи): 1) начнем считать количество путей с конца маршрута – с города К 2) записываем для каждой вершины, из каких вершин можно в нее попасть К ИДЖЕ И Д Ж ВЕ Е Г Д БВ Г А В АБГ Б А 3) теперь для удобства «обратного хода» вершины можно отсортировать так[1], чтобы сначала шли все вершины, в которые можно доехать только из начальной точки А: Б А Г А затем на каждом шаге добавляем те вершины, в которые можно доехать из уже добавленных в список (и из исходной точки): В АБГ Е Г далее добавляем все вершины, куда можно доехать из А, Б, Г, В и Е: Д БВ Ж ВЕ на следующем шаге добавляем вершину И И Д и, наконец, конечную. вершину К ИДЖЕ именно в таком порядке мы и будем вычислять количество путей для каждой вершины 4) теперь идем по полученному списку вершин, полагая, что количество вариантов попасть в вершину равно суммарному количеству вариантов попасть в ее непосредственных предшественников. NБ = 1, NГ = 1 NВ = 1+1+1 = 3, NЕ = 1 NД = 1+3 = 4, NЖ = 3 + 1 = 4 NИ = 4, N = NК = 4 + 4 + 4 + 1 = 13 5) заметим, что вершины можно и не сортировать специально, а просто выбирать возможный порядок вычисления: проверять, какие значения известны и какие можно рассчитать с их помощью на следующем шаге 6) Ответ: 13.
Решение (3 вариант, перебор вершин по алфавиту): 1) Запишем вершины в алфавитном порядке и для каждой из них определим, из каких вершин можно в нее попасть Б А В АБГ Г А Д БВ Е Г Ж ВЕ И Д К ИДЖЕ 2) теперь определяем количество путей; сначала ставим 1 для тех вершин, в которые можно проехать только из начальной (А):
3) затем на каждом шаге добавляем те вершины, в которые можно доехать из уже добавленных в список (и из исходной точки):
4) следующий шаг
5) и последние 2 шага
6) Ответ: 13. Решение (4 вариант, перебор всех путей с начала, А. Яфарова): 1) запишем все вершины, в которые есть прямой путь из вершины A: Б, В и Г; получается три начальных отрезка: АБ, АВ, АГ 2) рассмотрим маршрут АБ: из Б можно ехать в В и Д, поэтому получаем два маршрута: АБВ, АБД 3) рассматриваем конечные точки этих маршрутов: из В можно ехать в Д и Ж, а из Д – в И и К: АБВД, АБВЖ, АБДИ, АБДК 4) снова смотрим на конечные точки: из Д едем в И и К, из Ж и И – только в К: АБВДИ, АБВДК, АБВЖК, АБДИК, АБДК 5) из И едем только в К, таким образом, все возможные маршруты, содержащие участок АБ, доведены до конечной точки К, всего 5 таких маршрутов: АБВДИК, АБВДК, АБВЖК, АБДИК, АБДК 6) затем аналогично рассматриваем маршруты, которые начинаются с АВ: АВД, АВЖ АВДИ, АВДК, АВЖК АВДИК, АВДК, АВЖК всего 3 маршрута 7) наконец, остается рассмотреть маршруты, которые начинаются с АГ: АГВ, АГЕ АГВД, АГВЖ, АГЕЖ, АГЕК АГВДИ, АГВДК, АГВЖК, АГЕЖК, АГЕК АГВДИК, АГВДК, АГВЖК, АГЕЖК, АГЕК всего 5 маршрутов 8) складываем количество маршрутов для всех начальных участков: 5 + 3 + 5 = 13 9) Ответ: 13.
Решение (5 вариант, графический, О.О. Грущак, КузГПА): 1) Главную идею решения: (число дорог в город N есть сумма дорог, приводящих в города, из которых есть прямой проезд в город N), отразим на самой схеме, показывая на ней ЧИСЛО ДОРОГ, приводящих в каждый город. 2) Последовательность очевидна: начинаем с Б и Г (городов, куда есть по 1-й дороге из А) 3) Посчитаем дороги в В: 1 (из A)+ 1(дороги города Б)+ 1(дороги города В)= 3 4) Аналогично посчитаем дороги в Д, И, Е, Ж: 5) Определяем число дорог в город К, как сумму дорог в города, с которыми он связан: Д, И, Ж, Е. 6) Ответ: 13. Задачи для тренировки[2]: 1) На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К? 2) На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город З? 3) На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город З? 4) На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К?
5) На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К?
6) На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город Ж? 7) На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город Ж? 8) На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город Ж? 9) На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город Ж? 10) На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город Ж?
11) На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К?
12) На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К?
13) На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К?
14) На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К?
15) На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К?
16) На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К?
17) На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город И?
18) На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город И?
19) На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город И?
20) На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город З? 21) На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К?
[1] Такая процедура называется топологической сортировкой графа. [2] Источники заданий: 1. Тренировочные работы МИОО 2011-2012. 2. Авторские разработки.
Популярное: Как выбрать специалиста по управлению гостиницей: Понятно, что управление гостиницей невозможно без специальных знаний. Соответственно, важна квалификация... Как вы ведете себя при стрессе?: Вы можете самостоятельно управлять стрессом! Каждый из нас имеет право и возможность уменьшить его воздействие на нас... ©2015-2020 megaobuchalka.ru Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. (1069)
|
Почему 1285321 студент выбрали МегаОбучалку... Система поиска информации Мобильная версия сайта Удобная навигация Нет шокирующей рекламы |