"Информатика", Семакин И.Г., Залогова Л.А., Русаков С.В., Шестакова Л.В.
Массив позволяет хранить множество однотипных значений под одним именем, а обрабатывать их — с помощью повторяющихся действий. Один из основных примеров такой обработки — поиск наибольшего элемента. Для этого достаточно один раз пройти по массиву, сравнивая очередное значение с уже найденным максимумом. Разбор задачи показывает, как составить алгоритм, проверить его по шагам и избежать ошибок с индексами и начальным значением.
Текст подготовлен нейронной сетью по теме параграфа и не заменяет учебник — важные факты и формулировки сверяйте с ним.
Массив — это упорядоченный набор элементов одного типа, объединённых общим именем. Например, в массиве A могут храниться результаты измерений или оценки. Массив нужен, когда однотипных данных много: вместо отдельных переменных удобно обращаться к ним по номеру.
Индекс — номер элемента массива, по которому к нему обращаются. Запись A[i] означает элемент массива A с индексом i. Индекс помогает указать конкретное значение в цикле, поэтому важно знать, с какого числа начинается нумерация в используемом языке программирования.
Обработка массива — последовательное выполнение действий над его элементами. Например, можно сравнивать значения, считать подходящие элементы или вычислять сумму. Такой подход нужен, чтобы программа могла выполнить однотипную работу для всего набора, не повторяя вручную отдельную команду для каждого значения.
Наибольший элемент — значение массива, которое не меньше любого другого его значения. Его поиск состоит в последовательном сравнении элементов. Текущий максимум обозначим max: после проверки очередной части массива max должен быть наибольшим среди уже просмотренных значений.
Обработка массива обычно строится вокруг цикла: его тело выполняется для элементов с разными индексами. Это удобно, потому что команда обращения к A[i] остаётся одинаковой, а меняется только i. Цикл должен охватить все элементы, иначе часть данных не повлияет на ответ. Поэтому до написания программы определяют начальный и конечный индексы.
При поиске максимума нельзя сразу сравнивать элементы с произвольной константой, например с нулём. Если все значения отрицательные, ноль окажется больше каждого из них, хотя в массиве его нет. Надёжнее считать первым найденным максимумом первый элемент массива: max = A[1]. Тогда начальное значение гарантированно взято из данных.
После начальной установки остаётся проверить элементы со второго по последний. Для каждого элемента сравнивают A[i] и max. Если A[i] больше, прежний максимум уже не подходит для просмотренной части массива, поэтому его заменяют на A[i]. Если новое значение меньше или равно max, ничего менять не нужно: найденный ранее максимум остаётся наибольшим.
Такое рассуждение сохраняет полезное свойство на каждом шаге: после обработки позиции i переменная max хранит максимум среди A[1], A[2], …, A[i]. Вначале это верно для одного элемента. Затем сравнение либо оставляет прежний максимум, либо заменяет его на более крупное значение, поэтому свойство продолжает выполняться. После последней итерации просмотрен весь массив, а значит max и есть ответ.
Если в массиве несколько одинаковых наибольших значений, алгоритм всё равно вернёт правильное значение. Условие A[i] > max не заменяет максимум равным ему элементом, но для поиска самого значения это не имеет значения. Если требуется найти ещё и индекс максимума, нужно отдельно решить, какой индекс выбирать при совпадении: первый или последний.
Количество сравнений при таком поиске пропорционально количеству элементов: для массива из n элементов после начальной установки выполняется n − 1 проверка. Поэтому алгоритм подходит и для больших массивов: он просматривает данные один раз и хранит только текущий максимум. Это пример линейного алгоритма, потому что увеличение размера массива примерно во столько же раз увеличивает число шагов.
| Этап | Действие | Зачем это нужно |
|---|---|---|
| Начало | max = A[1] | Задаём максимум значением из массива |
| Просмотр | Проверяем A[i] для i от 2 до n | По очереди рассматриваем оставшиеся элементы |
| Сравнение | Если A[i] > max, то max = A[i] | Сохраняем самое большое из просмотренных значений |
| Завершение | Выводим max | После полного просмотра получаем максимум всего массива |
Читайте таблицу сверху вниз: каждый этап использует результат предыдущего. Границы цикла зависят от нумерации элементов: здесь предполагается, что индексы идут от 1 до n. Если в программе индексация начинается с 0, начальное значение берут из A[0], а цикл начинают с 1.
Условие. Дан массив A из пяти целых чисел: 4, −2, 7, 7, 1. Требуется найти наибольшее значение. Индексы элементов начинаются с 1. Перед вычислением полезно заметить, что максимальных значений может быть несколько: это не мешает найти само число, но важно при поиске его позиции.
Сначала принимаем первый элемент за текущий максимум: max = A[1] = 4. Это безопасное начальное значение, потому что оно действительно входит в массив, а не выбрано наугад.
Переходим к A[2] = −2. Сравниваем −2 с 4: новый элемент меньше, поэтому max оставляем равным 4. Среди первых двух элементов максимум по-прежнему найден правильно.
Проверяем A[3] = 7. Поскольку 7 больше 4, заменяем max на 7. Теперь это наибольшее значение среди первых трёх элементов.
Проверяем A[4] = 7. Значение равно текущему максимуму, а условие замены — строгое «больше». Поэтому max остаётся равным 7; для ответа о значении повтор не важен.
Проверяем A[5] = 1. Оно меньше 7, значит максимум менять не нужно. Все пять элементов просмотрены, поэтому найденное значение уже является наибольшим во всём массиве.
Для проверки можно записать изменения в таблицу: после первого элемента max равен 4, после второго — 4, после третьего — 7, после четвёртого — 7, после пятого — 7. Такая запись помогает обнаружить пропущенный элемент или неверное сравнение. В программе логика может быть записана так: max := A[1]; затем для i от 2 до n, если A[i] > max, присвоить max := A[i].
Ответ: наибольший элемент массива равен 7. Если требуется вывести его индекс, при поиске первого максимума сохраняют индекс только при строгом увеличении max; здесь будет найден индекс 3. Чтобы получить индекс последнего максимума, условие сравнения меняют на A[i] ≥ max.
Начинать максимум с нуля. Так делают, потому что ноль кажется удобной отправной точкой. Но в массиве из отрицательных чисел ответ окажется неверным; проверьте алгоритм на примере −5, −2 и убедитесь, что начальное значение взято из массива.
Пропускать первый или последний элемент. Ошибка возникает из-за неверных границ цикла или путаницы в индексации. Проверьте, что каждый индекс массива встречается при просмотре; для нумерации от 1 цикл после A[1] должен пройти от 2 до n.
Заменять максимум меньшим значением. Это происходит, если перепутать знак сравнения. Проследите за условием: новый элемент должен менять max только тогда, когда он больше текущего максимума.
Не учитывать массив из одного элемента. В таком случае цикл после начальной установки не выполняется, и это нормально: единственный элемент уже является максимумом. Проверьте, что программа не обращается к несуществующим индексам при n = 1.
Поиск максимума опирается на циклы: цикл позволяет выполнить одно сравнение для каждого элемента массива. Он также использует условный оператор, который выбирает, нужно ли обновить текущий максимум. Массивы встречаются в задачах на вычисление суммы, среднего значения и подсчёт элементов с заданным свойством; во всех этих случаях важно правильно задать границы просмотра. Пошаговая таблица связывает алгоритм с отладкой программы: по ней можно проверить, как меняются значения переменных.
Элементы массива обрабатывают по индексам, обычно в цикле.
Для поиска максимума сначала присваивают max значение первого элемента.
Остальные элементы сравнивают с max и заменяют его только при необходимости.
После полного просмотра массива max содержит его наибольшее значение.
Проверяйте индексацию, границы цикла и работу алгоритма на отрицательных числах и массиве из одного элемента.
§ 19. Одна задача обработки массива
