Одномерные массивы: обработка данных

Создание, заполнение, поиск максимума и минимума, суммирование элементов массива

Что такое массив

В программировании массивом (в языке Python — списком, list) называют упорядоченную последовательность элементов одного типа, хранящихся под одним именем и доступных по порядковому номеру — индексу. Массивы — одна из базовых структур данных, применяемая для хранения таблиц однотипных значений: результатов измерений, оценок учеников, координат точек и т.д. В языке Python роль массива обычно играет встроенный тип list, элементы которого нумеруются с нуля: первый элемент имеет индекс 0, второй — индекс 1, и так далее, последний элемент списка из n элементов имеет индекс n−1.

Индексация и обращение к элементам

Обратиться к элементу массива a по индексу i можно записью a[i]. Общее число элементов (длину массива) в Python возвращает функция len(a). Попытка обратиться к элементу с индексом, выходящим за границы массива (например, a[len(a)]), приводит к ошибке выполнения IndexError — эта ошибка называется выходом за границы массива и часто встречается у начинающих программистов.

$0\le i\le n-1,гдеn=len\left(a\right)$

Создание и заполнение массива

Существует несколько способов создать и заполнить массив в Python: перечислить элементы явно, создать список из n одинаковых значений, заполнить его случайными числами или значениями по формуле с помощью генератора списков (list comprehension).

# Явное задание массива

a = [5, 3, 8, 1, 9, 2]

# Массив из n нулей

n = 10

b = [0] * n

# Заполнение случайными числами от 1 до 100

import random

c = [random.randint(1, 100) for _ in range(n)]

# Заполнение по формуле (квадраты чисел от 0 до n-1)

d = [i ** 2 for i in range(n)]

print(a)

print(c)

print(d)

Ввод массива с клавиатуры

В учебных задачах и на экзамене часто требуется ввести массив с клавиатуры — либо по одному числу на строку, либо все числа сразу в одной строке через пробел. Второй способ реализуется связкой метода split() и функции map().

# Ввод n чисел, каждое на отдельной строке

n = int(input())

a = []

for i in range(n):

a.append(int(input()))

# Ввод чисел в одну строку через пробел

b = list(map(int, input().split()))

Перебор элементов массива

Обработка массива почти всегда начинается с его перебора — последовательного прохода по всем элементам. В Python для этого используют цикл for. Если помимо значения нужен ещё и индекс элемента, применяют функцию enumerate().

a = [5, 3, 8, 1, 9, 2]

# Перебор значений

for x in a:

print(x, end=' ')

print()

# Перебор с индексами

for i, x in enumerate(a):

print(f'a[{i}] = {x}')

# Перебор по индексам (классический способ)

for i in range(len(a)):

print(a[i], end=' ')

Поиск максимального и минимального элементов

Одна из самых распространённых задач обработки массива — найти его наибольший (максимальный) или наименьший (минимальный) элемент, а также определить его индекс (позицию в массиве). В Python есть встроенные функции max() и min(), но для понимания сути алгоритма и для задач, где важен именно индекс, полезно уметь писать поиск максимума вручную.

Идея алгоритма: заводится переменная-«кандидат» на максимум, в которую записывается первый элемент массива; далее каждый следующий элемент сравнивается с текущим кандидатом, и если он больше, кандидат обновляется. После просмотра всех элементов в переменной останется максимальное значение массива.

a = [5, 3, 8, 1, 9, 2]

max_value = a[0]

max_index = 0

for i in range(1, len(a)):

if a[i] > max_value:

max_value = a[i]

max_index = i

print('Максимум:', max_value, 'на позиции', max_index)

# Встроенные функции Python

print(max(a), min(a))

print(a.index(max(a)))

Каждый элемент массива при таком алгоритме сравнивается ровно один раз, поэтому для просмотра всех n элементов требуется n−1 сравнений: время работы алгоритма растёт прямо пропорционально числу элементов — говорят, что его временная сложность линейна и записывается как O(n).

$сложностьпоискамаксимума=O\left(n\right)$

Суммирование элементов и среднее арифметическое

Сумма всех элементов массива a₀, a₁, …, aₙ₋₁ вычисляется накоплением: заводится переменная-накопитель, изначально равная нулю, и к ней последовательно прибавляется каждый элемент массива.

$S=a_0+a_1+...+a_{n-1}$

$среднее=\frac{S}{n}$

a = [5, 3, 8, 1, 9, 2]

s = 0

for x in a:

s += x

average = s / len(a)

print('Сумма:', s)

print('Среднее:', average)

# Встроенная функция

