Обработка массива

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

Модель обработки массива

Массив содержит элементы, расположенные по индексам. В школьных задачах индексы часто начинаются с \(0\) в Python и с \(1\) в Паскале. Поэтому перед написанием алгоритма нужно установить границы перебора и не обращаться к несуществующему элементу.

Типовая схема такова: создать начальные значения переменных, пройти по всем индексам, проверить условие и изменить результат. Условия записываются с помощью условий, а несколько действий объединяются в составной оператор.

В Python перебор по индексам обычно выглядит так:

1for i in range(n):
2    # обработка a[i]
3    pass

Если сам индекс не нужен, можно перебирать значения напрямую: for x in a. Такой вариант короче, но он не изменяет элементы массива по месту и не сообщает их позиции.

Подсчёт и накопление

Для подсчёта элементов, удовлетворяющих условию, используют счётчик. Перед циклом ему присваивают ноль, а внутри цикла увеличивают на единицу только при выполнении условия.

Здесь \([P(a_i)]\) равно \(1\), если условие \(P\) истинно, и \(0\) в противном случае. Например, количество положительных элементов можно найти так:

1count = 0
2for x in a:
3    if x > 0:
4        count += 1

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

Поиск минимума, максимума и позиции

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

1minimum = a[0]
2position = 0
3for i in range(1, len(a)):
4    if a[i] < minimum:
5        minimum = a[i]
6        position = i

В результате minimum содержит значение минимума, а position — его индекс. Если требуется первая позиция, используют строгое сравнение <. При сравнении <= сохранится последняя позиция минимального элемента.

Фильтрация и преобразование

Фильтрация — отбор элементов, удовлетворяющих условию. Часто результат записывают в новый массив, чтобы не потерять исходные данные. Это удобно, когда нужно сохранить только положительные числа или элементы заданного диапазона.

1positive = []
2for x in a:
3    if x > 0:
4        positive.append(x)

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

1for i in range(len(a)):
2    if a[i] < 0:
3        a[i] = 0

Разобранный пример: подсчёт и замена

Дан массив целых чисел. Требуется посчитать количество отрицательных элементов, а затем заменить все отрицательные элементы на их модули. Рассмотрим массив \([-4, 7, -2, 0, -5]\).

1a = [-4, 7, -2, 0, -5]
2count = 0
3
4for i in range(len(a)):
5    if a[i] < 0:
6        count += 1
7        a[i] = -a[i]
8
9print(count, a)

Ответ: отрицательных элементов \(3\), итоговый массив — \([4,7,2,0,5]\). Алгоритм выполняет один проход, поэтому число сравнений пропорционально \(n\).

Комбинирование условий и границы диапазона

В задачах часто требуется обработать элементы, лежащие в диапазоне. Для включённых границ используют двойное условие: \(L\le x\le R\). В программе это записывают как L <= x <= R или как две проверки с логическим оператором and.

Если границы не входят в диапазон, применяют строгие знаки: L < x < R. Для объединения альтернатив используют or, например: число положительно или равно нулю.

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

Быстродействие и проверка алгоритма

Один полный проход по массиву имеет трудоёмкость \(O(n)\): каждый элемент обрабатывается ограниченное число раз. Два вложенных цикла по всему массиву обычно дают \(O(n^2)\). Для экзамена важно отличать правильный результат от эффективного: повторный поиск минимума внутри внешнего цикла часто можно заменить одним проходом.

• Проверить, с какого индекса начинается массив.
• Убедиться, что цикл обрабатывает каждый нужный элемент ровно один раз.
• Проверить начальные значения счётчиков и накопителей.
• Отдельно проверить пустой массив, если он допускается условием.
• Протестировать случай равных элементов и граничные значения.