§ 9.4. Двумерные массивы. Типы set и dict. Двумерные массивы разных типов

Школьный курс C++
Содержание

Что такое двумерный массив?

Двумерный массив структура данных, хранящая прямоугольную таблицу, которая называется матрицей. В математике матрица, имеющая m строк и n столбцов (m × n), представляется в следующем виде:

Матрица, в которой количество строк и столбцов одинаково, называется – квадратной. Традиционно, для обозначения индекса строки используют латинскую i, а индекс столбца обозначают латинской j. Элементы имеющие равные индексы (i == j) находятся на главной диагонали. Диагональ, проходящая через другие два угла, называется побочной.

В чем смысл такой организации данных? Матрицы используются в различных разделах математики. Одно из важных предназначений матриц – это описание векторного пространства, которое является предметом изучения линейной алгебры. Трансформация объекта (масштабирование, скос, вращение) и преобразование координат описывается с помощью матриц.
В большинстве случаев, как в математике, так и в программировании, с матрицей работают как с единым объектом. Однако, во многих языках, в том числе и в python, структуры данных (или типа) “двумерный массив” не существует. Двумерные массивы создаются как массив массивов. Это означает, что элементами одномерного (линейного) массива являются линейные массивы равной фиксированной длины.

Двумерный список

Рассмотрим вначале простой случай, когда элементами списка (линейного массива) являются тоже списки. Создать двумерный список (с инициализацией или без таковой) не сложно:

A = [[],[],[],[],[]]
L = [[2,3,4],[4,3,7],[8,3,5]]

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

Программа 9.4.1
Ar = []
for i in range(10):
    temp = []
    for j in range(10):
        temp.append(0)
    Ar.append(temp)

for i in range(10):
    for j in range(10):
        print(Ar[i][j], end=' ')
    print()

Вывод

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 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 
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 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 
Матричный вывод мы обсуждали ранее здесь.

Аналогичный результат, но в более компактной форме, можно получить с помощью генератора:

L = [[0] * 10 for j in range(10)]
print(L)

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

Обратите внимание, что счет индексов в массивах, как во внешнем, так и во вложенных начинается с 0!

В ручную матрицы заполнять оч. долго, поэтому в тестовых задачах заполнение элементов двумерного массива производится с помощью генератора случайных чисел.

Программа 9.4.2
from random import randint
Ar = [[] for i in range(7)]
for i in range(7):
    for j in range(7):
        Ar[i].append(randint(10,99))
        print('{:<3d}'.format(Ar[i][j]), end='')
    print()

Возможный вывод

45 32 82 47 86 46 42 
92 43 56 97 86 66 31 
79 21 43 81 90 39 89 
91 51 57 41 39 76 79 
44 75 48 38 49 19 65 
29 34 98 38 68 69 16 
79 46 29 81 30 36 32

Решим следующую задачу.
Задача 1. Дана матрица размера m × n. Для каждой строки матрицы найти сумму её элементов. Выведите номер строки в которой сумма максимальна, а также элементы этой строки. Для заполнения матрицы используйте генератор случайных чисел.

Программа 9.4.3
from random import randint
m = int(input('m = '))
n = int(input('n = '))
Ar = [[] for i in range(m)]
# Исходный массив нужно вывести:
for i in range(m):
    for j in range(n):
        Ar[i].append(randint(10,99))
        print('{:<3d}'.format(Ar[i][j]), end='')
    print()
# решаем задачу
Max, k = 0, 0
for i in range(m): 
    Sum = 0
    for j in range(n):
        Sum += Ar[i][j]
    if Sum > Max: 
        Max = Sum
        k = i
print('Максимальная сумма', Max,
      'находится в строке - ', k,
      '\nЭлементы этой строки:', end=' ')
for j in range(n):
    print('{:<3d}'.format(Ar[k][j]), end='')

Возможный вывод

m = 5
n = 7
55 95 69 26 30 56 61 
57 43 12 31 57 93 15 
67 36 38 58 99 71 36 
38 98 47 83 28 20 59 
13 72 47 77 35 15 88 
Максимальная сумма 405 находится в строке -  2 
Элементы этой строки: 67 36 38 58 99 71 36

Другой вариант решения задачи с использованием стандартной функции sum():

Max, k, j = 0, 0, 0
for i in Ar:
    Sum = sum(i)
    if Sum > Max:
        Max = Sum
        k = j
    j += 1

Обратите внимание, что в данном варианте производится итерация не по последовательности range(), а по массиву Ar. Следовательно, в переменной цикла i перебираются не индексы, а элементы-массивы.
Нужно сказать, что “оформление” матрицы в виде массива-массивов не является чем-то обязательным, а предназначено лишь для наглядного представления и удобной работы (это не относится к двумерным массивам, обсуждаемым ниже). Вместо двумерного массива можно использовать одномерный массив. Для этого, число строк и столбцов сохраняется в виде констант (например, row и col). Тогда программу, аналогичную программе 9.4.2, можно составить следующим образом:

from random import randint
row, col = 7, 7
Ar = []
for i in range(row * col):
    Ar.append(randint(10,99))
    print('{:<3d}'.format(Ar[i]), end='')
    if not (i+1) % col:
        print()

Типы set (множество) и dict (словарь)

set

set является неупорядоченным типом коллекции уникальных (не повторяющихся) элементов – ключей (хэшируемых объектов).

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

Когда говорится о неупорядоченности, то имеется ввиду, что элементы set не имеют порядка следования и не поддерживают порядок вставки так, как, например, в последовательности list. К его элементам нельзя обратиться по индексу или выполнить срез, поскольку данные операции не поддерживаются. Тем не менее, реализация внутреннего представления set приводит к такой упорядоченности данных, что поиск в этом типе последовательности осуществляется очень быстро (по сравнению с поиском в list). Достигается это путем реализации set в виде хэш-таблицы (как unordered_set в C++).
set является изменяемым типом, иными словами, поддерживает операции вставки и удаления элементов. Из этого следует, что он, сам по себе, не может быть хэш-объектом, т.е. set не может являться элементом другого set. Вариантом неизменяемого set является frozenset, который поддерживает все немодифицирующие операции set.
Множество можно создать с помощью фигурных скобок, либо с помощью функции преобразования (она же конструктор типа) set():

s0 = {}
s1 = {'alpha', 'beta', 'gamma'}
s2 = set('abracadabra')
s3 = set(['a', 'b', 'c', 'd'])

set является нестрогим аналогом математического объекта множество, поэтому для него реализованы основные операции над множествами. Список общих операций для set и frozenset см. в таблице ниже.

Операции set и frozenset
Операция Описание
len(s) Мощность множества (количество элементов)
x in s
x not in s
Тест на членство (вхождение)
isdisjoint(other) Возвращает True, если нет общих членов с other
issubset(other)
set <= other
Проверяет, все ли элементы находятся в other
set < other Проверяет, что set является подмножеством other
issuperset(other)
set >= other
Проверяет, все ли элементы множества other есть в set
set > other Проверяет, является ли set надмножеством
union(*others)
set | other |
Объединение множеств (возвращает новое множество)
intersection(*others)
set & other & …
Пересечение множеств (возвращает множество в котором только элементы общие для set и other)
difference(*others)
set – other – …
Возвращает множество элементов, которых нет в other
symmetric_difference(other)
set ^ other
Возвращает элементы, которые есть либо в set, либо в other, но не в обоих одновременно (исключающее или)
copy() Возвращает неполную копию множества

Задача 2. Даны две строки S1 и S2. Получить множество слов, которые встречаются только в S1 или в S2 (но не в обоих одновременно), с учетом регистра символов (т. е. 'ad' и 'Ad' – разные слова).

Программа 9.4.4
import string # для константы punctuation
S1 = input('S1 => ')
S2 = input('S2 => ')
# Функция очистки строки от всех знаков пунктуации
# и получения списка слов
def ClrPunct(S):
    S = list(S) # Список символов
    # Множество знаков пунктуации
    p = set(string.punctuation)
    for r in S:
        while r in p and r in S:
            S.remove(r)
    S = ''.join(S) # Собираем строку из оставшихся символов
    return S.split() # Возвращаем массив слов
# Получаем множества слов
S1 = set(ClrPunct(S1))
S2 = set(ClrPunct(S2))
# Получаем множество таких слов, которые встречаются
# только в S1 или в S2 но не в обоих одновременно
print(S1 ^ S2)

Вывод

S1 => A posse ad esse non valet consequential
S2 => Ab esse ad posse valet consequentia
{'A', 'consequential', 'consequentia', 'Ab', 'non'}
A posse ad esse non valet consequential — (лат.) По возможному ещё не следует заключать о действительном. Ab esse ad posse valet consequentia — (лат.) По действительному заключению о возможном.

Для изменяемого типа множества set определены следующие операции:

Модифицирующие операции set
Операция Описание
update(*others)
set |= other | …
Обновляет множество элементами других множеств.
intersection_update(*others)
set &= other & …
Обновляет множество, сохранив только те элементы, которые являются общими с другими множествами (пересечение).
difference_update(*others)
set -= other | …
Обновляет множество, удалив элементы, найденные в других множествах
symmetric_difference_update(other)
set ^= other
Обновляет множество, сохранив только элементы, которые найдены в любом другом множестве, но не являются общими (исключающее или).
add(elem) Добавляет элемент elem в множество
remove(elem) Удаляет элемент elem из множества. Возбуждается исключение, если такого элемента в множестве нет
discard(elem) Удаляет элемент elem из набора, если он присутствует в множестве
pop() Удаляет и возвращает произвольный элемент из множества. Возбуждается исключение, если набор пуст
clear() Удаляет все элементы из множества
dict

Тип dict (словарь) является одним из встроенных типов. dict представляет собой ассоциативный массив (хэш-массив, хэш), в котором ключу сопоставляется определенное значение. Т. е. элемент (mapping object) представляет из себя пару: {Ключ: Значение}. Ключ (так же, как и в set) – хэшируемый объект, которым не может быть никакой объект изменяемого типа. Ключ – неизменяемая часть пары. Значение (ключа) – это произвольный изменяемый объект (любого типа).
Словари создаются либо с помощью фигурных скобок, либо с помощью конструктора dict():

d1 = {'star': 1253, 'galaxy': 8467, 'nebula': 4235}
d2 = {1253: 'star', 8467: 'galaxy', 4235: 'nebula'}
d3 = dict(star = 1253, galaxy = 8467, nebula = 4235)
d4 = dict([(1253, 'star'), (8467, 'galaxy'), (4235, 'nebula')])
# Можно использовать функцию zip()
d5 = dict(zip(['star', 'galaxy', 'nebula'], [1253, 8467, 4235]))

Словарь поддерживает операцию индексации [], но в качестве индекса выступает не, собственно, индекс (которого нет в ассоциативном массиве), а ключ, например:

D = {1253: 'star', 8467: 'galaxy', 4235: 'nebula'}
print(D[1253], D[8467], D[4235])

Вывод

star galaxy nebula

Ниже в таблице приведены операции, которые определены для словаря.

Операции dict
Операция Описание
list(d) Возвращает список всех ключей, используемых в словаре
len(d) Возвращает количество элементов в словаре d
d[key] Возвращает значение d с помощью ключа key. Возбуждает исключение, если ключа нет в словаре.
d[key] = value Устанавливает значение value ключу key
del d[key] Удаляет элемент словаря
key in d
key not in d
Проверка на членство ключа в словаре
iter(d) Возвращает итератор по ключам словаря
clear() Удалить все элементы словаря
copy() Возвращает неполную копию словаря
fromkeys(iterable[, value]) Создает словарь с ключами iterable и значением value (по умолчанию None)
get(key[, default]) Возвращает значение ключа или None
items() Возвращает новый список-представление элементов словаря
keys() Возвращает новый список-представление ключей словаря
pop(key[, default]) Удаляет ключ и возвращает значение; если значения нет, то значение по умолчанию; если нет ключа или не указано значение по умолчанию, то возбуждается исключение
popitem() Удаляет и возвращает пару из словаря. Пары возвращаются в порядке LIFO
reversed(d) Возвращает реверсивный итератор по ключам словаря.
setdefault(key[, default]) Если ключ находится в словаре,то возвращает его значение. Если нет, то вставляет ключ со значением по умолчанию и возвращает значение по умолчанию. По умолчанию – None.
update([other]) Обновляет словарь парами (ключ: значение) из other, перезаписав существующие ключи.
values() Возвращает новый список-представление значений ключей словаря
d | other Создаёт новый словарь объединением ключей и значений d и other. Значения other имеют приоритет, если d и other используют равные ключи.
d |= other Обновляет словарь d ключами и значениями из other. Значения other имеют приоритет, если d и other используют равные ключи.

Решим задачу в которой используется словарь.
Задача 3. Дан массив средних показаний выпадения осадков по месяцами года в определенной местности. Определить наиболее дождливый месяц, наиболее засушливый месяц, среднее значение мм осадков за год, в какой сезон выпадает наибольшее количество осадков и какой сезон является наиболее засушливым.

Программа 9.4.5
# Словарь сопоставления числового значения месяца - 
# его текстовому значению
M = {1: 'январь', 2:'февраль', 3:'март', 4:'апрель', 
     5:'май', 6:'июнь', 7:'июль', 8:'август',
     9:'сентябрь', 10:'октябрь', 11:'ноябрь', 12:'декабрь'} 
# Получаем данные в словарь:
D = {}
for r in range(12):
    val = int(input())
    D |= {r+1:val}
print('Наиболее дождливый месяц =>',
      M.get(max(D, key=D.get)))
print('Наиболее засушливый месяц =>', 
      M.get(min(D, key=D.get)))
print('Сред. значение за год => {:.2f}'
      .format(sum(D.values()) / len(D)))
print('Самый дождливый сезон =>', end='')
S = {D.get(1) + D.get(2)  + D.get(12) : 'зима',
     D.get(3) + D.get(4)  + D.get(5)  : 'весна',
     D.get(6) + D.get(7)  + D.get(8)  : 'лето',
     D.get(9) + D.get(10) + D.get(11) : 'осень'}
print(S.get(max(S)))
print('Самый засушливый сезон =>', S.get(min(S)))
Вводились данные для г. Ейска

Вывод

90
77
64
61
60
79
54
55
53
54
73
94
Наиболее дождливый месяц => декабрь
Наиболее засушливый месяц => сентябрь
Сред. значение за год => 67.83
Самый дождливый сезон => зима
Самый засушливый сезон => осень
Обратите внимание на использование функций max() и min(). Поскольку мы имеем дело с последовательностью, в которой элемент представляет из себя пару (т.е. сложный объект), то необходимо передать функции необязательный аргумент key, подсказывающий какую часть пары нужно сравнивать (ключ или значение?). Этот аргумент принимает значение функционального объекта. В данном случае – это функция get, возвращающая значение ключа. Поэтому будут сравниваться значения ключей, а не сами ключи. Возвращается ключ, который содержит максимальное или минимальное значение.

Двумерные массивы разных типов

Двумерными могут быть не только списки, но и другие типы последовательностей как изменяемые, так и неизменяемые. При этом, массив одного типа может содержать, в качестве элементов, последовательность другого типа. Неизменяемая последовательность (кортеж) может содержать в качестве элементов списки (равно и наоборот). Количество элементов кортежа нельзя изменить, но списки, как изменяемые элементы, – можно! Элементами списка могут быть типы set и dict, но элементом множества или ключом словаря не могут быть изменяемые последовательности (такие, как list или set)! При этом, размеры массивов-элементов могут иметь переменную длину (такие двумерные массивы нельзя уже называть матрицей, поскольку в матрице строки и столбцы имеют равную длину; нельзя также назвать матрицей массивы, в которых элементами являются хэши). Двумерные массивы разных типов (с учетом их методов) по сложности уже близки к комбинированным типам, таким, как записи (в Pascal), структуры (в C/C++) или классы (C/C++/python). Эти типы мы будем рассматривать в старших классах.
Рассмотрим пример задачи.
Задача 4. В колледже N учащихся проходят курсовую подготовку по 4 предметам: A, B, C и D. Каждый курсант имеет уникальный номер (id). Нумерация начинается с 0. По окончании обучения они сдают выпускные экзамены по этим предметам. Результаты экзамена оцениваются по 10-бальной шкале. Диплом с отличием получает только тот выпускник курсов, который показал общий результат не менее 80% от максимальной суммы баллов по всем предметам. Программа “Экзаменатор” фиксирует результаты учащихся. По окончании экзамена, программе подан запрос на выборку данных: необходимо вывести данные тех учащихся, которые получили красный диплом, их id, средний и максимальный балл в порядке возрастания идентификаторов. В последней строке программа выводит общие средние баллы по всем предметам.

Программа 9.4.6
# Список курсантов
P = []
N = int(input('N = '))
for j in range(N):
    print(j+1)
    # Записываем результаты каждого курсанта
    D = {'A': None, 'B': None, 'C': None, 'D': None}
    D['A'] = int(input('A = '))
    D['B'] = int(input('B = '))
    D['C'] = int(input('C = '))
    D['D'] = int(input('D = '))
    # Добавляем словарь в список
    P.append(D)
# Обработка запроса
# Открываем протокол результатов экзамена
j = 1
SumA, SumB, SumC, SumD = 0, 0, 0, 0
for D in P:
    SumA += D['A']
    SumB += D['B']
    SumC += D['C']
    SumD += D['D']
    # Если суммы достаточно на красный диплом
    # и перешагнул порог по каждому предмету
    if sum(D.values()) >= 32 and\
        D['A'] >= 5 and D['B'] >= 5 and\
            D['C'] >= 5 and D['D'] >= 5:
        print('id =', j,            # Идентификатор
              sum(D.values()) / 4,  # Ср. балл
              max(D.values()))      # Max балл
    j += 1  
print('Ср. A = {:.2f}, B = {:.2f}, C = {:.2f}, D = {:.2f}.'
      .format(SumA / N, SumB / N, SumC / N, SumD / N))

Ввод

N = 3
1
A = 5
B = 9
C = 8
D = 7
2
A = 10
B = 8
C = 6
D = 9
3
A = 8
B = 8
C = 9
D = 7

Вывод

id = 2 8.25 10
id = 3 8.0 9
Ср. A = 7.67, B = 8.33, C = 7.67, D = 7.67.

Приложение

Примеры решения задач
Вопросы
Темы сообщений
Задания А
Задания Б
Задания С
Ссылки
1 Звезда2 Звезды3 Звезды4 Звезды5 Звезд (1 оценок, среднее: 5,00 из 5)
Загрузка...

Если вы нашли ошибку, пожалуйста, выделите фрагмент текста и нажмите Ctrl+Enter.

Обсуждение закрыто.