print(sum(a) / len(a))

Подсчёт элементов, удовлетворяющих условию

Часто требуется не просто просуммировать все элементы, а посчитать, сколько среди них чётных, положительных, больше заданного значения и т.п. Для этого заводят счётчик — переменную, которая увеличивается на 1 при выполнении заданного условия.

a = [5, 3, 8, 1, 9, 2, -4, 0]

count_even = 0

count_positive = 0

sum_positive = 0

for x in a:

if x % 2 == 0:

count_even += 1

if x > 0:

count_positive += 1

sum_positive += x

print('Чётных элементов:', count_even)

print('Положительных элементов:', count_positive)

print('Сумма положительных:', sum_positive)

Поиск второго по величине элемента

Более сложная, но часто встречающаяся на практике задача — найти не самый большой, а второй по величине элемент массива (например, для вычисления «серебряного» результата в списке результатов соревнования). Наивное решение — отсортировать массив и взять предпоследний элемент — работает, но требует полной сортировки. Эффективнее решить задачу за один проход, храня сразу два «кандидата»: текущий максимум и второй по величине элемент, обновляя их по мере перебора массива.

a = [5, 3, 8, 1, 9, 2]

first = second = float('-inf')

for x in a:

if x > first:

second = first

first = x

elif first > x > second:

second = x

print('Наибольший элемент:', first)

print('Второй по величине:', second)

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

Реверс массива без использования встроенных функций

Ещё одна классическая операция над массивом — обращение порядка его элементов (реверс). В Python для этого есть удобные встроенные средства (срез a[::-1] или метод a.reverse()), но полезно понимать, как реверс реализуется «вручную»: элементы меняют местами попарно — первый с последним, второй с предпоследним и так далее, — пока не будет пройдена середина массива.

a = [5, 3, 8, 1, 9, 2]

n = len(a)

for i in range(n // 2):

a[i], a[n — 1 — i] = a[n — 1 — i], a[i]

print(a) # [2, 9, 1, 8, 3, 5]

# Эквивалентные встроенные способы

b = [5, 3, 8, 1, 9, 2]

print(b[::-1])

b.reverse()

print(b)

Обратите внимание, что цикл выполняется только до середины массива (n // 2 раз), а не по всей его длине: если продолжить обмен и после середины, элементы просто вернутся в исходное положение — каждая пара будет переставлена местами дважды.

Изменение массива: добавление и удаление элементов

Список в Python — изменяемая структура: элементы можно добавлять и удалять уже после создания массива. Метод append() добавляет элемент в конец списка, insert(i, x) вставляет элемент x на позицию i, remove(x) удаляет первое вхождение значения x, а pop(i) удаляет и возвращает элемент по индексу i (без аргумента — удаляет последний элемент).

a = [5, 3, 8, 1, 9]

a.append(7) # [5, 3, 8, 1, 9, 7]

a.insert(0, 100) # [100, 5, 3, 8, 1, 9, 7]

a.remove(8) # удаляет первое значение 8

last = a.pop() # удаляет и возвращает последний элемент

del a[0] # удаляет элемент по индексу 0

print(a)

Типичные ошибки

Наиболее частая ошибка при обработке массивов — выход за границы индекса: например, использование range(1, len(a) + 1) вместо range(len(a)) приводит к обращению к несуществующему элементу a[len(a)] и ошибке IndexError. Вторая распространённая ошибка — забыть обнулить переменную-накопитель (сумму или счётчик) перед началом цикла, из-за чего результат складывается с «мусорным» значением, оставшимся от предыдущих вычислений. Третья ошибка — путать индекс элемента с его значением, например писать max_index = a[i] вместо max_index = i при поиске позиции максимума. Наконец, при поиске максимума среди элементов, удовлетворяющих условию (скажем, максимума среди отрицательных чисел), нельзя инициализировать кандидата произвольным значением вроде 0 — нужно либо взять первый подходящий элемент, либо использовать заведомо малое значение.

Краткий словарь терминов

Массив (список) — упорядоченная последовательность элементов одного типа, доступных по индексу.

Индекс — порядковый номер элемента массива; в Python нумерация начинается с 0.

Линейный перебор — последовательный просмотр всех элементов массива по очереди.

Накопитель — переменная, в которой пошагово накапливается сумма, произведение или счётчик при обработке массива.

IndexError — ошибка выполнения программы, возникающая при обращении к несуществующему индексу массива.

Сложность алгоритма O(n) — линейная сложность: время работы алгоритма растёт прямо пропорционально числу элементов n.

Заключение

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