Электронные таблицы: целочисленные данные

В задании 18 дают файл Excel: квадратное поле, в каждой клетке — монета. Робот идёт по полю по заданным правилам и собирает монеты. Нужно найти, какую наибольшую и какую наименьшую сумму он может собрать. Вот задача, которую мы будем решать всю тему:

«Квадрат разлинован на N × N клеток (1 < N < 30). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз. Квадрат ограничен внешними стенами. Между соседними клетками квадрата также могут быть внутренние стены. Сквозь стену Робот пройти не может. Перед каждым запуском Робота в каждой клетке квадрата лежит монета достоинством от 1 до 100. Посетив клетку, Робот забирает монету с собой; это также относится к начальной и конечной клеткам маршрута Робота. В «угловых» клетках поля — тех, которые справа и снизу ограничены стенами, Робот не может продолжать движение, поэтому накопленная сумма считается итоговой. Таких конечных клеток на поле может быть несколько, включая правую нижнюю клетку поля. Определите максимальную и минимальную денежные суммы среди всех возможных итоговых сумм, которые может собрать Робот, пройдя из левой верхней клетки в конечную клетку маршрута. В ответе укажите два числа — сначала максимальную сумму, затем минимальную. Исходные данные представляют собой электронную таблицу размером N × N, каждая ячейка которой соответствует клетке квадрата. Внутренние и внешние стены обозначены утолщёнными линиями.»

Маршрутов на поле 20 × 20 — миллиарды, перебрать их не выйдет. Поэтому задачу решают таблицей в Excel: для каждой клетки считают лучшую сумму, с которой в неё можно прийти. Каждый шаг сначала проверим руками на маленьком поле 4 × 4. Разберём условие:

Тема состоит из пяти подтем и дополнительного урока — у каждой своя страница. Идём по ним по порядку:

1. Лучшая сумма до клетки — ты сейчас здесь: правило клетки на поле 4 × 4.
2. Таблица в Excel — то же правило формулами.
3. Стены — как стена меняет формулу.
4. Тупики и недостижимые клетки — решим задачу темы целиком: ответ 2629 378.
5. Другие направления и правила — влево и вверх, старт в середине поля, цена шага, запас энергии.
6. Диагонали, ладья и число маршрутов — дополнительный урок для редких задач.

Что такое маршрут и как посчитать его сумму?

Маршрут — цепочка клеток от старта до финиша, а его сумма — сумма монет всех этих клеток. Начнём без стен: робот идёт из левой верхней клетки A1 в правую нижнюю D4. Буквы — столбцы, числа — строки, как адреса ячеек Excel:

Маршрут A1 → B1 → B2 → C2 → C3 → D3 → D4 собирает 2 + 7 + 1 + 8 + 2 + 9 + 2 = 31, а маршрут A1 → A2 → B2 → B3 → B4 → C4 → D4 — 26. Нам нужны наибольшая и наименьшая суммы среди всех маршрутов. На этом поле маршрутов 20, а на поле 20 × 20 — больше 35 миллиардов, так что перебирать их не будем.

Как найти лучшую сумму до клетки B2, не перебирая маршруты?

Посмотри, откуда робот сделал последний шаг. В B2 он пришёл либо слева, из A2, либо сверху, из B1. Лучшая сумма до B2 — её монета плюс лучшая из сумм до A2 и до B1.

До A2 путь один: 2 + 5 = 7. До B1 тоже один: 2 + 7 = 9. Значит, наибольшая сумма до B2 — 1 + 9 = 10, а наименьшая — 1 + 7 = 8.

Сравнивают суммы всего пути до соседей, а не монеты в них. А складывать суммы слева и сверху нельзя: это два разных маршрута, а в клетку робот приходит один раз.

Почему для клетки достаточно помнить одну лучшую сумму?

Два маршрута, пришедшие в одну клетку, дальше могут идти одинаково — и тот, что впереди, так и останется впереди. В C3 можно прийти с суммой 23 (A1 → B1 → C1 → C2 → C3) или с суммой 17 (A1 → A2 → A3 → B3 → C3). Продолжим оба одинаково, через D3 в D4:

Какое бы продолжение мы ни выбрали, к обеим суммам прибавится одно и то же. Поэтому маршрут с суммой 17 уже не обгонит маршрут с 23, и для максимума в C3 достаточно помнить 23.

Как посчитать лучшие суммы для всех клеток поля?

Идём по строкам сверху вниз, а в строке — слева направо: к каждой клетке суммы её соседей слева и сверху уже готовы. Старт A1 — просто его монета, 2. В верхнюю строку приходят только слева, в левый столбец — только сверху: там суммы просто накапливаются. Остальные клетки — по правилу последнего шага. Наибольшие и наименьшие суммы считают в двух отдельных таблицах. Пройди заполнение по шагам:

В D4 получилось 35 — это наибольшая сумма маршрута, и 25 — наименьшая. Маршруты 31 и 26 из начала урока лежат между ними.

Такой способ — решить задачу для каждой клетки и записать ответы в таблицу — называют динамическим программированием. Слово «программирование» тут историческое: считать можно и в Excel, и руками.

• Маршрутклетки от старта до финиша, сумма — их монеты
• Последний шагпри ходах вправо и вниз — слева или сверху
• Правило клеткимонета + лучшая из сумм соседей слева и сверху
• Краястарт — своя монета; верхняя строка и левый столбец — накопленные суммы
• Две таблицымаксимум и минимум считают отдельно
• Поле 4 × 4наибольшая 35, наименьшая 25