Обход массива по улитке | OTUS
⚡ Подписка на курсы OTUS!
Интенсивная прокачка навыков для IT-специалистов!
Подробнее

Курсы

Программирование
Backend-разработчик на PHP
-9%
Алгоритмы и структуры данных
-9%
Team Lead
-6%
Архитектура и шаблоны проектирования Разработчик IoT
-13%
C# Developer. Professional
-9%
HTML/CSS
-11%
C# ASP.NET Core разработчик
-5%
Kotlin Backend Developer
-8%
iOS Developer. Professional
-8%
Java Developer. Professional JavaScript Developer. Professional Базы данных Android Developer. Professional Framework Laravel Cloud Solution Architecture Highload Architect Reverse-Engineering. Professional Vue.js разработчик Agile Project Manager VOIP инженер Scala-разработчик Супер-практикум по использованию и настройке GIT Symfony Framework Java Developer. Basic Unity Game Developer. Professional Супер-интенсив Azure
Инфраструктура
Экспресс-курс «IaC Ansible»
-10%
Administrator Linux.Basic
-10%
Мониторинг и логирование: Zabbix, Prometheus, ELK
-10%
Экспресс-курс «CI/CD или Непрерывная поставка с Docker и Kubernetes»
-30%
Administrator Linux. Professional
-6%
Дизайн сетей ЦОД
-13%
NoSQL Основы Windows Server MS SQL Server Developer Инфраструктурная платформа на основе Kubernetes Cloud Solution Architecture Highload Architect Разработчик голосовых ассистентов и чат-ботов VOIP инженер Супер-практикум по работе с протоколом BGP Супер - интенсив по паттернам проектирования Супер - интенсив по Kubernetes Супер-интенсив "Tarantool"
Специализации Курсы в разработке Подготовительные курсы
+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 комментариев
Для комментирования необходимо авторизоваться