Просмотр содержимого документа
«2.3.Еще пример задания»
Еще пример задания:
Таблица стоимости перевозок устроена следующим образом: числа, стоящие на пересечениях строк и столбцов таблиц, означают стоимость проезда между соответствующими соседними станциями. Если пересечение строки и столбца пусто, то станции не являются соседними. Укажите таблицу, для которой выполняется условие: «Минимальная стоимость проезда из А в B не больше 6». Стоимость проезда по маршруту складывается из стоимостей проезда между соответствующими соседними станциями.
1) | 2) | 3) | 4) |
| A | B | C | D | Е | A | | | 3 | 1 | | B | | | 4 | | 2 | C | 3 | 4 | | | 2 | D | 1 | | | | | Е | | 2 | 2 | | | | | A | B | C | D | Е | A | | | 3 | 1 | 1 | B | | | 4 | | | C | 3 | 4 | | | 2 | D | 1 | | | | | Е | 1 | | 2 | | | | | A | B | C | D | Е | A | | | 3 | 1 | 4 | B | | | 4 | | 2 | C | 3 | 4 | | | 2 | D | 1 | | | | | Е | 4 | 2 | 2 | | | | | A | B | C | D | Е | A | | | | 1 | | B | | | 4 | | 1 | C | | 4 | | 4 | 2 | D | 1 | | 4 | | | Е | | 1 | 2 | | | |
Решение (вариант 1):
нужно рассматривать все маршруты из А в В, как напрямую, так и через другие станции
рассмотрим таблицу 1:
из верхней строки таблицы следует, что из А в В напрямую везти нельзя, только через C (стоимость перевозки А-С равна 3) или через D (стоимость перевозки из А в D равна 1)
предположим, что мы повезли через C; тогда из третьей строки видим, что из C можно ехать в В, и стоимость равна 4
таким образом общая стоимость перевозки из А через С в В равна 3 + 4 = 7
кроме того, из С можно ехать не сразу в В, а сначала в Е:
а затем из Е – в В (стоимость также 2),
так что общая стоимость этого маршрута равна 3 + 2 + 2 = 7
теперь предположим, что мы поехали из А в D (стоимость 1); из четвертой строки таблицы видим, что из D можно ехать только обратно в А, поэтому этим путем в В никак не попасть:
таким образом, для первой таблицы минимальная стоимость перевозки между А и В равна 7; заданное условие «не больше 6» не выполняется
аналогично рассмотрим вторую схему; возможные маршруты из А в В:
, стоимость 7
, стоимость 7
таким образом, минимальная стоимость 7, условие не выполняется
для третьей таблицы:
, стоимость 7
, стоимость 6
, стоимость 7
таким образом, минимальная стоимость 6, условие выполняется
для четвертой:
, стоимость 9
, стоимость 8
минимальная стоимость 8, условие не выполняется
условие «не больше 6» выполняется только для таблицы 3
таким образом, правильный ответ – 3.
Возможные ловушки и проблемы: метод ненагляден, легко запутаться и пропустить решение с минимальной стоимостью |
Решение (вариант 2, с рисованием схемы):
для каждой таблицы нарисуем соответствующую ей схему дорог, обозначив стоимость перевозки рядом с линиями, соединяющими соседние станции:
1) | 2) | 3) | 4) |
| A | B | C | D | Е | A | | | 3 | 1 | | B | | | 4 | | 2 | C | 3 | 4 | | | 2 | D | 1 | | | | | Е | | 2 | 2 | | | | | A | B | C | D | Е | A | | | 3 | 1 | 1 | B | | | 4 | | | C | 3 | 4 | | | 2 | D | 1 | | | | | Е | 1 | | 2 | | | | | A | B | C | D | Е | A | | | 3 | 1 | 4 | B | | | 4 | | 2 | C | 3 | 4 | | | 2 | D | 1 | | | | | Е | 4 | 2 | 2 | | | | | A | B | C | D | Е | A | | | | 1 | | B | | | 4 | | 1 | C | | 4 | | 4 | 2 | D | 1 | | 4 | | | Е | | 1 | 2 | | | |
теперь по схемам определяем кратчайшие маршруты для каждой таблицы:
1: или , стоимость 7
2: или , стоимость 7
3: , стоимость 6
4: , стоимость 8
условие «не больше 6» выполняется только для таблицы 3
таким образом, правильный ответ – 3.
Возможные ловушки и проблемы: нужно внимательно строить схемы по таблицам, этот дополнительный переход (от табличных моделей к графическим) повышает наглядность, но добавляет еще одну возможность для ошибки наглядность схемы зависит от того, как удачно вы выберете расположение ее узлов; один из подходов – сначала расставить все узлы равномерно на окружности, нарисовать все связи и посмотреть, как можно расположить узлы более удобно по невнимательности можно пропустить решение с минимальной стоимостью |