Lesson 9
Двумерные списки (массивы)
1. Вложенные списки: обработка и печать
В реальном мире часто задачам приходится хранить прямоугольную таблицу данных. [скажем больше об этом!] Такие таблицы называются матрицами или двумерными массивами. В Python любая таблица может быть представлена как список списков (список, где каждый элемент, в свою очередь, является списком). Например, вот программа, которая создает числовую таблицу с двумя строками и тремя столбцами, а затем выполняет некоторые манипуляции с ней:a = [[1, 2, 3], [4, 5, 6]] print(a[0]) print(a[1]) b = a[0] print(b) print(a[0][2]) a[0][1] = 7 print(a) print(b) b[2] = 9 print(a[0]) print(b)
Первый элемент a здесь - a[0] - это список чисел [1, 2, 3] . Первый элемент этого нового списка - a[0][0] == 1 ; кроме того, a[0][1] == 2 , a[0][2] == 3 , a[1][0] == 4 , a[1][1] == 5 , a[1][2] == 6 .
Для обработки двумерного массива обычно используются вложенные циклы. Первый цикл повторяется через номер строки, второй цикл проходит через элементы внутри строки. Например, так вы показываете двумерный численный список на экране по строкам, разделяя числа пробелами:
a = [[1, 2, 3, 4], [5, 6], [7, 8, 9]]
for i in range(len(a)):
for j in range(len(a[i])):
print(a[i][j], end=' ')
print()
Мы уже пытались объяснить, что переменная for-loop в Python может выполнять итерацию не только по range() , но обычно по всем элементам любой последовательности. Последовательности в Python - это списки и строки (и некоторые другие объекты, которые мы еще не встретили). Посмотрите, как вы можете печатать двумерный массив, используя эту удобную функцию цикла for :
a = [[1, 2, 3, 4], [5, 6], [7, 8, 9]]
for row in a:
for elem in row:
print(elem, end=' ')
print()
Естественно, для вывода одной строки вы можете использовать метод join() :
for row in a:
print(' '.join([str(elem) for elem in row]))
Так вы можете использовать 2 вложенных цикла для вычисления суммы всех чисел в двумерном списке:
a = [[1, 2, 3, 4], [5, 6], [7, 8, 9]]
s = 0
for i in range(len(a)):
for j in range(len(a[i])):
s += a[i][j]
print(s)
Или то же самое с итерацией элементами, а не переменными i и j :
a = [[1, 2, 3, 4], [5, 6], [7, 8, 9]]
s = 0
for row in a:
for elem in row:
s += elem
print(s)
2. Вложенные списки: создание
Предположим, что указаны два числа: число строк n и количество столбцов m . Вы должны создать список размером n × m , заполненный, скажем, нулями.
Очевидное решение кажется неправильным:
a = [[0] * m] * n
Это можно легко увидеть, если вы установите значение a[0][0] на 5 , а затем распечатаете значение a[1][0] - оно также будет равно 5. Причина в том, что [0] * m возвращает только ссылку на список из m нулей, но не список. Последующее повторение этого элемента создает список из n элементов, все ссылки на один и тот же список (как и операция b = a для списков не создает новый список), поэтому все строки в результирующем списке на самом деле одинаковы строка.
Используя наш визуализатор, отслеживайте идентификатор списков. Если два списка имеют одинаковый номер id, это фактически тот же список в памяти.
n = 3 m = 4 a = [[0] * m] * n a[0][0] = 5 print(a[1][0])
Таким образом, двумерный список не может быть создан просто путем повторения строки. Что делать?..
Возможный способ: вы можете создать список из n элементов (например, из n нулей), а затем сделать каждый из элементов ссылкой на другой одномерный список из m элементов:
n = 3
m = 4
a = [0] * n
for i in range(n):
a[i] = [0] * m
Другой (но похожий) способ: создать пустой список, а затем append к нему новый элемент n раз (этот элемент должен быть списком длины m ):
n = 3
m = 4
a = []
for i in range(n):
a.append([0] * m)
Но самый простой способ - использовать генератор, создавая список из n элементов, каждый из которых представляет собой список из m нулей:
n = 3 m = 4 a = [[0] * m for i in range(n)]
В этом случае каждый элемент создается независимо от других. Список [0] * m n раз помечается как новый, и копирование ссылок не происходит.
3. Как вы вводите двумерный массив?
Скажем, программа принимает входной двумерный массив в виде n строк, каждый из которых содержит m чисел, разделенных пробелами. Как заставить программу читать ее? Пример того, как вы можете это сделать:
# первая строка ввода - это количество строк массива
n = int(input())
a = []
for i in range(n):
a.append([int(j) for j in input().split()])
Или, не используя сложные вложенные вызовы:
# первая строка ввода - это количество строк массива
n = int(input())
a = []
for i in range(n):
row = input().split()
for i in range(len(row)):
row[i] = int(row[i])
a.append(row)
Вы можете сделать то же самое с генераторами:
# первая строка ввода - это количество строк массива n = int(input()) a = [[int(j) for j in input().split()] for i in range(n)]
4. Обработка двумерного массива: пример
Предположим, вам задан квадратный массив (массив из n строк и n столбцов). Предположим, вы должны установить элементы главной диагонали, равные 1 (т. Е. Те элементы a[i][j] для которых i==j ), чтобы установить элементы выше, чем диагональ, равная 0, и установить элементы ниже этой диагонали, равной 2. То есть вам нужно создать такой массив (пример для n==4 ):
1 0 0 0 2 1 0 0 2 2 1 0 2 2 2 1(В этом случае вы можете сделать это вручную, установив
a[0][0] = 1 , a[0][1] = 0 и т. Д., Но вы не будете делать это вручную для массивов из 100 строк и 100 столбцов , что часто бывает.) Мы стремимся показать вам несколько способов решения этой проблемы. Во-первых, обратите внимание, что элементы, лежащие над главной диагональю, - это элементы a[i][j] для которых i<j , а для элементов ниже главной диагонали i>j . Таким образом, мы можем сравнить значения i и j , определяющие значение a[i][j] . Мы получаем следующий алгоритм:
n = 4
a = [[0] * n for i in range(n)]
for i in range(n):
for j in range(n):
if i < j:
a[i][j] = 0
elif i > j:
a[i][j] = 2
else:
a[i][j] = 1
for row in a:
print(' '.join([str(elem) for elem in row]))
Этот алгоритм медленный: он использует два цикла и для каждой пары (i,j) выполняет одну или две команды if . Если мы усложним алгоритм, мы сможем сделать это без условного оператора.
Сначала заполните основную диагональ, для которой нам понадобится один цикл:
for i in range(n):
a[i][i] = 1
Затем заполните нулями все элементы над главной диагональю. Чтобы сделать это, для каждой строки с номером i вам нужно присвоить значение a[i][j] для j = i+1 , ..., n-1 . Для этого вам нужны вложенные циклы:
for i in range(n):
for j in range(i + 1, n):
a[i][j] = 0
По аналогии, для j = 0 , ..., i-1 задайте элементы a[i][j] равными 2 :
for i in range(n):
for j in range(0, i):
a[i][j] = 2
Вы можете комбинировать весь этот код и получить другое решение:
n = 4
a = [[0] * n for i in range(n)]
for i in range(n):
for j in range(0, i):
a[i][j] = 2
a[i][i] = 1
for j in range(i + 1, n):
a[i][j] = 0
for row in a:
print(' '.join([str(elem) for elem in row]))
Вот еще одно решение, которое повторяет списки для создания следующих строк списка. i строка списка состоит из i чисел 2 , за которым следует одно целое число 1 , за которым следуют ni-1 нули:
n = 4
a = [0] * n
for i in range(n):
a[i] = [2] * i + [1] + [0] * (n - i - 1)
for row in a:
print(' '.join([str(elem) for elem in row]))
Как обычно, вы можете заменить петлю генератором:
n = 4
a = [0] * n
a = [[2] * i + [1] + [0] * (n - i - 1) for i in range(n)]
for row in a:
print(' '.join([str(elem) for elem in row]))
5. Двумерные массивы: вложенные генераторы
Вы можете использовать вложенные генераторы для создания двумерных массивов, поместив генератор списка, который является строкой, внутри генератора всех строк. Напомним, что вы можете создать список из n строк и m столбцов с помощью генератора (который создает список из n элементов, где каждый элемент представляет собой список из m нулей):
[[0] * m for i in range(n)]
Но внутренний список также может быть создан с использованием, например, такого генератора: [0 for j in range(m)] . Вложив один генератор в другой, получим
[[0 for j in range(m)] for i in range(n)]
Как это связано с нашей проблемой? Дело в том, что если число 0 заменяется некоторым выражением, которое зависит от i (номер строки) и j (номер столбца), вы получаете заполненную матрицу согласно некоторой формуле.
Например, предположим, что вам нужно инициализировать следующий массив (для удобства добавляются дополнительные пробелы между элементами):
0 0 0 0 0 0 0 1 2 3 4 5 0 2 4 6 8 10 0 3 6 9 12 15 0 4 8 12 16 20
В этом массиве есть n = 5 строк, m = 6 столбцов, а элемент с индексом строки i и индексом столбца j вычисляется по формуле a[i][j] = i * j .
Как всегда, вы можете использовать генератор для создания такого массива:
[[i * j for j in range(m)] for i in range(n)]