§ 26. Типовые задачи обработки массивов

Определения и обозначения

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

Элемент массива — отдельное значение, входящее в эту последовательность. Чтобы обратиться к нему, указывают имя массива и индекс: например, запись a[i] означает элемент массива a с индексом i. Такое обращение позволяет использовать конкретное значение в вычислении или проверять его условием.

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

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

Как это устроено

Обработку массива обычно начинают с перебора, потому что условие задачи может относиться к любому его элементу. Цикл последовательно задаёт допустимые индексы: от первого до последнего, не выходя за границы массива. Если элементов n и индексация начинается с нуля, обычно перебирают индексы от 0 до n − 1; при нумерации с единицы — от 1 до n.

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

Среднее арифметическое получают делением найденной суммы на количество элементов: average = sum / n. Размер массива n известен, поэтому отдельный подсчёт его элементов не нужен. Если n равно нулю, деление невозможно, а у пустого массива нет среднего; такой случай нужно проверить до вычисления.

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

Количество элементов, удовлетворяющих условию, хранят в счётчике. Его начинают с нуля и увеличивают на единицу только тогда, когда текущий элемент проходит проверку, например a[i] ≥ порога. Счётчик отвечает на вопрос «сколько?», а накопитель суммы складывает сами значения; при необходимости оба результата обновляют в одном цикле.

Типовые задачи обработки массива и основные приёмы

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

Разбор задач

Задача 1. Дан массив целых чисел. Найти сумму его элементов. Поскольку сумма зависит от каждого значения, нужно пройти массив полностью, а не ограничиваться первым или последним элементом. Для промежуточного результата заведём переменную sum.

1. Перед циклом присвоим sum значение 0, чтобы в ответ не попало постороннее слагаемое.
2. Последовательно переберём все допустимые индексы массива.
3. На каждом шаге прибавим текущий элемент: sum = sum + a[i]. После последнего шага накопитель содержит сумму всех элементов.

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

Задача 2. Дан массив оценок. Найти средний балл и количество оценок не ниже заданного порога. Оба результата можно получить за один проход: каждую оценку нужно включить в сумму, а для счётчика дополнительно проверить условие. Пусть число оценок равно n, а порог обозначен p.

1. Перед перебором зададим sum = 0 и count = 0.
2. Для каждой оценки a[i] увеличим сумму на её значение. Если a[i] ≥ p, увеличим count на единицу.
3. После цикла проверим, что n больше нуля, и вычислим средний балл как sum / n. Счётчик уже содержит количество оценок не ниже порога.

Ответ: средний балл равен sum / n, число оценок не ниже порога равно count. Например, оценки 4, 5 и 3 при пороге 4 дают сумму 12, среднее 4 и счётчик 2. При пустом массиве среднее не вычисляют.

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

1. Проверим, что массив непуст, и положим max = a[первый индекс].
2. Переберём элементы и заменим max текущим значением, если оно больше сохранённого.
3. Обнулим count и ещё раз переберём массив. Каждый раз, когда a[i] равно max, увеличим count на единицу.

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

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

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

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

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

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

Связь с другими темами

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

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

Что запомнить

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