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

Курсы

Курсы в разработке Подготовительные курсы
Работа в компаниях Компаниям Блог +7 499 110-61-65

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

PHP_Deep_6.8_site-5020-c1ff65.png

Однажды мне на глаза попалась задачка, которую кому-то из хабравчан предложили для решения на собеседовании. Суть её состояла в том, чтобы заполнить квадратную матрицу с размерностью 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-20219-1d186e.png

Не пропустите новые полезные статьи!

Спасибо за подписку!

Мы отправили вам письмо для подтверждения вашего email.
С уважением, OTUS!

Автор
0 комментариев
Для комментирования необходимо авторизоваться