Перебор массива

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

Идея последовательного перебора

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

Переменная \(i\) называется индексом или счётчиком цикла. На каждом шаге она принимает очередное значение, а программа обращается к элементу \(a[i]\). Общая схема такова: прочитать элемент, проверить условие или выполнить действие, перейти к следующему индексу.

for i in range(n):
    x = a[i]
    # обработка элемента x

for i := 1 to n do
begin
  x := a[i];
  { обработка элемента x }
end;

Типовые действия при переборе

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

• Подсчёт: увеличить счётчик, если элемент удовлетворяет условию.
• Сумма: прибавить очередной элемент к накопленной сумме.
• Поиск: сравнить элемент с искомым значением и запомнить результат.
• Выбор минимума или максимума: сравнивать элементы с текущим лучшим значением. Подробный случай разобран на странице минимума и максимума в массиве.
• Преобразование: заменить элемент новым значением, например увеличить все положительные элементы в два раза.

Здесь квадратные скобки означают индикатор условия: они равны 1, если условие истинно, и 0 — если ложно. На практике вместо такой математической записи используется if.

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

Этот фрагмент считает положительные элементы. Начальное значение count = 0 обязательно: до просмотра массива найдено ноль подходящих элементов. Аналогично сумма обычно начинается с нуля, а произведение — с единицы. Среднее арифметическое нельзя вычислять до проверки, что количество выбранных элементов не равно нулю; отдельная страница посвящена среднему арифметическому элементов массива.

Как правильно строить алгоритм

Перед написанием цикла полезно назвать величину, которую требуется получить, и определить её начальное значение. Затем нужно выбрать условие обработки и способ обновления результата. Например, для количества элементов, больших \(k\), нужны переменная-счётчик, начальное значение 0, проверка a[i] > k и увеличение счётчика на 1.

Разобранный пример: сумма и количество

Дан массив из \(n\) целых чисел. Требуется найти среднее арифметическое положительных элементов. Если положительных элементов нет, вывести сообщение об отсутствии результата.

sum_positive = 0
count = 0

for x in a:
    if x > 0:
        sum_positive += x
        count += 1

if count > 0:
    average = sum_positive / count
    print(average)
else:
    print("нет положительных элементов")

Рассмотрим массив \([-3, 5, 2, -1]\). После обработки \(-3\) значения не меняются. После 5 получаем sum = 5, count = 1. После 2 — sum = 7, count = 2. Последний элемент отрицательный, поэтому итоговое среднее равно \(7/2=3{,}5\).

Перебор с изменением массива

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

for i in range(len(a)):
    if a[i] < 0:
        a[i] = -a[i]

После такого прохода все элементы становятся неотрицательными. Для простого чтения можно использовать for x in a, но для изменения обычно нужен for i in range(len(a)). Ввод и вывод массива рассматриваются на соседних страницах ввода массива и вывода массива. Если обрабатывать нужно только часть массива, сначала изучите обработку отрезка массива. Обратный порядок просмотра разобран на странице обратного перебора массива.