Есть задача - заполнить таблицу размером $%n \times n$% рядом натуральных чисел от 1 до $%n^2 $%, начиная с левого верхнего угла, по спирали по часовой стрелке. Можно ли тут проследить какие-либо закономерности, а не использовать большое количество циклов?

задан 27 Сен '14 9:50

изменен 28 Сен '14 21:34

А по какому принципу заполняется таблица? Если по строкам, то закономерность там простая. Но в условии говорится про спираль; тогда надо уточнить способ заполнения. Например, по часовой стрелке. По идее, закономерность там должна быть, то есть можно явную формулу указать, чему равно a[i,j]. В таком виде задача достаточно интересная получается.

(27 Сен '14 13:40) falcao
10|600 символов нужно символов осталось
2

Будем считать, что таблица заполняется по спирали по часовой стрелке. Нумерация строк и столбцов такая же, как в матрицах (начинается с 1).

Пусть нужно вычислить значение $%a_{ij}$%. Обозначим через $%k$% минимум из чисел $%i,j,n+1-i, n+1-j$%. Тогда $$a_{ij}=4(k-1)(n-k+1)+\begin{cases}j-k+1, \text{если } i=k,\\ n-3k+i+2, \text{если } j=n-k+1,\\ 3n-5k-j+4, \text{если } i=n-k+1,\\ 4n-7k-i+5, \text{если } j=k,i\neq k.\end{cases}$$

Такой ответ легко угадывается по индукции: $%k$% - это номер витка спирали, который мы заполняем, на предыдущих витках мы поставили как раз $%4(k-1)(n-k+1)$% чисел. А дальше нужно просто получить формулу для первого витка.

В зависимости от целей ответ можно модифицировать, разбив квадрат на 4 сектора и заполняя каждый сектор отдельно. Например, пусть $%i\leqslant n/2$% и $%j\leqslant n/2$%, тогда $$a_{ij}=\begin{cases} 4(i-1)(n-i+1)+j-i+1, \text{если } i\leqslant j,\\ 4(j-1)(n-j+1)+4n-7j-i+5, \text{если } j< i. \end{cases}$$

ссылка

отвечен 27 Сен '14 17:26

изменен 27 Сен '14 18:57

@cartesius: я написал программу в Maple для проверки указанных Вами формул. Получается что-то близкое к тому, что нужно, но не до конца. При $%n=3$% всё сошлось, но при $%n=4$% два последних числа не подошли. Там должно быть $%a[3,3]=16$% и $%a[3,2]=19$%, а должно быть 15 и 16 соответственно. Видимо, надо слегка откорректировать вид формул.

(27 Сен '14 17:49) falcao

Да, верно, я поторопилась, делая замены переменных. Сейчас поправлю.

(27 Сен '14 18:00) cartesius

@cartesius: при $%n=4$% теперь всё верно, а при $%n=5$% в центре квадрата получилось 29 вместо 25.

(27 Сен '14 18:24) falcao

Еще раз поправила: уже в суммировании - та же ошибка была. Вроде больше ошибаться негде.

(27 Сен '14 18:59) cartesius

@cartesius: да, вот эти формулы уже должны быть верны!

(27 Сен '14 20:52) falcao
10|600 символов нужно символов осталось
1

Немного переделал формулы, чтоб подходили для индексации с нуля.

$%k$% - это меньшее из $%i,$% $%j,$% $%n-i-1$% и $%n-j-1$%

$$ a_{i, j} = 4\big(kn- k^{2} \big)+ \begin{cases}j-k+1 & если & i=k\\n-3k+i & если & j=n-k-1\\3n-5k-j-2 & если & i=n-k-1\\4n-7k-i-3 & если & j=k,i\neq k \end{cases} $$

Нужно было для функции в программе:

def mtrx_snake(i, j, n):
    """
    Возвращает значение, расположенное в матрице размером n x n
    в строке i и в столбце j. Матрица заполнена порядковыми числами
    спиралью по часовой стрелке
    """
    k = min(i, j, n-i-1, n-j-1)
    if i == k:
        return 4 * (k * n - k**2) + j - k + 1
    elif j == n - k - 1:
        return 4 * (k * n - k**2) + n - 3 * k + i
    elif i == n - k - 1:
        return 4 * (k * n - k**2) + 3 * n - 5 * k - j - 2
    else:
        return 4 * (k * n - k**2) + 4 * n - 7 * k - i - 3

n = int(input())
mtrx = [[0 for j in range(n)] for i in range(n)]

print()
for i in range(n):
    for j in range(n):
        mtrx[i][j] = mtrx_snake(i, j, n)
        print(mtrx[i][j], end = '\t')
    print()
ссылка

отвечен 8 Июн '16 16:02

изменен 8 Июн '16 17:32

while True:

    while j < max_j:
        j += 1
        mtrx[i][j] = count
        count += 1
    max_j -= 1
    while i < max_i:
        i += 1
        mtrx[i][j] = count
        count += 1
    max_i -= 1
    while j > min_j:
        j -= 1
        mtrx[i][j] = count
        count += 1
    min_j += 1
    while i > min_i:
        i -= 1
        mtrx[i][j] = count
        count += 1
    min_i += 1

    if j == (n - 1) // 2 and i == n // 2:
        break
(8 Июн '16 23:25) Abigail Sparow

Таким было первое решение. 4 переключателя max_i, max_j, min_i, min_j. И при помощи циклов бежим до первого(правого верхнего) угла, попутно заполняя. Меняем значение переключателя и бежим вниз. И так пока не уткнемся в последнее значение :)

(8 Июн '16 23:32) Abigail Sparow

Видел еще решение с другими переключателями на форуме:

dx, dy = 1, 0
x, y = 0, 0
arr = [[None] * n for _ in range(n)]
for i in range(1, n**2+1):
    arr[x][y] = i
    nx, ny = x+dx, y+dy
    if 0 <= nx < n and 0 <= ny < n and not arr[nx][ny]:
        x, y = nx, ny
    else:
        dx, dy = -dy, dx
        x, y = x+dx, y+dy

Решение не мое, но думаю все понятно. Принцип похож. Единственное, что тут она заполняется в другую сторону.

(8 Июн '16 23:34) Abigail Sparow

Для второго варианта, по-моему, можно сделать проще условие завершения: count == 1+(n*n). Ваше условие, честно говоря, я даже как-то не понимаю… :)

(9 Июн '16 0:03) abracadabra

@abracadabra, точно. Последний же счетчик на 1 больше квадрата n. Мое условие это координата последнего значения - если n нечетная, то последнее значение ровно посередине n//2 - поскольку индексация с нуля, то не нужно 1 прибавлять. А если четное, то посередине находится виток из 4 значений: ++++ +00+ +х0+ ++++ в котором последнее находится внизу слева, значит координата строки n//2, а столбца (n-1)//2, это условие подходит и для нечетного значения, поэтому не нужно было ветвление делать. Мне в школе на математике вечно оценку снижали за нерациональность. Мышление у меня такое - нестандартное.

(9 Июн '16 15:56) Abigail Sparow

@Abigail Sparow Дошло. Почему-то сначала поверил разметке больше, чем коду, а проверять, как работает этот код, всё-таки не стал. :) Решил, что после двух косых черт — комментарий какой-то непонятный… Без всякой связи (почти!) вспоминается: «А вы / ноктюрн сыграть / могли бы // На флейте водосточных труб?» :D

(9 Июн '16 21:16) abracadabra
показано 5 из 6 показать еще 1
10|600 символов нужно символов осталось
0

Занятно. В принципе, я могу видеть три подхода. Первый — найти функцию, которая преобразует последовательность возрастающих целых чисел в последовательность индексных пар. Тогда можно значения последовательности использовать в качестве переменной цикла, чтобы в этом цикле по очереди заполнять значения. Второй — найти функцию, которая обратна функции из первого пункта. Тогда можно обходить массив как угодно, помечая каждую клетку верным значением. Или какой-нибудь функцией верного значения, если надо. Этот способ был предложен выше. Третий — найти функцию, которая каждой клетке массива сопоставляет следующую клетку. По-моему, это проще всего.

Сначала находим расстояние текущей клетки до каждой из границ массива. Пусть множество всех клеток, наименьшее расстояние от каждой из которых до какой-нибудь стороны массива равно какому-то числу, называется оквадратностью. Мы находимся: 1) на какой-нибудь оквадратности; 2) либо на какой-то стороне этой оквадратности, либо в её углу. Пометив клетку, мы дальше двигаемся, используя создаваемую функцию.

А дальше построение функции очевидно. (В этом-то и прелесть.) Из левого верхнего угла мы никуда не движемся. Из клетки на левой стороне на расстоянии от верхнего угла в единицу мы движемся вправо, если мы не находимся при этом в левом нижнем углу; если находимся, то никуда не движемся. Это особые случаи. В остальных случаях направление можно тоже однозначно указать по стороне или углу оквадратности, где мы находимся.

Программный код не проще, чем во втором случае (даже сложнее, потому что нужно различить девять случаев), но понять его, по-моему, становится проще.

PS: не заметил, что вопрос старый.

ссылка

отвечен 8 Июн '16 20:57

@abracadabra: первый абзац я понял, а дальше наступили трудности. Непонятно, о каком массиве идёт речь (о двумерном?), что такое "оквадратность", а также почему там возникает несколько случаев.

(8 Июн '16 22:41) falcao

@falcao Двумерный массив, конечно же. Оквадратность — по аналогии с окружностью. Спираль проходит по «оквадратности», пока не переходит к следующей «оквадратности» из клетки под левым верхним углом предыдущей «оквадратности». Честное слово, не знаю, как назвать. Наверное, «виток спирали». Соответственно, случаи связаны с тем, в каком месте спирали (в каком месте «оквадратности») мы находимся: 4 стороны, 4 угла, а также особенное место под левым верхним углом, где мы переходим к следующему витку спирали, коли следующий виток имеется.

(8 Июн '16 22:49) abracadabra

@abracadabra: если под "оквадратностями" понимаются, по сути дела, концентрические контуры квадратов, состоящие из клеток (на что я в первую очередь и подумал), то меня сбило с толку замечание о том, что мы либо находимся на некоторой "оквадратности", либо что-то ещё. Но ведь любая клетка входит в одно из таких множеств, поэтому всегда имеет месть случай 1).

Если бы я сам это дело излагал, то за неимением удобного названия ввёл бы обозначения $%M_i$% как подмножества клеток квадрата на расстоянии $%i$% от граничного слоя клеток (или типа этого). Хотя я сам не люблю формул, предпочитая слова.

(8 Июн '16 23:35) falcao

@falcao «Первое» и «второе» имеют место одновременно. Это не перечисление альтернатив, это два условия, которые всегда выполняются. Просто второе условие состоит из альтернатив. А девять случаев — это черта реализации; по-моему, @Abigail Sparow реализовал лучше. Сейчас попробую обрамить его код (приравнять начальные значения индексов $%i$% и $%j$% нулям, вставить код в функцию, вызвать её) и запустить для проверки. :)

(8 Июн '16 23:42) abracadabra

@abracadabra: сейчас я вчитался, и смысл до меня дошёл. Но так писать не следовало, по моему. Если Вы хотели подчеркнуть, что мы всегда находимся на некоторой ОК, то лучше было без пунктов написать, что, находясь на ОК, мы находимся или на её стороне, или в углу. И тогда, если вводить пункты, то 1) для стороны, и 2) для угла. То, что Вы сделали, в самом деле сбивает с толку -- с учётом неуверенности в правильности понимания того, что было определено как ОК.

(8 Июн '16 23:54) falcao
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×91
×83

задан
27 Сен '14 9:50

показан
3779 раз

обновлен
9 Июн '16 21:20

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru