ФИПИ · ЕГЭ · все форматы ответа · 2475 заданий
Тип задачи: Оптимальный маршрут по клетчатому полю.
Учебные темы: Двумерные массивы (матрицы). Алгоритмы обработки двумерных массивов: заполнение двумерного числового массива по заданным правилам, поиск элемента в двумерном массиве, вычисление максимума (минимума) и суммы элементов двумерного массива, перестановка строк и столбцов двумерного массива; Динамическое программирование как метод решения задач с сохранением промежуточных результатов. Задачи, решаемые с помощью динамического программирования: вычисление рекурсивных функций, подсчёт количества вариантов, задачи оптимизации; Анализ данных с помощью электронных таблиц. Вычисление суммы, среднего арифметического, наибольшего (наименьшего) значения диапазона. Вычисление коэффициента корреляции двух рядов данных. Построение столбчатых, линейчатых и круговых диаграмм. Построение графиков функций. Подбор линии тренда, решение задач прогнозирования. Решение задач оптимизации с помощью электронных таблиц.
| КЭС: | 4.2 Анализ данных с помощью электронных таблиц. Вычисление суммы, среднего арифметического, наибольшего (наименьшего) значения диапазона. Вычисление коэффициента корреляции двух рядов данных. Построение столбчатых, линейчатых и круговых диаграмм. Построение графиков функций. Подбор линии тренда, решение задач прогнозирования. Решение задач оптимизации с помощью электронных таблиц 4.3 Дискретизация при математическом моделировании непрерывных процессов. Моделирование движения. Моделирование биологических систем. Математические модели в экономике. Вычислительные эксперименты с моделями. Обработка результатов эксперимента. Метод наименьших квадратов. Оценка числовых параметров моделируемых объектов и процессов. Восстановление зависимостей по результатам эксперимента 4.4 Вероятностные модели. Методы Монте-Карло. Имитационное моделирование. Системы массового обслуживания 4.5 Табличные (реляционные) базы данных. Таблица – представление сведений об однотипных объектах. Поле, запись. Ключ таблицы. Работа с готовой базой данных. Заполнение базы данных. Поиск, сортировка и фильтрация данных. Запросы на выборку данных. Запросы с параметрами. Вычисляемые поля в запросах. Многотабличные базы данных. Типы связей между таблицами. Внешний ключ. Целостность базы данных. Запросы к многотабличным базам данных 4.6 Текстовый процессор. Средства поиска и автозамены в текстовом процессоре. Структурированные текстовые документы. Сноски, оглавление. Правила цитирования источников и оформления библиографических ссылок |
| Тип ответа: | Краткий ответ |
Ответ: 438 669
Решение.
В приложенной таблице заполнен квадрат A1:O15, то есть N = 15. Робот делает 14 шагов вправо и 14 вниз, посещая 29 клеток. Плата берётся также за начальную A1 и конечную O15.
Введём две вспомогательные таблицы. В ячейке одной будем хранить наименьшую стоимость пути от A1 до соответствующей клетки, в ячейке другой — наибольшую.
В стартовой клетке обе стоимости равны 22. В первой строке путь единственный: можно идти только вправо, поэтому складываем стоимость предыдущей клетки и текущую плату. В первом столбце аналогично идём только вниз.
В любую внутреннюю клетку можно прийти только сверху или слева. Пусть a — плата текущей клетки, L и U — уже вычисленные стоимости для левой и верхней клеток. Для минимальной стоимости берём a + min(L, U), для максимальной — a + max(L, U). Все возможные последние шаги учтены; к оптимальному пути до предшествующей клетки можно дописать нужный шаг. Поэтому эта рекурсия даёт и оценку, и достигающий её маршрут.
Заполним вспомогательные таблицы по строкам. Можно разместить таблицу минимума в A18:O32, а максимума — в A35:O49:
| Ячейка или диапазон | Действие |
|---|---|
| A18 | =A1 |
| B18, затем протянуть до O18 | =A18+B1 |
| A19, затем протянуть до A32 | =A18+A2 |
| B19, затем заполнить B19:O32 | =B2+МИН(A19;B18) |
| A35 | =A1 |
| B35, затем протянуть до O35 | =A35+B1 |
| A36, затем протянуть до A49 | =A35+A2 |
| B36, затем заполнить B36:O49 | =B2+МАКС(A36;B35) |
Все ссылки относительные. В английской локализации функции называются MIN и MAX. Первые строки и столбцы заполняем до внутренних клеток.
В O32 получаем 438, в O49 — 669. Проверка. Восстановим маршруты, каждый раз выбирая предшественника, по которому была вычислена стоимость. В таблице ниже перечислены последовательные группы клеток от начала до конца:
| Маршрут | Клетки по порядку | Платы |
|---|---|---|
| Минимум | A1, B1, B2, B3, C3 | 22 + 21 + 11 + 12 + 18 |
| Минимум | D3, D4, D5, E5, F5 | 20 + 11 + 15 + 14 + 27 |
| Минимум | G5, G6, H6, I6, J6 | 16 + 15 + 11 + 15 + 11 |
| Минимум | J7, K7, L7, L8, L9 | 12 + 13 + 15 + 17 + 14 |
| Минимум | L10, L11, L12, L13, L14 | 10 + 14 + 13 + 12 + 11 |
| Минимум | M14, N14, N15, O15 | 14 + 24 + 18 + 12 |
| Максимум | A1, A2, A3, A4, A5 | 22 + 28 + 29 + 13 + 15 |
| Максимум | A6, B6, B7, C7, D7 | 24 + 26 + 24 + 28 + 28 |
| Максимум | D8, D9, E9, E10, E11 | 18 + 29 + 16 + 28 + 17 |
| Максимум | E12, F12, F13, G13, G14 | 23 + 30 + 28 + 24 + 16 |
| Максимум | G15, H15, I15, J15, K15 | 25 + 29 + 25 + 24 + 21 |
| Максимум | L15, M15, N15, O15 | 20 + 29 + 18 + 12 |
Каждая последовательность содержит 29 клеток; соседние клетки соединены разрешённым шагом вправо или вниз. Суммы плат равны 438 и 669 соответственно. Обратный расчёт от конечной клетки к начальной независимо даёт те же границы.
В ответе сначала записываем минимальную сумму, затем максимальную.
Ответ: 438 669.
Напишите пожелание к сайту или решению либо сообщите о найденной неточности в задании EGEINFF3A05F.
Сообщение увидит только команда сайта: на странице оно не публикуется.
Комментарии к решению
Комментарии видны всем посетителям сайта.
Комментариев пока нет. Будьте первым.
Чтобы оставить комментарий, войдите или зарегистрируйтесь.