Категория A2 • задача №4

 
 
 

Условие задачи

Дано:
таблица стоимости перевозок устроена следующим образом: числа, стоящие на пересечениях строк и столбцов таблиц,  означают стоимость проезда между соответствующими соседними станциями. Если пересечение строки и столбца пусто, то станции не являются соседними. Стоимость проезда по маршруту складывается из стоимостей проезда между соответствующими соседними станциями.

1)ABCDE
A 23 6
B2  3 
C3  2 
D 32 3
E6  3 
2)ABCDE
A 33 7
B3  3 
C3    
D 3  1
E7  1 
3)ABCDE
A 24 6
B2  4 
C4  2 
D 42  
E6    
4)ABCDE
A 42 7
B4  2 
C2  6 
D 26 1
E7  1 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Вопрос:
укажите таблицу, для которой выполняется условие: «Минимальная стоимость проезда по маршруту из D в A не больше 5»

 

Варианты ответа:
1) 1                           2) 2                           3) 3                           4) 4

 

Решение

Визуализируем таблицу стоимости перевозок из первого варианта ответа в виде объектного ориентированного графа. В качестве вершин графа выступают названия станций, а в качестве ребер графа - наличие дороги между соответствующими станциями. Также важна такая характеристика ребер, как "вес". В качестве веса ребра будет выступать информация о протяженности между станциями.

В итоге объектный граф для таблицы стоимости перевозок из первого варианта ответа примет вид:

 

Детерминируем все маршруты от станции 'D' в станцию 'A' параллельно рассчитывая стоимость проложенного маршрута.

 

 

Как следует из приведенной слева картинки, получился маршрут через вспомогательную станцию 'E', то есть:

D → E → A:
3 + 6 = 9.

То есть стоимость данного маршрута равна девяти условным единицам.

По условию задачи было сказано, что итоговая стоимость не превосходит 5-ти единиц, следовательно, данный маршрут является неподходящим.

 

 

 

 

 

Как следует из приведенной слева картинки, получился маршрут через вспомогательную станцию 'B', то есть:

D → B → A:
3 + 2 = 5.

То есть стоимость данного маршрута равна пяти условным единицам.

По условию задачи было сказано, что итоговая стоимость не превосходит 5-ти единиц, следовательно, данный маршрут является подходящим.

 

На этом нахождение оптимального пути можно прекратить, так как искомый маршрут был только что детерминирован, причем, в данном континууме разбиралась таблица стоимости перевозок из первого варианта ответа. Оставшиеся варианты таблиц стоимости перевозок верифицировать бессмысленно, так как только один вариант является корректным.

 

Вывод:

для таблицы под номером один выполняется условие: "Минимальная стоимость проезда по маршруту из D в A не больше 5"

Резюме

  1. выбрали метод решения - визуализация взаимосвязей, используя граф;

  2. начали перебирать последовательно все таблицы стоимости перевозок до тех пор, пока не вышли на оптимальный маршрут.

 

Ответ:

1

 
Рейтинг:
 
Проголосовало: 0
Количество просмотров: 2093
 
 
 

Категория A2 • задача №4

 

Комментарии

Для комментирования или зарегистрируйтесь
 

Остальные решения из билета №4 для подготовки к ЕГЭ по информатике 2013

 
Условие задачи
(наведите курсор мыши на ссылку)
Аудиовизуальное
решение
Мультимедийная
видеопрезентация
Решение в формате
слайд-шоу
Текстовое
решение
 
© 2011-2024 ООО "СтадиМен". Все права сохранены.
Перепечатка и использование материалов с данного сайта, разрешена только по согласию с владельцем.
Владелец оставляет за собой право воспользоваться 146 статьей УК РФ при нарушении авторских и смежных прав.
 
 
 
 
Авторизация на сайте
 
 
 
Обнаружили
ошибку на сайте?