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

Курсы

Программирование
iOS Developer. Basic
-23%
Python Developer. Professional
-13%
Разработчик на Spring Framework
-23%
Golang Developer. Professional
-17%
Python Developer. Basic
-16%
iOS Developer. Professional
-13%
Node.js Developer
-15%
Unity Game Developer. Professional
-11%
React.js Developer
-12%
Android Developer. Professional
-7%
Software Architect
-12%
C++ Developer. Professional
-8%
Разработчик C#
-8%
Backend-разработчик на PHP Архитектура и шаблоны проектирования
-12%
Программист С Базы данных Framework Laravel PostgreSQL Reverse-Engineering. Professional CI/CD Agile Project Manager Нереляционные базы данных Супер - интенсив по паттернам проектирования Супер-практикум по использованию и настройке GIT IoT-разработчик Advanced Fullstack JavaScript developer Супер-интенсив "Azure для разработчиков"
Инфраструктура
Мониторинг и логирование: Zabbix, Prometheus, ELK
-17%
DevOps практики и инструменты
-18%
Архитектор сетей
-21%
Инфраструктурная платформа на основе Kubernetes
-22%
Супер-интенсив «IaC Ansible»
-16%
Супер-интенсив по управлению миграциями (DBVC)
-16%
Administrator Linux.Basic
-10%
Супер-интенсив «ELK»
-10%
Administrator Linux. Professional MS SQL Server Developer Безопасность Linux PostgreSQL Reverse-Engineering. Professional CI/CD VOIP инженер Супер-практикум по работе с протоколом BGP Супер - интенсив по паттернам проектирования Супер - интенсив по Kubernetes Супер-интенсив «СУБД в высоконагруженных системах»
Специализации Курсы в разработке Подготовительные курсы
+7 499 938-92-02

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

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 комментариев
Для комментирования необходимо авторизоваться