Обход массива по улитке.

Опубликовано Опубликовано в рубрике PHP, Theory, ООП

Доброго дня, уважаемые посетители моего блога!

Не так давно мне на глаза попалась задачка, которую кому-то из хабравчан предложили для решения на собеседовании. Суть ее состояла в том, чтобы заполнить квадратную матрицу с размерностью n*n числами от 1 до n^2 по спирали, закручивающейся от элемента [0, 0] к центру по часовой стрелке.

Поняв, что мысль о решении не дает мне покоя, я взялся вспоминать первый курс института 🙂

Минут 20 я рисовал квадратные матрицы разных размеров, пытаясь выявить закономерности, которые помогут упростить алгоритм обхода. Я выделил несколько интересных особенностей:

1. Каждый угловой элемент «улитки» (тот элемент, на котором происходит очередной поворот) можно легко рассчитать по формуле, зная размерность матрицы и номер шага:

C = l * s - M;
l - размерность
s - номер шага
M - смещение

Смещение — это сдвиг от «края» матрицы. Ведь на каждой итерации угловые элементы приближаются к центру. Соответственно, он меняется с каждым шагом. Изначально он равен 0. Для следующего шага (s+1) он рассчитывается так:

M = M + delta;

if(s % 2 != 0)
 delta = ceil(s / 2)

s - номер шага

2. Зная угловой элемент и направление движения на следующем шаге, можно легко заполнить недостающие элементы.

Что ж, думаю, что этих вещей вполне достаточно для реализации задачи. На мой взгляд, главной изюминкой решения является идея с угловыми элементами. Мы сокращаем вычисления, сводя заполнение «неугловых» ячеек простым инкрементированием.

Я думаю, что в самой статье приводить листинг кода не нужно, а любой заинтересовавшийся может легко скачать код из репозитория.

Использование класса Snail очень простое. Мы создаем новый объект и вызываем у него метод cookSnail(int $length), где $length — это размерность квадратной матрицы.

Текущая версия легко «готовит» и выводит «улитку» со стороной до 550 ячеек. А попробовать программу в действии можно тут:


Демо-пример

Демо-пример

За сим все! Безошибочного Вам кода!

Обход массива по улитке.: 1 комментарий

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *