Недавно был вопрос об инициализации массива спиральной матрицей. Хотя предложенные решения его решают, интересно решить эту задачу без использования памяти под массив, а именно:
Написать метод getNum(int s, int x, int y), который принимает три целых параметра — размер квадратной матрицы (s) и координаты позиции в этой матрице (x, y от 0 до s-1) и возвращает число от 1 до s*s, которое должно стоять в соответствующей ячейке «спиральной матрицы» (сматывающейся от левого-верхнего угла к центру по часовой стрелке).
Тогда задача вывода данной матрицы на экран должна свестись к такому коду (никакой массив не нужен):
for (int y = 0; y < s; y++) {
for (int x = 0; x < s; x++) {
System.out.printf("%4d", getNum(s, x, y));
}
System.out.println();
}
Кроме того можно вообще выводить огромные матрицы, в UI-окошке и скроллить мышкой, быстро отрисовывая только видимую часть.
Как же реализовать такой метод?
Решения на других языках тоже принимаются.
Ответ
Для начала переведём входные координаты x и y в систему координат относительно центра матрицы. Так как размер может быть чётным или нечётным, удвоим координаты, чтобы не возиться с половинками:
x = 2 * x - s + 1;
y = 2 * y - s + 1;
Скажем, для матрицы 5×5 возможные значения x и y будут -4, -2, 0, 2, 4. А для матрицы 6×6 — -5, -3, -1, 1, 3, 5.
Дальше определим, на каком квадрате от центра лежит текущая точка. Это просто максимум модуля обеих координат:
int n = Math.max(Math.abs(x), Math.abs(y));
Скажем, для квадрата 5×5 значения будут такие:
4 4 4 4 *4
4 2 2 *2 4
4 2 *0 2 4
4 2 2 2 4
4 4 4 4 4
Заметим, что внутри текущего квадрата (n-1)*(n-1) записей. Попробуем определить, какое число должно быть на правой-верхней диагонали. Надо из квадрата s*s вычесть квадрат n*n и посмотреть, что получается. Оказывается, надо ещё n вычесть. Вот значения s*s-n*n-n для квадрата 5×5:
5 5 5 5 *5
5 19 19 *19 5
5 19 *25 19 5
5 19 19 19 5
5 5 5 5 5
Ура, диагональ получили. С чётной стороной это тоже верно. Теперь посчитаем расстояние от этой диагонали с учётом знака:
int p = (y + x) / 2;
Прибавим это расстояние к нашему s*s - n*n - n, получим:
1 2 3 4 5
2 17 18 19 6
3 18 25 20 7
4 19 20 21 8
5 6 7 8 9
Отлично, теперь весь правый-верхний треугольник мы правильно выдаём. Чтобы починить левый-нижний, надо для него заменить p на 2*n-p. Точка лежит в левом-нижнем треугольнике, если x < y
if (x < y)
p = 2 * n - p;
Вот полный код:
public static int getNum(int s, int x, int y) {
x = 2 * x - s + 1;
y = 2 * y - s + 1;
int n = Math.max(Math.abs(x), Math.abs(y));
int p = (x + y) / 2;
if (x < y)
p = 2 * n - p;
return s * s - n * n - n + p;
}