Контрольная работа № 2 Массивы

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

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

Рассмотрим некоторые типовые алгоритмы обработки массивов. Положим, что в декларативной части программы описаны следующие переменные: одномерные массивы А и В, переменные целого типа n, i и j и вспомогательные переменные типа элементов массива.

1. Инвертирование массива

Суть алгоритма, состоит в перестановке элементов массива в обратном порядке, т.е. меняет местами первый с последним элементом, второй с предпоследним элементом массива и т.д. Число перестановок равно n div 2, т.к. если менять местами элементы n раз, то все элементы массива встанут на свои места.

Реализация:

for i:=1 to n div 2 do

begin

{ Обменяем i-й и (n-i+1)-й элементы}

temp:=a[i];

a[i]:=a[n-i+1];

a[n-i+1]:=temp

end;

2. Циклический сдвиг элементов массива вправо (влево) на м позиций

При решении задач, в которых необходимо вставить элемент в массив используется циклический сдвиг элементов. В этом алгоритме сначала запоминаем последний элемент, если сдвиг будем делать вправо (первый элемент, если сдвиг влево). Затем сдвигаем элементы, т.е. на n место ставим n-1 элемент, на n-1 ставим n-2, и т.д. на 2-е место ставим 1-й элемент, тем самым как бы освободив первую позицию. Наконец, на первое место записываем последний элемент, который хранится во вспомогательной переменной. Подобные действия повторяются m раз, т.е. число раз, на которое необходимо осуществить сдвиг. Мы рассмотрели циклический сдвиг на m позиций вправо.

Реализация:

{Циклический сдвиг на m позиций вправо}

Writeln(‘ Введите число сдвигов’);

Readln( m);

For i:=1 to m do

begin

{Запоминаем последний элемент массива}

temp:=a[n];

{Сдвиг элементов массива на одну позицию вправо}

For j:= n downto 2 do a[j]:=a[j-1];

a[1]:= temp

end;

{Печать измененного массива}

For i:=1 to n do Writeln(‘a[‘, i, ‘]= ’, a[i]);

3. Поиск минимального (максимального) элемента

Данный алгоритм заключается в следующем: вначале запоминаем номер первого элемента массива, принимая его за минимальный (максимальный). Далее, начиная со второго, все элементы сравниваются с предполагаемым минимумом (максимумом) и если какой-нибудь из них меньше (больше) предполагаемого минимума (максимума), то запоминается номер этого элемента. Эти действия повторяются до тех пор, пока не закончатся элементы массива. Ниже написан фрагмент программы для поиска минимального элемента. Для реализации алгоритма введем еще один объект программы n_min, переменную, в которой будет храниться номер минимального элемента.

Реализация:

Writeln(‘ Введите количество элементов массива’);

Readln(n);

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

for i:=1 to n do read(a[i]);

{ Пусть первый элемент минимальный }

n_min:=1;

for i:=2 to n do

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

writeln('Минимальный элемент массива: ',a[n_min]);

writeln('Номер элемента: ',n_min);