Вычисление произведения матриц

Умножение матриц — одна из основных операций над матрицами. Матрица, получаемая в результате операции умножения, называется произведением матриц.

Операция умножения двух матриц выполнима только в том случае, если число столбцов в первом сомножителе равно числу строк во втором; в этом случае говорят, что форма матриц согласована. В частности, умножение всегда выполнимо, если оба сомножителя — квадратные матрицы одного и того же порядка.

Следует заметить, что из существования произведения A*B вовсе не следует существование произведения B*A.

Произведение матриц A*B состоит из всех возможных комбинаций скалярных произведений строк матрицы A и столбцов матрицы B. Элемент матрицы A*B с индексами i, j есть скалярное произведение i-ой строки матрицы A и j-го столбца матрицы B.

К примеру:

Элемент x3,4 произведения матриц, приведённых выше вычисляется следующим образом

Первая координата в обозначении матрицы обозначает строку, вторая координата — столбец; этот порядок используют как при индексации, так и при обозначении размера. Элемент xij на пересечении строки i и столбца j результирующей матрицы является скалярным произведением i-й строки первой матрицы и j-го столбца второй матрицы. Это объясняет почему ширина и высота умножаемых матриц должны совпадать: в противном случае скалярное произведение не определено.

 

Многомерные списки в Python

ОБРАБОТКА И ВЫВОД ВЛОЖЕННЫХ СПИСКОВ

Часто в задачах приходится хранить прямоугольные таблицы с данными. Такие таблицы называются матрицами или двумерными массивами. В языке программирования Питон таблицу можно представить в виде списка строк, каждый элемент которого является в свою очередь списком, например, чисел. Например, создать числовую таблицу из двух строк и трех столбцов можно так:

A = [ [1, 2, 3], [4, 5, 6] ]

Здесь первая строка списка 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

Для обработки и вывода списка как правило используется два вложенных цикла. Первый цикл по номеру строки, второй цикл по элементам внутри строки. Например, вывести двумерный числовой список на экран построчно, разделяя числа пробелами внутри одной строки, можно так:

for i in range(len(A)):

