Прежде чем перейти к статье, хочу вам представить, экономическую онлайн игру Brave Knights, в которой вы можете играть и зарабатывать. Регистируйтесь, играйте и зарабатывайте!
Размышления о способах непрерывного обхода двухмерных массивов, в которых траектория не пересекает саму себя, привели к выводу что их и не так-то много. На самом деле базовые алгоритмы можно, как говорится, пересчитать по пальцам одной руки. Наиболее известные из них: обход по спирали и обход «змейкой». В сети можно найти предостаточное количество решений, основная часть которых опирается на фундаментальные элементы программирования: условные переходы и циклы.
Однако, некоторое время назад меня посетила шальная мысль: а нельзя ли придумать математическую формулу, которая могла бы вычислить значение любого элемента подобных матриц на основании лишь его координат? Такая формула, конечно, не ускорила бы процесс полного обхода матрицы и соответственно установления каких-либо значений по пути следования (обычно по возрастающей). Но она позволила бы узнать значение любого элемента независимо от его положения за одну операцию, без необходимости прохождения через предыдущие ячейки со счётчиком. Конечно, практическая значимость такой формулы остается под большим вопросом, однако сама по себе идея была заманчива и пробуждала спортивный интерес.
В результате на Хабре появились две работы (для спиральной матрицы - https://habr.com/ru/articles/560266/, для матрицы «змейкой» - https://habr.com/ru/articles/672198/), в которых достаточно подробно описаны формулы нахождения значений элементов матриц и методика их построения.
Непродолжительное время назад мне вспомнился еще один алгоритм обхода - т.н. «угловой обход». Естественным образом возникло желание вывести уравнение и для этого способа, дабы обеспечить полноту коллекции формул для матриц широко известным числом 3. Следует отметить, что речь идет исключительно о квадратных матрицах, в которых количество столбцов равняется количеству строк.
Угловой обход и заполнение матрицы возрастающими значениями от 1 до N2 показан на рисунке 1:
Полагается, что нет необходимости описывать на естественном языке изучаемую траекторию и приведённой схемы достаточно для уяснения ее сути. Остается лишь добавить, что вариантов углового обхода можно насчитать целых 8 штук, в зависимости от того, с какого угла и в каком направлении (по горизонтали или вертикали) начинается движение. Однако предстоящая работа связана с «традиционным» вхождением в массив с левого верхнего угла, с первым шагом по горизонтали. Результаты достаточно легко адаптировать для любого из других 7 способов.
Таким образом задача: построить математическое уравнение для вычисления значений элементов матрицы, не используя условные переходы и заранее заготовленные наборы данных: массивы, словари, множества и т.д. Циклы применяются только для перебора всех элементов массива и также не присутствуют непосредственно в уравнении. Аргументами выступают координаты заданной ячейки (I, J) и размер матрицы (N).
Подготовка. Математический аппарат будет строиться параллельно с разработкой кода на языке С++. Для обеспечения программной реализации решений подготовим соответствующий скрипт, объявив в нем массив размером 5x5 (присвоим ему оригинальное наименование «А») и заполнив его нулевыми значениями. Уравнение будет строиться и проверяться поэтапно в процессе его одновременной работы со всеми элементами матрицы, перебор которых производится традиционным способом двумя вложенными циклами от 1 до N.
Основной скрипт выглядит следующим образом:
#include <iostream>
using namespace std;
int main()
{
int N = 5; // задаем размер матрицы
int a[N][N]; // и инициализируем ее
for (int ik = 0; ik < N; ik++)
for (int jk = 0; jk < N; jk++)
a[ik][jk] = 0; // заполнив для удобства нулями
for (int ik = 0; ik < N; ik++){ //назовем его "Основной цикл"
for (int jk = 0; jk < N; jk++){
int i = ik + 1; // Номера строк и столбцов приводим в удобный
int j = jk + 1; // в математическом плане вид (от 1 до N)
// ... здесь будем вставлять основной код вычислений
}
}
for (int ik = 0; ik < N; ik++){ //Блок "Вывод массива"
for (int jk = 0; jk < N; jk++){
printf( " %02d " , a[ik][jk]);// дополняем число ведущими нулями
}
cout << endl;
}
return 0;
}1 этап. Как и в предыдущих случаях, задачу необходимо разделить на несколько этапов. На первом этапе предстоит разбить массив на секции, в которых элементы логически связаны друг с другом и представляют собой цельный интервал. В данном случае это угловые участки - полупериметры каждого вложенного квадрата матрицы (для прояснения столь запутанного предложения смотрим на рисунок 2).
Обозначив и пронумеровав каждую секцию на схеме, можно убедиться, что их количество равняется размеру матрицы.
Теперь же требуется вычислить номер секции по имеющимся аргументам, то есть координатам ячейки.
Как это сделать?
Для начала рассмотрим взаимосвязь координат ячеек с номерами секций на рисунке 3.
Отсюда видно, что номер секции, в которой находится элемент равняется наибольшему значению из двух чисел, обозначающих его координаты D = max (i, j). Но как определить наибольшее из двух чисел, не используя условный переход? К счастью, для этого имеется распространённый способ, заключающийся в делении суммы результата сложения и абсолютной разницы на 2. То есть по формуле max = ((a + b) + |a - b|) / 2. При этом, результат будет целочисленным, так как ((a + b) + |a - b|) всегда дает четное число.
В нашем случае, после ввода соответствующей переменной, это будет:
Не откладывая в долгий ящик, сразу пробуем это в компиляторе (результат на рисунке 4):
int D = (i + j + abs(i - j))/2;
a[ik][jk] = D;
Убедившись, что все прекрасно работает, переходим к следующему этапу.
2 этап. Теперь необходимо определить диапазон значений в каждой секции и расположить эти самые значения в возрастающем порядке хотя бы в одном направлении.
Учитывая, что работа осуществляется с абсолютно квадратной матрицей (неабсолютно квадратные матрицы – это прямоугольные матрицы, у которых количество строк не равняется количеству столбцов
Интересные статьи
Интересные статьи
