Заполнить квадратную матрицу введенного размера цепочкой последовательных натуральных чисел по часовой стрелке от центра к границам. Матрицу показать пользователю.

Здравствуйте, Аноним, Вы писали:

ИМХО, легче заполнять с конца.
Заполнять курсором. Как только он наталкивается на край или уже заполненные поля — поворачивать.
Поворот означает умножение двухмерного шага на матрицу поворота.
От центра критерий поворота муторнее.

Здравствуйте, Аноним, Вы писали:

А>Заполнить квадратную матрицу цепочкой последовательных натуральных чисел по часовой стрелке от центра к границам.

Заполнил.

A> Матрицу показать пользователю.

923
814
765

Показал.

Здравствуйте, <Аноним>, Вы писали:

А>Заполнить квадратную матрицу введенного размера цепочкой последовательных натуральных чисел по часовой стрелке от центра к границам. Матрицу показать пользователю.
Размерность к или 2к+1?
Если 2к+1, куда первый от центра шаг?
Если к, ещё и с какой начинать?

Здравствуйте, sugarde, Вы писали:

S>Здравствуйте, Аноним, Вы писали:

S>ИМХО, легче заполнять с конца.
S>Заполнять курсором. Как только он наталкивается на край или уже заполненные поля — поворачивать.
S>Поворот означает умножение двухмерного шага на матрицу поворота.
S>От центра критерий поворота муторнее.
Как определить конец?
Так чтобы уж совсем полное...

Здравствуйте, VEAPUK, Вы писали:

VEA>Так чтобы уж совсем полное...
Пусть центр при четных размерах левый нижний кандидат.
Если мы делаем первый шаг вправо, то конец — левый верхний.

При нечетных если первый шаг опять вправо, то конец — правый нижний.
Как-то так.
Определившись с тем, куда начинаем, сразу установим где конец.

Здравствуйте, sugarde, Вы писали:

Упс. Я против часовой пошел. Но мысль ясна.

Здравствуйте, Аноним, Вы писали:

А>Заполнить квадратную матрицу введенного размера цепочкой последовательных натуральных чисел по часовой стрелке от центра к границам. Матрицу показать пользователю.

Ходить курсором не круто. Круто написать функцию, которая по координатам определяет значение

Скажем начинаем с центральной клетки (0, 0), и присваиваем ей номер 0, например, и идём сначала влево в (1, 0), потом в (1, 1), в (0, 1) ну и так далее.

Задача по координатам клетки определить её номер
Скажем номер клетки (3, — 2) будет 25

Интересна, так же, и оратная задача (по номеру клетки определить её координаты)

Здравствуйте, Erop, Вы писали:

E>Ходить курсором не круто. Круто написать функцию, которая по координатам определяет значение
O(1)-функцию?

Здравствуйте, Erop, Вы писали:

E>Ходить курсором не круто. Круто написать функцию, которая по координатам определяет значение
Угу. Точно. Там такая себе вычисляемая в O(1) квадратичная функция от координат.

E>Интересна, так же, и оратная задача (по номеру клетки определить её координаты)
Курсор делает повороты после 1-1-2-2-3-3-4-4 и т.д. клеток.
Известно число поворотов и последняя сторона квадрата. И так далее.

Ясно.

Здравствуйте, <Аноним>, Вы писали:

А>Заполнить квадратную матрицу введенного размера цепочкой последовательных натуральных чисел по часовой стрелке от центра к границам. Матрицу показать пользователю.

Я даже догадываюсь, кто это пользователь. Препод. Угадал?

1. Моделируем процесс на бумажке

. j . . .    . q . . . .
. i b c .    . p e f g .
. h А d .    . o d А h .
. g f e .    . n c b i .
. . . . .    . m l k j .
             . . . . . .

2. Становится очевидно, что значение элемента m(x,y) = (s-2)^2 + (s-1)*k + p, где
s — длина стороны квадрата, на которой расположена точка (x,y)
k — номер стороны (0..3): верхняя, правая, нижняя, левая
p — смещение на стороне

3. Будем искать формулы, чтоб найти (s,k,p) из (x,y).
Для удобства положим, что все числа у нас начинаются с 0. А система координат — слева направо и сверху вниз.

Сперва s(x)
Опять же, бумажка творит чудеса для понимания:

      0 1 2 3 4          0 1 2 3 4 5
      5 3 1 3 5          6 4 2 2 4 6
    +----------        +------------
0 5 | 5 5 5 5 5    0 6 | 6 6 6 6 6 6
1 3 | 5 3 3 3 5    1 4 | 6 4 4 4 4 6
2 1 | 5 3 1 3 5    2 2 | 6 4 2 2 4 6
3 3 | 5 3 3 3 5    3 2 | 6 4 2 2 4 6
4 5 | 5 5 5 5 5    4 4 | 6 4 4 4 4 6
                   5 6 | 6 6 6 6 6 6

s(x,y) = max(s(x),s(y))
s(x) = max(n-2x, 2x+2-n)

Будет удобно, если мы введём зеркальные координаты: x' = n-1-x, y' = n-1-y
s(x) = max(n-2x, n-2x')

Теперь номер стороны.

k              d = x-y       d' = x'-y
+----------    +----------   +----------
| 3 0 0 0 0    | 0 + + + +   | + + + + 0
| 3       1    | - 0 + + +   | + + + 0 -
| 3       1    | - - 0 + +   | + + 0 - -
| 3       1    | - - - 0 +   | + 0 - - -
| 2 2 2 2 1    | - - - - 0   | 0 - - - -

Итак, видно, что:
(d>0 && d'>=0) ==> k=0
(d>=0 && d'<0) ==> k=1
(d<0 && d'<=0) ==> k=2
(d<=0 && d'>0) ==> k=3

Осталось найти смещение на стороне. Из предыдущего рисунка видно, что
k=0 ==> p=d-1
k=1 ==> p=-d'-1
k=2 ==> p=-d-1
k=3 ==> p=d'-1

Ну и следует корректно обработать сингулярность в центре (для нечётных n). Очевидно, что там будет ответ 0.

---

Гипотеза нуждается в проверке. Простенький скрипт на питоне:

def index(n,x,y) :
    x1, y1 = n-1-x, n-1-y
    sx, sy = max(n-2*x,n-2*x1), max(n-2*y,n-2*y1)
    s = max(sx,sy)
    s2 = max(s-2,0)
    d, d1 = x-y, x1-y
    if d>0 and d1>=0 : k, p = 0, d-1
    if d>=0 and d1<0 : k, p = 1, -d1-1
    if d<0 and d1<=0 : k, p = 2, -d-1
    if d<=0 and d1>0 : k, p = 3, d1-1
    if d==0 and d1==0: k, p = 0, 0
    i = s2*s2 + (s-1)*k + p
    return (s,k,p,i)

def letter(i) :
    return chr(ord('A')+i)

def show(n) :
    for y in range(n) :
        for x in range(n) :
            s,k,p,i = index(n,x,y)
            #print s,  # использовал для отладки
            print letter(what),
        print

for n in range(1,7) :
    show(n)
    print