for j in range(len(A[i]):

print(A[i][j], end = ' ')

print()

То же самое, но циклы не по индексу, а по значениям списка:

for row in A:

for elem in row:

print(elem, end = ' ')

print()

Естественно для вывода одной строки можно воспользоваться методом join:

for row in A:

print(' '.join(map(str, row)))

Используем два вложенных цикла для подсчета суммы всех чисел в списке:

S = 0

for i in range(len(A)):

for j in range(len(A[i])):

S += A[i][j]

Или то же самое с циклом не по индексу, а по значениям строк:

S = 0

for row in A:

for elem in row:

S += elem

СОЗДАНИЕ ДВУМЕРНОГО СПИСКА

Пусть даны два числа: количество строк n и количество столбцов m. Необходимо создать список размером n×m, заполненный нулями.
Очевидное решение оказывается неверным:

A = [[0] * m] * n

В этом легко убедиться, если присвоить элементу A[0][0] значение 1, а потом вывести значение другого элемента A[1][0] — оно тоже будет равно 1! Дело в том, что [0] * m возвращает ccылку на список из m нулей. Но последующее повторение этого элемента создает список из n элементов, которые являются ссылкой на один и тот же список (точно так же, как выполнение операции B = A для списков не создает новый список), поэтому все строки результирующего списка на самом деле являются одной и той же строкой.

Таким образом, двумерный список нельзя создавать при помощи операции повторения одной строки. Что же делать?
Первый способ: сначала создадим список из n элементов (для начала просто из n нулей). Затем сделаем каждый элемент списка ссылкой на другой одномерный список из m элементов:

A = [0] * n

for i in range(n):

A[i] = [0] * m

Другой (но похожий) способ: создать пустой список, потом n раз добавить в него новый элемент, являющийся списком-строкой:

A = []

for i in range(n):

A.append([0] * m)

Но еще проще воспользоваться генератором: создать список из n элементов, каждый из которых будет списком, состоящих из m нулей:

A = [[0] * m for i in range(n)]

В этом случае каждый элемент создается независимо от остальных (заново конструируется список [0] * m для заполнения очередного элемента списка), а не копируются ссылки на один и тот же список.

ВВОД ДВУМЕРНОГО СПИСКА

Пусть программа получает на вход двумерный массив, в виде n строк, каждая из которых содержит m чисел, разделенных пробелами. Как их считать? Например, так:

A = []

for i in range(n):

A.append(list(map(int, input().split())))

Или, без использования сложных вложенных вызовов функций:

A = []

for i in range(n):

row = input().split()

for i in range(len(row)):

row[i] = int(row[i])

A.append(row)

Можно сделать то же самое и при помощи генератора:

A = [list(map(int, input().split())) for i in range(n)]

СЛОЖНЫЙ ПРИМЕР ОБРАБОТКИ ДВУМЕРНОЙ ТАБЛИЦЫ

Пусть дан квадратный массив из n строк и n столбцов. Необходимо элементам, находящимся на главной диагонали, проходящей из левого верхнего угла в правый нижний (то есть тем элементам A[i][j], для которых ij) присвоить значение 1, элементам, находящимся выше главной диагонали – значение 0, элементам, находящимся ниже главной диагонали – значение 2. То есть получить такой массив (пример для n4):

1 0 0 0

2 1 0 0

2 2 1 0

2 2 2 1

Рассмотрим несколько способов решения этой задачи. Элементы, которые лежат выше главной диагонали – это элементы A[i][j], для которых i<j, а для элементов ниже главной диагонали i>j. Таким образом, мы можем сравнивать значения i и j и по ним определять значение A[i][j]. Получаем следующий алгоритм:

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

Данный алгоритм плох, поскольку выполняет одну или две инструкции if для обработки каждого элемента. Если мы усложним алгоритм, то мы сможем обойтись вообще без условных инструкций.

Сначала заполним главную диагональ, для чего нам понадобится один цикл:

for i in range(n):

A[i][i] = 1

Затем заполним значением 0 все элементы выше главной диагонали, для чего нам понадобится в каждой из строк с номером 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

Аналогично присваиваем значение 2 элементам A[i][j] для j=0, …, i-1:

for i in range(n):

for j in range(0, i):

A[i][j] = 2

Можно также внешние циклы объединить в один и получить еще одно, более компактное решение:

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

А вот такое решение использует операцию повторения списков для построения очередной строки списка. i-я строка списка состоит из i чисел 2, затем идет одно число 1, затем идет n-i-1 число 0:

for i in range(n):

A[i] = [2] * i + [1] + [0] * (n - i - 1)

А можно заменить цикл на генератор:

A = [[2] * i + [1] + [0] * (n - i - 1) for i in range(n)]

Множества в Python

Множество — это «мешок», содержащий неупорядоченные уникальные значения. Одно множество может содержать значения любых типов. Если у вас есть два множества, вы можете совершать над ними любые стандартные операции, например, объединение, пересечение и разность.

СОЗДАНИЕ МНОЖЕСТВА

>>> a_set = {1} (1)
>>> a_set
{1}
>>> type(a_set) (2)
<class 'set'>
>>> a_set = {1, 2} (3)
>>> a_set
{1, 2}

Чтобы создать множество с одним значением, поместите его в фигурные скобки ({}).
Множества, вообще-то, реализуются как классы, но пока не беспокойтесь об этом.
Чтобы создать множество с несколькими значениями, отделите их друг от друга запятыми и поместите внутрь фигурных скобок.

Также вы можете создать множество из списка.

>>> a_list = ['a', 'b', 'mpilgrim', True, False, 42]
>>> a_set = set(a_list) (1)
>>> a_set (2)
{'a', False, 'b', True, 'mpilgrim', 42}

Если вы добавляете элементы в множество, оно не запоминает, в каком порядке они добавлялись.

Можно создать пустое множество.

>>> a_set = set() (1)
>>> a_set (2)
set()
>>> type(a_set) (3)
<class 'set'>
>>> len(a_set) (4)
0
>>> not_sure = {} (5)
>>> type(not_sure)
<class 'dict'>

1. Чтобы создать пустое множество, вызовите set() без аргументов.

2. Напечатанное представление пустого множества выглядит немного странно. Вы, наверное, ожидали увидеть {}? Это означало бы пустой словарь, а не пустое множество.

3. Несмотря на странное печатное представление, это действительно множество…

4. …и это множество не содержит ни одного элемента.

5. В силу исторических причуд, пришедших из Python 2, нельзя создать пустое множество с помощью двух фигурных скобок. На самом деле, они создают пустой словарь, а не множество.

ИЗМЕНЕНИЕ МНОЖЕСТВА

Есть два способа добавить элементы в существующее множество: метод add() и метод update().

>>> a_set = {1, 2}
>>> a_set.add(4) (1)
>>> a_set
{1, 2, 4}
>>> len(a_set) (2)
3
>>> a_set.add(1) (3)
>>> a_set
{1, 2, 4}
>>> len(a_set) (4)
3

1. Метод add() принимает один аргумент, который может быть любого типа, и добавляет данное значение в множество.

2. Теперь множество содержит 3 элемента.

3. Множества — мешки уникальных значений. Если попытаться добавить значение, которое уже присутствует в множестве, ничего не произойдет. Это не приведет в возникновению ошибки; просто нулевое действие.

4. Это множество все ещё состоит из 3 элементов.

>>> a_set = {1, 2, 3}
>>> a_set
{1, 2, 3}
>>> a_set.update({2, 4, 6}) (1)
>>> a_set (2)
{1, 2, 3, 4, 6}
>>> a_set.update({3, 6, 9}, {1, 2, 3, 5, 8, 13}) (3)
>>> a_set
{1, 2, 3, 4, 5, 6, 8, 9, 13}
>>> a_set.update([10, 20, 30]) (4)
>>> a_set
{1, 2, 3, 4, 5, 6, 8, 9, 10, 13, 20, 30}

1. Метод update() принимает один аргумент — множество, и добавляет все его элементы к исходному множеству. Так, как если бы вы вызывали метод add() и по очереди передавали ему все элементы множества.

2. Повторяющиеся значения игнорируются, поскольку множество не может содержать дубликаты.

3. Вообще-то, вы можете вызвать метод update() с любым количеством параметров. Когда он вызывается с двумя множествами, метод update() добавляет все элементы обоих множеств в исходное множество (пропуская повторяющиеся).

4. Метод update() может принимать объекты различных типов, включая списки. Когда ему передается список, он добавляет все его элементы в исходное множество.