ЕГЭ и ОГЭФИПИ · понять и решить
Начать подготовку
Меню

Задание EGEINF2F4C39: Графы, таблицы и маршруты

ФИПИ · ЕГЭ · все форматы ответа · 2475 заданий

Открыть решение ↓ Ошибка или пожелание

Тип задачи: Графы, таблицы и маршруты.

Учебные темы: Модели и моделирование. Цели моделирования. Адекватность модели моделируемому объекту или процессу. Формализация прикладных задач. Представление результатов моделирования в виде, удобном для восприятия человеком. Графическое представление данных (схемы, таблицы, графики).; Графы. Основные понятия. Виды графов. Описание графов с помощью матриц смежности, весовых матриц, списков смежности. Решение алгоритмических задач, связанных с анализом графов (построение оптимального пути между вершинами графа, определение количества различных путей между вершинами ориентированного ациклического графа).

Выберите правильный ответ.

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

Укажите таблицу, для которой выполняется условие: “Минимальная стоимость проезда  из А в B не больше 6”.

Стоимость проезда по маршруту складывается из стоимостей проезда между соответствующими  соседними станциями.


 1) 

 

A

B

C

D

E

A

    

3

1

  

B

    

4

  

2

C

3

4

    

2

D

1

        

E

  

2

2

    

 2) 

 

A

B

C

D

E

A

 

 

3

1

1

B

 

 

4

 

 

C

3

4

 

 

2

D

1

 

 

 

 

E

1

 

2

 

  

 3) 

 

A

B

C

D

E

A

    

3

1

  

B

    

4

  

1

C

3

4

    

2

D

1

        

E

  

1

2

    

 4) 

 

A

B

C

D

E

A

 

 

 

1

 

B

 

 

4

 

1

C

 

4

 

4

2

D

1

 

4

 

 

E

 

1

2

 

  

i
СВОЙСТВА ЗАДАНИЯ
КЭС:
2.10 Модели и моделирование. Цели моделирования. Адекватность модели моделируемому объекту или процессу. Формализация прикладных задач. Представление результатов моделирования в виде, удобном для восприятия человеком. Графическое представление данных (схемы, таблицы, графики).
Тип ответа:Выбор ответа
Номер: 2F4C39
НЕ РЕШЕНО Ответить

Решение задания EGEINF2F4C39

Ответ: 3

Решение.
Ищем таблицу, в которой существует маршрут из A в B стоимостью не больше 6. Минимальная стоимость — это наименьшая сумма цен дорог по допустимому маршруту; прямой дороги A–B может не быть.
Пустая клетка запрещает прямой переезд. Все стоимости положительны. Если маршрут посещает станцию повторно, его замкнутый участок можно удалить и уменьшить цену. Поэтому для поиска минимума достаточно путей без повторных станций.
Таблица 1. Все пути без повторений: A → C → B — 7; A → C → E → B — 7.
Минимальная стоимость для таблицы 1: 7. Она больше 6, таблица не подходит.
Таблица 2. Все пути без повторений: A → C → B — 7; A → E → C → B — 7.
Минимальная стоимость для таблицы 2: 7. Она больше 6, таблица не подходит.
Таблица 3. Все пути без повторений: A → C → E → B — 6; A → C → B — 7.
Минимальная стоимость для таблицы 3: 6. Она не больше 6, условие выполнено.
Таблица 4. Все пути без повторений: A → D → C → E → B — 8; A → D → C → B — 9.
Минимальная стоимость для таблицы 4: 8. Она больше 6, таблица не подходит.
В третьей таблице путь A → C → E → B имеет стоимость 3 + 2 + 1 = 6. Все три переезда разрешены соответствующими непустыми клетками.
Проверка: минимумы четырёх таблиц равны 7, 7, 6 и 8. Только третий не превышает установленную границу. Полнота рассмотрения обеспечена перебором всех продолжений из каждой станции без повторений; добавление цикла не может снизить стоимость.
Ответ: 3.

Помочь улучшить сайт

Напишите пожелание к сайту или решению либо сообщите о найденной неточности в задании EGEINF2F4C39.

Сообщение увидит только команда сайта: на странице оно не публикуется.

Комментарии к решению

Комментарии видны всем посетителям сайта.

Комментариев пока нет. Будьте первым.

Чтобы оставить комментарий, войдите или зарегистрируйтесь.