Подтема 6 из 6 · дополнительный урок
Диагонали, ладья и число маршрутов
Когда соседей больше двух, когда приходы складывают, а не выбирают, и как сложить результаты нескольких запусков.
Диагонали
Дополнительный урок — для продвинутых. Изредка в задании 18 робот ходит по диагонали или на несколько клеток, спрашивают число маршрутов или сумму нескольких запусков. Задачи основных подтем решаются без этого урока.
Что, если разрешён ещё и шаг по диагонали вправо-вниз?
Появляется третий сосед — клетка слева сверху. Он просто добавляется в МАКС или МИН. Шаг влево-вниз добавил бы соседа справа сверху:
=B2+МИН(A7;На поле 4 × 4 минимум падает с 25 до 7: маршрут A1 → B2 → C3 → D4 собирает 2 + 1 + 2 + 2 и проходит всего четыре клетки. С диагоналями маршруты бывают разной длины. Верхняя строка и левый столбец считаются по-прежнему: у них диагонального соседа нет.
Ладья
А если робот ходит, как ладья, — сразу на несколько клеток вправо или вниз?
Тогда соседи — вся строка левее клетки и весь столбец выше неё. Ладья собирает числа только тех клеток, где останавливается, и может перепрыгивать отрицательные. В формуле — два диапазона, которые растут при растягивании:
=B2+МАКС($A7:A7;Начало диапазона закреплено знаком $, а конец сдвигается: в C8 формула станет =C3+МАКС($A8:B8; — вся строка левее и весь столбец выше. Такие и делают диапазон растущим:
| A | B | C | D | |
|---|---|---|---|---|
| 1 | 3 | -2 | 5 | -4 |
| 2 | -6 | 4 | -1 | 2 |
| 3 | 1 | -3 | 6 | -5 |
| 4 | -2 | 7 | -8 | 4 |
| 5 | ||||
| 6 | 3 | 1 | 8 | 4 |
| 7 | -3 | 5 | 7 | 9 |
| 8 | 4 | 2 | 14 | 9 |
| 9 | 2 | 12 | 6 | 16 |
A6=A1B6скопирована до D6=B1+МАКС($A6:A6)A7скопирована до A9=A2+МАКС(A$6:A6)B7скопирована до D9=B2+МАКС($A7:A7;B$6:B6)
Ладья собирает до 16, а робот обычными шагами на этом поле — только 10: длинные ходы перепрыгивают отрицательные числа.
Число маршрутов
Сколько разных маршрутов ведёт из A1 в D4?
Каждый маршрут приходит в клетку слева или сверху, и это разные маршруты. Поэтому их число не выбирают, а складывают: =A7+B6. В старте — 1.
| Строка | A | B | C | D |
|---|---|---|---|---|
| 1 | 1 | 1 | 1 | 1 |
| 2 | 1 | 2 | 3 | 4 |
| 3 | 1 | 3 | 6 | 10 |
| 4 | 1 | 4 | 10 | 20 |
До D4 ведут 20 маршрутов. Приход сквозь стену даёт 0: со стенами между C1 и C2 и между C4 и D4 маршрутов остаётся 8.
Несколько запусков
Робота запускают дважды, и финиши должны быть разными. Какую наибольшую общую сумму он соберёт?
Монеты перед каждым запуском возвращаются, поэтому запуски независимы: берут два лучших результата разных финишей. На поле 4 × 4 со стенами из подтемы о тупиках наибольшие суммы в тупиках — 16, 23 и 32, наименьшие — 14, 23 и 28. Выпишем их в столбец и сложим два лучших:
=НАИБОЛЬШИЙ(F2:F4;Общий максимум 32 + 23 = 55, общий минимум 14 + 23 = 37 — через . Удвоить лучший результат нельзя: это дважды один и тот же финиш.
Если различаться должны старты, таблицу считают в обратную сторону — от клетки до финиша: монета плюс лучшая из сумм соседей справа и снизу. Тогда в клетке каждого старта окажется его результат, и два лучших снова складывают.
Итого
- Диагональтретий сосед:
=B2+МИН(A7;B6; A6) - Ладья
=B2+МАКС($A7:A7;B$6:B6) - Число маршрутов
=A7+B6, в старте 1, сквозь стену 0 - Несколько запусковсумма k лучших результатов разных финишей
Проверьте себя
Ответь сначала сам, потом открой ответ.
A6:D9. Какая формула наибольших сумм стоит в C8?ОтветСкрыть ответ
=C3+МАКС(B8;ОтветСкрыть ответ
ОтветСкрыть ответ
$A7:A7 при растягивании вправо расширяется?ОтветСкрыть ответ
$, а конец сдвигается вместе с формулой: в D7 будет $A7:C7.Практика
Для проверки ответов нужен JavaScript. Условия, подсказки и решения доступны ниже.
Диагональ вправо-вниз
Робот движется из A1 в C3 по полю 3, 4, 2 / 1, 8, 5 / 6, 2, 7. Разрешены шаги вправо, вниз и по диагонали вправо-вниз, стен нет, учитываются все посещённые числа. Найди максимум и минимум.
Введите два числа через пробел: максимум, затем минимум.
Подсказка
Третий сосед — клетка слева сверху.
Решение
Максимум остаётся 27, минимум уменьшается до 13: маршрут A1 → A2 → B3 → C3, где A2 → B3 — диагональный шаг, сумма 3 + 1 + 2 + 7.
Ответ: 27 13
Диагонали на поле 15 × 15
В файле 18-7.xlsx квадрат 15 × 15, в клетках записаны целые числа. Робот стоит в левой верхней клетке и за один ход переходит на одну клетку вправо, вниз или по диагонали вправо-вниз. Определите максимальную и минимальную суммы чисел в клетках, через которые проходит робот (включая начальную и конечную), на пути в правую нижнюю клетку.
Введите через пробел максимальную сумму, затем минимальную.
Подсказка
Добавь в формулу соседа слева сверху.
Решение
максимум 491, минимум −707.
Формулы в Excel
Поле A1:O15, блок максимума A17:O31:A17: =A1B17: =A17+B1 (вправо до O17)A18: =A17+A2 (вниз до A31)B18: =B2+МАКС(A18;B17;A17) (на B18:O31)Минимум — заменой МАКС на МИН.Ответ: 491 -707
Диагонали на поле без стен
В файле 18-1.xlsx квадрат 15 × 15 без стен. Робот стоит в левой верхней клетке и за один ход переходит на одну клетку вправо, вниз или по диагонали вправо-вниз, забирая монеты во всех клетках, в которых побывал. Определите максимальную и минимальную денежные суммы на пути в правую нижнюю клетку.
Введите через пробел максимальную сумму, затем минимальную.
Подсказка
Третий сосед — клетка слева сверху.
Решение
Максимум не изменился от диагоналей — при положительных монетах длинный путь выгоднее, а минимум упал до 470.
Формулы в Excel
Поле A1:O15, блок максимума A17:O31:A17: =A1B17: =A17+B1 (вправо до O17)A18: =A17+A2 (вниз до A31)B18: =B2+МАКС(A18;B17;A17) (на B18:O31)Ответ: O31; затем МАКС → МИН (Ctrl+H).Ответ: 1940 470
Ладья в строке
Ладья проходит строку 4, −9, 6, −2, 5 слева направо, начиная в первой клетке и останавливаясь в последней. Какую наибольшую сумму остановок она соберёт? А робот одиночными шагами?
Введите два числа через пробел: сумму ладьи, затем робота.
Подсказка
Ладья может остановиться на любой клетке правее.
Решение
Ладья: 4 + 6 + 5 = 15, перепрыгивая −9 и −2. Робот одиночными шагами собирает всё: 4.
Ответ: 15 4
Маршруты на поле 5 × 5
Сколько маршрутов вправо и вниз ведёт из левой верхней клетки в правую нижнюю на поле 5 × 5 без стен?
Введите число.
Подсказка
Число маршрутов клетки — сумма чисел соседей слева и сверху.
Решение
70: в нижней строке таблицы путей 5 × 5 стоят 1, 5, 15, 35, 70; это число последовательностей из четырёх П и четырёх Н.
Ответ: 70
Маршруты со стенами
На поле 4 × 4 из урока стоят стены между C1 и C2 и между C4 и D4. Сколько маршрутов ведёт из A1 в D4?
Введите число.
Подсказка
Стена убирает слагаемое запрещённого прихода.
Решение
8: в C2 теперь приходят только слева, в D4 — только сверху.
Ответ: 8
Маршруты по высотам
В файле 18-9.xlsx поле 15 × 15, в клетках — высота местности. Робот стоит в левой верхней клетке и ходит на одну клетку вправо или вниз, но только если высоты двух клеток различаются не больше чем на 50. Задание 1: определите количество различных маршрутов в правую нижнюю клетку. Задание 2: определите количество клеток, в которые робот не может попасть.
Введите через пробел число маршрутов, затем число недостижимых клеток.
Подсказка
Переход разрешён, если высоты различаются не больше чем на 50.
Решение
46 398 маршрутов, 34 недостижимые клетки.
Формулы в Excel
Блок числа маршрутов, старт: 1;клетка: =ЕСЛИ(ABS(B2-A2)<=50;A18;0) +ЕСЛИ(ABS(B2-B1)<=50;B17;0);недостижимые клетки — с числом 0:=СЧЁТЕСЛИ(блок;0).Ответ: 46398 34
Два запуска из разных стартов
Результаты пяти стартов до финиша: максимумы 70, 95, 60, 95, 81, минимумы 40, 52, 33, 47, 39. Найди общие максимум и минимум за два запуска из разных стартов.
Введите два числа через пробел: максимум, затем минимум.
Подсказка
Два наибольших и два наименьших результата разных стартов.
Решение
Максимум 95 + 95 = 190 (два разных старта с одинаковым результатом), минимум 33 + 39 = 72.
Ответ: 190 72
Два запуска к разным финишам
В файле 18-3.xlsx поле 20 × 20 со стенами. Робот начинает в левой верхней клетке и ходит вправо или вниз; в «угловых» клетках, ограниченных стенами справа и снизу, он останавливается. При повторном запуске конечная клетка должна отличаться от прежней, монеты перед запуском восстанавливаются. Определите максимальную и минимальную денежные суммы, которые робот может собрать суммарно за два запуска.
Введите через пробел максимальную сумму, затем минимальную.
Подсказка
Две наибольшие и две наименьшие суммы «угловых» финишей.
Решение
Две наибольшие суммы «угловых» финишей 2629 + 2497, две наименьшие — 378 + 659.
Формулы в Excel
Поле A1:T20, блок максимума A22:T41:A22: =A1B22: =A22+B1 (вправо до T22)A23: =A22+A2 (вниз до A41)B23: =B2+МАКС(A23;B22) (на B23:T41)У стен — один сосед: =B2+A23 или =B2+B22.Клетки блока, куда не попасть, — пустые.Суммы тупиков выпиши в столбец;ответ: НАИБОЛЬШИЙ(…;1)+НАИБОЛЬШИЙ(…;2)и то же с НАИМЕНЬШИЙ по блоку минимума.Ответ: 5126 1037
Три запуска из разных стартов
В файле 18-6.xlsx поле 20 × 20 со стенами. Робот может начать движение в одной из «угловых» клеток — тех, которые слева и сверху ограничены стенами, включая левую верхнюю, — и ходит вправо или вниз до правой нижней клетки. При повторных запусках начальная клетка должна отличаться от прежних, монеты перед каждым запуском восстанавливаются. Определите максимальную и минимальную денежные суммы, которые робот может собрать суммарно за три запуска.
Введите через пробел максимальную сумму, затем минимальную.
Подсказка
Считай от финиша: блок «к финишу» даёт результат каждого старта.
Решение
Стартов шесть; три наибольших суммы до финиша 2499, 1798, 1303, три наименьших — 388, 611, 711.
Формулы в Excel
Блок «к финишу»: в клетке под T20 — =T20;внутренняя клетка: монета + МАКС(клетка справа;клетка снизу) — то же с МИН во втором блоке.Ответ — сумма трёх наибольших и трёх наименьшихрезультатов стартов (НАИБОЛЬШИЙ, НАИМЕНЬШИЙ).Ответ: 5600 1710
Два старта
В файле 18-6.xlsx поле 20 × 20 со стенами. Робот может начать движение в любой клетке, ограниченной стенами слева и сверху, включая левую верхнюю, и ходит вправо или вниз до правой нижней клетки. Начальные клетки двух запусков различаются, монеты восстанавливаются. Определите максимальную и минимальную денежные суммы, которые робот может собрать суммарно за два запуска.
Введите через пробел максимальную сумму, затем минимальную.
Подсказка
Блок «к финишу» и два лучших результата стартов.
Решение
Два наибольших результата стартов 2499 + 1798, два наименьших 388 + 611.
Формулы в Excel
Блок «к финишу», клетка: монета + МАКС(справа;снизу), второй блок — с МИН. Ответ — сумма двухнаибольших и двух наименьших результатов стартов.Ответ: 4297 999