Категория A2 • задача №4
Условие задачи
Дано:
таблица стоимости перевозок устроена следующим образом: числа, стоящие на пересечениях строк и столбцов таблиц, означают стоимость проезда между соответствующими соседними станциями. Если пересечение строки и столбца пусто, то станции не являются соседними. Стоимость проезда по маршруту складывается из стоимостей проезда между соответствующими соседними станциями.
1) | A | B | C | D | E |
A | 2 | 3 | 6 | ||
B | 2 | 3 | |||
C | 3 | 2 | |||
D | 3 | 2 | 3 | ||
E | 6 | 3 |
2) | A | B | C | D | E |
A | 3 | 3 | 7 | ||
B | 3 | 3 | |||
C | 3 | ||||
D | 3 | 1 | |||
E | 7 | 1 |
3) | A | B | C | D | E |
A | 2 | 4 | 6 | ||
B | 2 | 4 | |||
C | 4 | 2 | |||
D | 4 | 2 | |||
E | 6 |
4) | A | B | C | D | E |
A | 4 | 2 | 7 | ||
B | 4 | 2 | |||
C | 2 | 6 | |||
D | 2 | 6 | 1 | ||
E | 7 | 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 |
Категория A2 • задача №4
Остальные решения из билета №4 для подготовки к ЕГЭ по информатике 2013
Условие задачи (наведите курсор мыши на ссылку) |
Аудиовизуальное решение |
Мультимедийная видеопрезентация |
Решение в формате слайд-шоу |
Текстовое решение |
---|
Комментарии