Типовые алгоритмы обработки массивов

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

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

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

Массив

Это структура данных, которая хранит несколько значений одного типа под одним именем, а каждое значение доступно по номеру (индексу).

Индекс элемента

Это номер элемента в массиве, начиная с нуля (в большинстве языков программирования).

Перебор элементов

Это последовательное обращение к каждому элементу массива с помощью цикла.

Поиск элемента

Это алгоритм, который проверяет каждый элемент массива на соответствие заданному условию и возвращает индекс или значение найденного элемента.

Подсчёт по условию

Это алгоритм, который считает, сколько элементов массива удовлетворяют заданному условию.

Сортировка

Это процесс упорядочивания элементов массива по возрастанию или убыванию.

Сумма элементов

Это результат сложения всех элементов массива, который вычисляется накоплением в переменной.

• Индексация элементов массива в большинстве языков (Python, C++, Java) начинается с нуля: первый элемент имеет индекс 0, второй — 1 и так далее.
• Для перебора массива обычно используется цикл for: for i in range(len(arr)): — в Python, или for (int i = 0; i < n; i++) — в C++.
• Поиск максимального/минимального элемента: начальное значение переменной max/min берётся как первый элемент массива, затем сравнивается с остальными.
• Сумма элементов вычисляется так: sum = 0; for i in range(n): sum += arr[i].
• Подсчёт количества элементов по условию: count = 0; for i in range(n): if arr[i] > 10: count += 1.
• Замена элемента: arr[i] = новое_значение — присваивание нового значения элементу с индексом i.
• Сортировка пузырьком — простейший алгоритм сортировки: многократно проходит по массиву, сравнивая соседние элементы и меняя их местами, если они стоят в неправильном порядке.
• Сортировка выбором — на каждом шаге находит минимальный элемент в неотсортированной части и ставит его в начало.

1. Пример 1случай

   Список оценок ученика за четверть

   Пояснение

   • это массив. Чтобы найти средний балл, нужно вычислить сумму всех оценок и разделить на их количество
2. Пример 2случай
   • Температура воздуха за неделю хранится в массиве из 7 чисел
   • Чтобы узнать, сколько дней было холоднее 0°, нужно перебрать массив и посчитать элементы, меньшие нуля
3. Пример 3случай

   В игре «Сапёр» поле

   Пояснение

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

• Сортировка пузырьком — один из самых неэффективных алгоритмов сортировки, но его часто изучают первым из-за простоты понимания.
• В реальных программах для сортировки используют встроенные функции, например, sort() в Python, которые работают гораздо быстрее, чем пузырёк.
• Массивы используются в компьютерной графике для хранения пикселей изображения: каждый пиксель — это элемент массива.

• Алгоритмы и исполнители
• Основы программирования на Python
• Циклы и ветвления
• Строки и списки
• Двумерные массивы