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

К стандартным типам задач на обработку массивов данных можно отнести следующие задачи:

-  нахождение суммы элементов массива;

-   нахождение количества элементов массива, удовлетворяющих определенным условиям;

-   задачи на поиск элементов массива, удовлетворяющих некоторым заданным условиям;

-   преобразование массивов путем замены и перестановки их элементов;

-  упорядочение элементов массива и др.

Рассмотрим некоторые типовые алгоритмы обработки массивов данных.

3.3.1 Нахождение суммы элементов массива

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

Пример 1. Найти сумму четных элементов заданного одномерного массива из 10 целых чисел.

PROGRAM Sum_mas;

Type Mas=array[1..10] of integer;

Var a: Mas;

i,s: integer;

begin

s:=0;

for i:=1 to 10 do

begin

writeln('Введите элемент массива');

readln(a[i]);

if a[i] mod 2=0 then s:=s+a[i] {Проверка четности элемента и накопление суммы}

end;

writeln('Сумма s=', s)

end.

3.3.2 Поиск данных в массивах

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

Пример 2. Задан одномерный массив из 7 действительных элементов. Найти наибольший элемент данного массива.

PROGRAM Max_mas;

Type Mas=array[1..7] of real;

Var a: Mas;

max : real;

i: integer;

begin

for i:=1 to 7 do

begin

writeln(‘Введите элемент а[‘,i,’]’);

readln(a[i])

end;

max:=a[1];

for i:=2 to 7 do

if max<a[i] then max:=a[i];

writeln(‘max=’, max)

end.

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

3.3.3 Сортировка массивов данных

Сортировкой массива называют упорядочение его элементов в соответствии с определенными правилами (как правило, по возрастанию или убыванию элементов).

Рассмотрим следующие алгоритмы сортировки массивов данных: линейная сортировка (сортировка отбором) и сортировка методом «пузырька».

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

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