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