"Информатика (базовый и углублённый уровни) (в 2 частях)", Поляков К.Ю., Еремин Е.А.
Алгоритмы обработки массивов помогают находить нужные значения, считать элементы по условию и упорядочивать данные. Обычно программа проходит по массиву циклом, обращаясь к каждому элементу по индексу. Чтобы получить ответ, она хранит промежуточный результат: например, текущий максимум, сумму или счётчик. Понимание этих приёмов позволяет решать задачи с числами и оценками, а также готовит к изучению более быстрых способов обработки данных.
Текст подготовлен нейронной сетью по теме параграфа и не заменяет учебник — важные факты и формулировки сверяйте с ним.
Алгоритм обработки массива — последовательность действий, которая получает из элементов массива нужный результат или изменяет их порядок. Например, программа может найти самое большое число, вычислить сумму или расставить значения по возрастанию. Такой алгоритм нужен, чтобы поручить компьютеру повторяющуюся работу с данными и получить ответ по чётким правилам.
Поиск максимального или минимального элемента — последовательный просмотр массива с сохранением текущего наибольшего или наименьшего значения. Текущим кандидатом сначала считают один из элементов, а затем сравнивают с ним остальные. Этот способ нужен, когда требуется найти крайнее по значению число, не меняя сам массив.
Подсчёт элементов по условию — определение количества элементов массива, удовлетворяющих заданному условию. Например, можно посчитать оценки не ниже четырёх или числа, делящиеся на три. Для такой задачи используют счётчик: он показывает, сколько подходящих элементов уже встретилось.
Сортировка массива — упорядочивание его элементов по возрастанию или убыванию. После сортировки значения расположены в заданном порядке, поэтому их удобнее просматривать и сравнивать. Сортировка выбором — один из способов выполнить такую перестановку, каждый раз помещая на нужное место наименьший элемент оставшейся части.
Большинство алгоритмов обработки массива просматривает элементы по очереди с помощью цикла. Индекс — это номер элемента, по которому программа к нему обращается; в зависимости от языка программирования нумерация может начинаться с нуля или единицы. Цикл меняет индекс и повторяет действие для очередного элемента, потому что иначе пришлось бы отдельно записывать одинаковые команды для каждой позиции. Границы цикла должны соответствовать допустимым индексам массива, иначе программа может пропустить элемент или обратиться за пределы массива.
При поиске максимума или минимума начальным кандидатом выбирают первый элемент, а затем сравнивают с ним остальные. Если очередное значение больше кандидата, его записывают как новый максимум; для минимума действуют наоборот. Первый элемент подходит как начальное значение, потому что он уже принадлежит массиву и сравнивается с остальными на тех же основаниях. Если нужно сообщить позицию результата, вместе со значением обновляют и индекс кандидата.
Сумму элементов накапливают в переменной, предварительно присвоив ей ноль. Ноль здесь удобен: прибавление к нему первого значения даёт именно это значение, поэтому в результат не попадает лишнее число. Количество элементов, подходящих под условие, накапливают отдельно: перед циклом счётчик обнуляют, а внутри увеличивают на единицу только при истинном условии. Разные переменные нужны потому, что сумма хранит числовое значение, а счётчик — число найденных элементов.
Среднее арифметическое находят делением накопленной суммы на число элементов. Делить нужно именно на количество значений, участвовавших в сумме: так определяется среднее на один элемент. Для непустого массива количество не равно нулю, поэтому проверка деления на ноль не требуется. Если массив может быть пустым, сначала следует проверить его длину, иначе вычислить среднее невозможно.
При сортировке выбором на каждом шаге находят наименьший элемент неупорядоченной части массива и меняют его местами с первым элементом этой части. После обмена этот элемент занимает окончательное место, а упорядоченная часть становится длиннее на одну позицию. Поиск минимума продолжают уже среди оставшихся значений, поэтому ранее расставленные элементы не нужно переставлять снова. Повторяют шаги, пока не останется неупорядоченной части.
Таблица показывает, какие промежуточные данные хранить и что делать с каждым очередным элементом. Сопоставьте задачу с переменной: это помогает понять, что нужно подготовить до запуска цикла. При сортировке результатом становится переставленный массив, а не отдельное число.
| Задача | Что хранится в переменной | Действие при просмотре элемента | Результат |
|---|---|---|---|
| Поиск максимума или минимума | Текущий экстремальный элемент | Сравнить с текущим кандидатом и при необходимости заменить его | Значение и, при необходимости, индекс найденного элемента |
| Нахождение суммы | Накопленная сумма | Прибавить очередной элемент | Сумма элементов |
| Подсчёт по условию | Счётчик | Проверить условие и увеличить счётчик, если оно истинно | Количество подходящих элементов |
| Сортировка выбором | Позиция очередного минимума | Найти минимум в неупорядоченной части и обменять элементы | Массив, упорядоченный по возрастанию |
Задача 1. Дан непустой массив целых чисел. Найти его наибольший элемент. Начинать с нуля рискованно: если в массиве все числа отрицательные, ноль не будет его элементом и исказит ответ. Поэтому начальным максимумом станет значение из первой ячейки.
Ответ: наибольший элемент хранится в переменной максимума после завершения цикла. Если нужно узнать его позицию, при каждой замене максимума следует записывать индекс текущего элемента.
Задача 2. Дан массив оценок. Найти среднюю оценку и количество оценок не ниже заданного порога. Здесь нужны два независимых результата: сумма оценок и число тех, которые прошли проверку. Их можно получить за один проход, потому что оба вычисления используют очередной элемент массива.
Ответ: средняя оценка равна сумме всех оценок, делённой на их общее количество; счётчик показывает число оценок не ниже порога. Важно отличать общее число оценок для среднего от количества подходящих значений.
Задача 3. Упорядочить по возрастанию массив из n целых чисел методом выбора. На первом шаге ещё весь массив не упорядочен, поэтому минимум ищут среди всех элементов. На каждом следующем шаге начало неупорядоченной части сдвигается вправо.
Ответ: после выполнения шагов массив упорядочен по возрастанию. Важно менять местами элемент начала части именно с элементом по найденному индексу минимума, а не с самим значением индекса.
Инициализация максимума или минимума нулём может дать неверный результат, если все элементы массива имеют другой знак. Так начинают, потому что ноль кажется удобным нейтральным значением, но для сравнения он не обязательно подходит. Надёжнее взять первый элемент непустого массива и проверить на наборе чисел одного знака.
Ошибка в границе цикла возникает, когда первый элемент уже использовали для инициализации, но просмотр начинают с неверного индекса или заканчивают слишком рано. Причина обычно в том, что начальный индекс и условие продолжения выбирают независимо друг от друга. Проверьте, что каждый нужный элемент массива сравнивается ровно один раз, а последний индекс допустим.
Если перед циклом не обнулить сумму или счётчик, в результат попадут старые значения. Это случается, когда переменную повторно используют или забывают, что она могла сохраниться после предыдущих вычислений. Перед запуском мысленно проверьте её начальное значение: сумма и счётчик должны начинаться с нуля.
При сортировке можно найти минимум правильно, но обменять его не с тем элементом. Такая ошибка возникает, если перепутать индекс минимума, значение минимума и позицию начала неупорядоченной части. Проверьте, что переставляются два значения: по индексу найденного минимума и в первой позиции текущей части; после обмена минимум должен оказаться на своём месте.
Для понимания алгоритмов обработки нужны знания об устройстве массивов, индексах элементов и циклах с параметром: именно они позволяют последовательно перебрать данные. Такие алгоритмы применяются при анализе таблиц, например для поиска крайних значений или подсчёта записей, и при подготовке данных к поиску. Сравнение способов сортировки помогает перейти к оценке времени выполнения алгоритмов и изучению более эффективных методов упорядочивания.
Почему максимум нельзя всегда начинать с нуля?
Если все числа массива отрицательные, ноль окажется больше любого из них и не будет настоящим максимумом. Поэтому для непустого массива начальным кандидатом выбирают его первый элемент.
Как найти не только значение максимума, но и его индекс?
Нужно хранить две переменные: значение максимума и индекс, где оно найдено. Когда очередной элемент больше текущего максимума, обновляют обе переменные.
Чем переменная-счётчик отличается от переменной-накопителя суммы?
Счётчик хранит количество найденных элементов и при выполнении условия увеличивается на единицу. Накопитель суммы хранит сумму значений и на каждом шаге прибавляет очередной элемент.
Почему при вычислении среднего нужно знать количество элементов?
Среднее арифметическое — это сумма всех элементов, разделённая на их количество. Без количества нельзя определить, на сколько частей делить сумму.
Как сортировка выбором упорядочивает массив?
На каждом шаге алгоритм ищет минимальный элемент в ещё не упорядоченной части массива. Затем он меняет этот элемент местами с первым элементом этой части, постепенно увеличивая упорядоченный участок.
§ 63. Алгоритмы обработки массивов
