Эта задача довольно часто встречается в сети, и решений для нее написано много, однако среди них есть и похуже, и получше. Мы разберём разные варианты, а также моё решение (нет, оно не лучшее).
И мы не сразу начнём с решения, потому что даже такая простая вещь, как работа с матрицей, требует обширной подготовки.
Задача
Нужно вывести на печать матрицу размером N*N, заполненную числами натурального ряда, начиная с первого элемента и двигаясь по спирали:
Комментарий
Вывод на печать происходит в командной консоли построчно, то есть нельзя печатать числа в произвольных позициях на экране.
Требуется только вывести числа на печать, то есть иметь в программе структуру данных и заполнять её числами не обязательно. А возможно, и не приветствуется. Потому что матрица может иметь размер миллиард на миллиард, и выделить под неё память будет проблематично.
Но все решения, в том числе и моё, сначала заполняют матрицу, а потом печатают. Это неудивительно, так как внятный алгоритм для получения чисел матрицы "на лету" трудно вообразить. Придётся пока с этим смириться.
Подготовка
Заведём N как константу прямо в программе. Откуда она берётся, нам не интересно, мы можем просто исправлять её как потребуется:
N = 5
Надо создать в памяти матрицу N*N. После этого останется заполнить её тем или иным способом.
Нас интересуют коллекции. В Питоне есть: список, множество, ассоциативный массив. Нам подойдёт список, потому что это упорядоченная последовательность элементов. Он инициализируется так:
a = []
Это создаёт пустой список, но нам нужен не пустой. Тогда можно написать так:
a = [0, 0, 0, 0, 0]
Мы получили список из 5 элементов, равных 0. Это нас тоже не устраивает. Во-первых, нам нужен список из N элементов, а N может быть любым. Значит, мы не можем заранее написать нужное количество элементов в списке. Во-вторых, нам нужен не одномерный, а двумерный список размером N*N.
Двумерных списков в Питоне нет. Но можно сделать список, состоящий из списков. Вот так:
a = [[0,0,0,0,0], [0,0,0,0,0], [0,0,0,0,0], [0,0,0,0,0], [0,0,0,0,0]]
А чтобы было нагляднее, можно вставить переносы строк:
a = [
[0, 0, 0, 0, 0],
[0, 0, 0, 0, 0],
[0, 0, 0, 0, 0],
[0, 0, 0, 0, 0],
[0, 0, 0, 0, 0]
]
Теперь можно разглядеть матрицу из 5 строк, где каждая строка имеет 5 элементов (столбцов). Осталось сделать так, чтобы эта структура формировалось автоматически по заданному N.
Мы можем создать список из N элементов следующим образом:
a = [0] * N
В данном конкретном случае это не умножение, а повторение содержимого списка. Из одного элемента получилось N элементов:
Осталось сделать повторение повторений:
a = [[0] * N] * N
И вроде бы дело в шляпе, но не совсем. Повторяя элемент, который является числом 0, мы создаём в памяти новое число 0. Но повторяя элемент, который сам является списком, мы создаём не новый список, а только лишь новый указатель на него. То есть вместо пяти списков мы получаем один список и пять одинаковых указателей:
Список внутри списка хранится как указатель, поэтому его нужно не повторять, а именно создавать заново N раз. Для этого потребуется цикл:
a = [None] * N
for i in range(N): a[i] = [None] * N
В первой строке мы создали список из N элементов типа None. Это специальный тип Питона, который означает "ничто". Мы могли бы создать N нулей или N любых других типов, неважно. Это просто места для будущих элементов, они будут перезаписаны, но по логике они сейчас пустые, и поэтому мы отразили это с помощью None.
Далее в цикле мы заполним каждый элемент новым указателем на список из N элементов. Конструкция
for i in range(N):
переводится так: для (for) переменной i, которая меняется в диапазоне (in range) от 0 до N-1 включительно, повторить то, что написано после ":"
а повторяться будет вот это: a[i] = [None] * N
Ранее мы уже подготовили список a из N элементов. Доступ к элементам списка осуществляется так:
a[0] – элемент со смещением 0 от начала списка (то есть самый первый)
a[1] – элемент со смещением 1 от начала списка (то есть второй)
И т.д. Подставляя в качестве смещения переменную i, мы получаем:
a[i] – элемент со смещением i от начала списка
Подытожим: переменная i в цикле меняется от 0 до N-1. В этом же цикле мы обращаемся к элементу списка a со смещением i, т.е. a[i], и помещаем туда указатель на новый список из N элементов. Указатель получается из выражения [None] * N, которое создаёт новый список. Таким образом мы создаём N списков по N элементов, или матрицу N*N.
Почему написано in range(N), а i достигает только N-1? Потому что когда мы пишем in range(N), то фактически мы хотим повторить цикл N раз. Но так как отсчёт идёт от 0, то i должна достигнуть только N-1, иначе получится на 1 раз больше. Так же и элементы списка имеют смещения от 0 до N-1. Так что всё совпадает.
Узнать больше: Почему программисты считают с нуля
Ладно, наша матрица N*N наконец готова. Если доступ к элементу списка выглядит как a[x], то как будет выглядеть доступ к элементу двумерного списка, или списка списков?
Обратившись к списку списков через a[x], мы получим его элемент, который тоже список. Значит к нему тоже можно обратиться через [x]. Попробуем так:
x = 3; y = 2
line = a[y]
elem = line[x]
Что мы сделали:
- завели переменные x и y, то есть координаты элемента в матрице
- нашли в нашем списке списков элемент со смещением y – это строка матрицы. И присвоили его переменной line.
- так как line – это тоже список, внутри него мы ищем элемент со смещением x, то есть столбец внутри строки.
Так как выражение a[y] это тоже список, то [x] можно приписать прямо к нему, не создавая промежуточную переменную:
elem = a[y][x]
Обратите внимание, что координаты x,y мы используем в обратном порядке, то есть y,x. Это потому, что координата у соответствует строкам, а мы сначала должны найти строку, а потом столбец. Мы могли бы, ничего не меняя, писать x,y, но тогда наша матрица оказалась бы геометрически повёрнутой на 90 градусов. Что также не играет в данной задаче никакой роли. Но мы будем придерживаться правильных представлений, исходя из структуры данных в памяти.
Читайте также: Адресация в матрицах
Подытожим в очередной раз:
- Мы можем создавать матрицы размером N*N как списки списков
- Мы можем обращаться к элементу матрицы с координатами x,y, используя запись a[y][x]
- Мы знаем, как работает цикл for i in range(N)
Подготовка закончена.
Следующая часть: Первая реализация