Алгоритмы обработки массивов

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

Базовые алгоритмы: Вычисление суммы элементов, Подсчёт количества элементов массива, удовлетворяющих заданному условию, Нахождение максимального (минимального) элемента массива и его номера.

Алгоритмы поиска: Прямой поиск, Двоичный (бинарный) поиск.

Алгоритмы сортировки массивов: Метод вставки, Метод выбора, Метод «пузырька»

Вычисление суммы эл-тов: sum=0; (for i=0; i< n; i++) sum=sum+a[i].

Подсчет кол-ва эл-тов крат 5: kol: =0; for i: =1 to n do if a[i] div 5 = a[i]/5 then kol: =kol+1;

Нахождение max эл-та и его номера. Пусть этот элемент единственный:

max: =x[1]; ind_max: =1; for i: =1 to n do if x[i]> max then begin max: =x[i]; ind_max: =i; end;

Прямой поиск: Элементы массива просматриваются поочередно, каждый из них сравнивается с тем значением, которое необходимо найти.

var flag: Boolean; flag: =false; for i: =1 to n do if x[i]< 0 then begin flag: =true; break; end;

if flag then writeln(‘Есть хотя бы 1 отриц.элемент’) else writeln(‘Нет ни одного отриц.элемента’); end.

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

Алгоритм сортировки вставкой: массив делят на две части – отсортированную и неотсортированную. Элементы из неотсортированной части последовательно выбираются и вставляются в отсортированную часть так, чтобы не нарушить в ней упорядоченности. В начале в качестве отсортированного массива берут первый элемент. Всего требуется n-1 подход.

Пузырьковая сортировка: слева на право поочередно сравниваются два соседних элемента, если их взаиморасположение не соответствует заданному условию упорядоченности, то они меняются местами. Потом берут след два элемента. На последней позиции будет находиться max элемент. Второй подход выполняется до n-1 элемента. Всего требуется n-1 подход. For i: =n-1 downto 1 do for j: =1 to i do if x[j]> x[j+1] then

Begin tmp: =x[j]; x[j]: =x[j+1]; x[j+1]: =tmp; end.

Алгоритм сортировки выбором:

1)установить номер наименьшего элемента массива

2) поменять местами наименьший и первый элемент массива

3) не принимая во внимание первый элемент выполнить п1-2 над оставшимися элементами

4) п3 выполнять пока остаток массива не сократиться до одного элемента. n-1 подход.

For i: =1 to n-1 do

Begin

Min: =x[i]; ind_min: =i;

For j: =i+1 to n do

If x[j]< min then begin min: =x[j]; ind_min: =j;

End;

tmp: =x[i]; x[i]: =x[indmin]; x[indmin]: =tmp; end;

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

void main ()

{

srand ((unsigned) time (NULL));

const int n = 20; // число элементов массива

double x[n]; // объявлен исходный массив

double *r[n]; // объявлен массив указателей

double *tmp; // временная переменная для обмена

int i, j; // параметры цикла

/* Задание значений элементов исходного массива и распечатка их на экране (a и b – границы интервала значений элементов массива). Здесь же массив r заполняется адресами соответствующих элементов массива x: */ int a = 0, b = 10;

for (i = 0; i < n; i++)

{x[i] = (double) rand () /RAND_MAX* (b-a+1) + a; printf (“%4.21f”, x[i]); r[i] = x + i; };

/* Сортировка массива r по возрастанию значений элементов массива x: */

for (i = n -1; i > 0; i--) for (j = 0; j < i; j++) if (*r[j] > *r[j+1]) { tmp = r[j]; r[j] = r[j+1]; r[j+1] = tmp; }