Задача
В этой таблице 20x20 четыре числа по диагонали помечены красным:
Произведение этих чисел равно 26×63×78×14=1788696.
Каково максимальное произведение четырёх последовательных чисел в любом направлении (вверх, вниз, влево, вправо, или по диагонали) в таблице 20×20?
Решение
Порядок операндов в произведении не имеет значения, поэтому половину направлений можно сразу отбросить, так как они будут дублироваться. Например, если взять 4 числа по горизонтали: 1, 2, 3, 4, то произведение можно посчитать начиная с 1 и направо, либо с 4 и налево. Таким образом, отбрасываем направления влево, вверх, и диагонали влево-вверх и вправо-вверх.
Будем двигаться по таблице начиная с левого верхнего угла и не доходя 4 элемента до низа и правого края.
Для начала надо смастерить таблицу из исходных данных. Не набивать же их руками. В этот раз обошлось без программных преобразований, просто сделал несколько поисков и замен по тексту.
Данный массив – одномерный, в котором существуют виртуальные координаты (x, y). Отображение координат на адрес в массиве выглядит так:
addr = y * 20 + x
Так как надо перемножать всего 4 числа, это можно сделать без цикла.
Создадим массив, содержащий смещения нужных для подсчёта элементов:
Это, начиная от текущего элемента: строка вправо, столбец вниз, диагональ вправо-вниз, и диагональ снизу-вправо-вверх:
Сделаем перебор элементов таблицы и вычисление произведения со сравнением:
Функция compare() нужна исключительно для красоты, чтобы не загромождать код:
Она вычисляет произведение по переданным четырём адресам и возвращает большее из двух.
Собственно, массив offsets тоже нужен исключительно для красоты. Все эти значения можно вписать прямо по месту использования, но будет громоздко.
Ссылка на онлайн-компилятор языка C с текстом программы
Задача не стоит никаких оптимизаций, давайте подождём, когда появится что-то более серьёзное.
Вся подборка задач: