ФИПИ · ЕГЭ · все форматы ответа · 2475 заданий
Тип задачи: Оптимальный маршрут по клетчатому полю.
Учебные темы: Двумерные массивы (матрицы). Алгоритмы обработки двумерных массивов: заполнение двумерного числового массива по заданным правилам, поиск элемента в двумерном массиве, вычисление максимума (минимума) и суммы элементов двумерного массива, перестановка строк и столбцов двумерного массива; Динамическое программирование как метод решения задач с сохранением промежуточных результатов. Задачи, решаемые с помощью динамического программирования: вычисление рекурсивных функций, подсчёт количества вариантов, задачи оптимизации; Анализ данных с помощью электронных таблиц. Вычисление суммы, среднего арифметического, наибольшего (наименьшего) значения диапазона. Вычисление коэффициента корреляции двух рядов данных. Построение столбчатых, линейчатых и круговых диаграмм. Построение графиков функций. Подбор линии тренда, решение задач прогнозирования. Решение задач оптимизации с помощью электронных таблиц.
| КЭС: | 4.2 Анализ данных с помощью электронных таблиц. Вычисление суммы, среднего арифметического, наибольшего (наименьшего) значения диапазона. Вычисление коэффициента корреляции двух рядов данных. Построение столбчатых, линейчатых и круговых диаграмм. Построение графиков функций. Подбор линии тренда, решение задач прогнозирования. Решение задач оптимизации с помощью электронных таблиц 4.3 Дискретизация при математическом моделировании непрерывных процессов. Моделирование движения. Моделирование биологических систем. Математические модели в экономике. Вычислительные эксперименты с моделями. Обработка результатов эксперимента. Метод наименьших квадратов. Оценка числовых параметров моделируемых объектов и процессов. Восстановление зависимостей по результатам эксперимента 4.4 Вероятностные модели. Методы Монте-Карло. Имитационное моделирование. Системы массового обслуживания 4.5 Табличные (реляционные) базы данных. Таблица – представление сведений об однотипных объектах. Поле, запись. Ключ таблицы. Работа с готовой базой данных. Заполнение базы данных. Поиск, сортировка и фильтрация данных. Запросы на выборку данных. Запросы с параметрами. Вычисляемые поля в запросах. Многотабличные базы данных. Типы связей между таблицами. Внешний ключ. Целостность базы данных. Запросы к многотабличным базам данных 4.6 Текстовый процессор. Средства поиска и автозамены в текстовом процессоре. Структурированные текстовые документы. Сноски, оглавление. Правила цитирования источников и оформления библиографических ссылок |
| Тип ответа: | Краткий ответ |
Ответ: 1120 1035
Решение.
Откроем приложенную электронную таблицу. Исходные числа занимают диапазон A1:T20: поле имеет размер 20 × 20. Начинаем в A1 и движемся только вправо или вниз. Число в каждой посещённой клетке, включая начало и финиш, прибавляется к сумме.
Нужно обязательно дойти до T20. Маршрут, закончившийся у стен раньше, в ответ не входит.
В исходном поле найдено 13 внутренних границ между соседними клетками, через которые проход запрещён.
Будем хранить для каждой достижимой клетки две величины: L — наименьшую сумму от A1 до неё, H — наибольшую. Для A1 обе величины равны числу в самой A1: 28.
В любую другую клетку можно прийти только из соседней слева или сверху. Переход слева разрешён, если нет стены между этими клетками; переход сверху — если нет стены над текущей клеткой. Недостижимого соседа не используем.
Если оба входа разрешены, прибавим число текущей клетки к меньшей из двух величин L и к большей из двух величин H. Если допустимый вход один, берём только его. Если нет ни одного, помечаем клетку «нет пути», а не нулём.
Это динамическое программирование: любой путь в текущую клетку заканчивается одним из допустимых входов. Поэтому выбор лучшего пути до предшественника перебирает все возможности последнего шага. Обрабатывая строки сверху вниз, а клетки в строке слева направо, получаем точные минимум и максимум для всего поля.
Для расчёта в редакторе таблиц создадим под исходными числами блок максимумов с началом в A22. В A22 введём =A1. Например, значение для B2 окажется в B23: при двух допустимых входах формула имеет вид =B2+МАКС(A23;B22). Если вход перекрыт стеной или ведёт из недостижимой клетки, соответствующую ссылку исключаем. Начальную клетку общей формулой не заменяем.
Первую строку заполняем только по входу слева, первый столбец — только по входу сверху. После каждой стены отдельно проверяем достижимость. Для минимумов создадим такой же блок, заменив МАКС на МИН и сохранив все ограничения переходов. Нельзя протянуть общую формулу через стены без исправления ссылок.
Контрольные значения начала таблицы:
| Клетка | Число | L | H |
|---|---|---|---|
| A1 | 28 | 28 | 28 |
| B1 | 29 | 57 | 57 |
| A2 | 27 | 55 | 55 |
| B2 | 28 | 83 | 85 |
Итог в единственной разрешённой конечной клетке T20:
| Финиш | Минимум | Максимум |
|---|---|---|
| T20 | 1035 | 1120 |
В T20 получаем L = 1035, H = 1120. Значения в других тупиках не учитываем.
Проверка. Восстановим оба оптимальных маршрута, каждый раз выбирая предшественника, давшего записанную сумму. Ниже указаны посещённые столбцы по строкам; диапазон включает оба края. Между строками спускаемся в том столбце, в котором закончился предыдущий отрезок. Знак «—» означает, что маршрут завершился раньше.
| Строка | Минимальный: столбцы | Сумма | Максимальный: столбцы | Сумма |
|---|---|---|---|---|
| 1 | A | 28 | A | 28 |
| 2 | A–B | 55 | A | 27 |
| 3 | B–H | 186 | A | 29 |
| 4 | H | 25 | A | 30 |
| 5 | H | 25 | A | 26 |
| 6 | H–J | 79 | A–B | 58 |
| 7 | J | 27 | B | 30 |
| 8 | J | 25 | B | 30 |
| 9 | J–P | 186 | B–C | 57 |
| 10 | P–Q | 54 | C | 28 |
| 11 | Q–R | 51 | C | 30 |
| 12 | R | 27 | C | 25 |
| 13 | R | 29 | C | 29 |
| 14 | R–S | 50 | C–D | 60 |
| 15 | S | 26 | D–G | 112 |
| 16 | S | 25 | G | 30 |
| 17 | S | 25 | G–N | 229 |
| 18 | S–T | 54 | N–Q | 115 |
| 19 | T | 29 | Q–S | 88 |
| 20 | T | 29 | S–T | 59 |
| Итого | 1035 | 1120 |
Все переходы этих маршрутов разрешены. Суммы чисел исходного файла дают 1035 и 1120; начальная и конечная клетки учтены ровно один раз. Таблица динамического программирования доказывает, что меньшая и большая суммы невозможны.
По условию сначала записываем максимум, затем минимум.
Ответ: 1120 1035.
Напишите пожелание к сайту или решению либо сообщите о найденной неточности в задании EGEINF5D4CE0.
Сообщение увидит только команда сайта: на странице оно не публикуется.
Комментарии к решению
Комментарии видны всем посетителям сайта.
Комментариев пока нет. Будьте первым.
Чтобы оставить комментарий, войдите или зарегистрируйтесь.