Проверка соседних элементов массива

Задача 18: Подсчитать, сколько в массиве элементов, равных 0, справа и слева от которых стоят отрицательные элементы.

Фрагмент программы:

…

k:=0; {количество таких элементов}

{проходим по всем элементам массива A}

{начинаем не с первого, а со второго, потому что у первого элемента

нет стоящего слева от него}

{заканчиваем на n-1 элементе, а не на n, потому что у последнего

n-го элемента нет элемента, стоящего от него справа}

for i:=2 to n-1 do

{если i-ый элемент равен 0 и элемент слева от него и

элемент справа от него отрицательные}

if (A[i]=0) and (A[i-1]<0) and (A[i+1]<0)

then Inc(k); {тогда увеличиваем счетчик}

…

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

Фрагмент программы:

…

k:=0; {k - номер искомого элемента}

i:=2; {начинаем со второго элемента}

while (i<=n-1) and (k=0) do {пока не нашли искомый элемент

и не просмотрели все элементы массива}

begin

{если элемент тот, что надо, то запоминаем его индекс}

if (A[i-1]>0) and (A[i+1]>0) then k:=i;

Inc(i); {переходим к следующему элементу}

end;

{выводим позицию искомого элемента}

if k=0

then writeln('искомых элементов в массиве нет')

else writeln('искомый элемент занимает позицию ',k);

Сортировка массива и работа с отсортированным массивом

Задача 20: Отсортировать массив по возрастанию. Массив A является отсортированным (упорядоченным) по возрастанию, если для всех i из интервала [1..n-1] выполняется условие A[i]<=A[i+1]. Существует множество методов сортировки, мы же воспользуемся один из самых простых - метод сортировки выбором (поиском минимального).

Суть этого метода сортировки заключается в следующем:

1. В массиве находим минимальный элемент.

2. Меняем минимальный элемент с первым.

3. В усеченном (исключая первый элемент) массиве находим

минимальный элемент.

4. Ставим 080 аu1077 его на второе место.

И так далее n-1 раз.

Пример:

Массив A, исходное состояние 1 3 0 9 2

Процесс сортировки

0: 1 3 0 9 2 min=a[3]=0 Переставляем a[1]<->a[3]

1: 0|3 1 9 2 min=a[3]=1 Переставляем a[2]<->a[3]

2: 0 1|3 9 2 min=a[5]=2 Переставляем a[3]<->a[5]

3: 0 1 2|9 3 min=a[5]=3 Переставляем a[4]<->a[5]

4: 0 1 2 3 9 Готово

Здесь знак | отделяет уже отсортированную часть массива от еще не

отсортированной.

На Turbo Pascal этот алгоритм будет выглядеть следующим образом:

Var {дополнительные переменные}

buf: integer; {через buf будем менять значения двух элементов массива}

imin:IndexEl; {индекс минимального элемента неотсортированной части массива}

…

Begin

…

{n-1 раз ищем минимальный элемент массива}

for i:=1 to n-1 do

begin

{Ищем минимальный элемент в несортированной части массива (от i-го элемента)}

imin:=i; {imin - это индекс минимального элемента массива}

for j:=i+1 to n do

if A[j]<A[imin] then imin:=j;

{переставляем i-ый и imin-ый элементы}

buf:=A[i];

A[i]:=A[imin];

A[imin]:=buf;

End;

…

Задача 21. Вставить в упорядоченный по возрастанию массив новый элемент таким образом,

чтобы сохранилась упорядоченность.

Алгоритм решения задачи следующий:

1. Ищем в массиве тот элемент, который больше вставляемого, – для

этого последовательно просматриваем все элементы, начиная с первого.

2. Увеличиваем длину массива на 1.

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

4. На освободившуюся позицию вставляется искомый элемент.

Замечание: если все элементы массива меньше вставлямого, то новый элемент надо вставить в конец массива. Если все элементы массива больше вставляемого, то новый элемент надо вставить в начало массива.

Пример: Надо вставить 5 в массив A: 3 4 7 9

1. Ищем элемент, больший вставляемого. Это элемент A[3]=7.

2. Увеличиваем длину массива на 1.

Получаем массив A: 3 4 7 9 X

3. Сдвигаем элементы, начиная с 3-го, вправо.

Получаем массив A: 3 4 7 7 9

4. В элемент A[3] заносим 5.

Получаем массив: 3 4 5 7 9

Фрагмент программы, реализующей данный алгоритм:

… {

считываем число, которое надо вставить в

массив}

read(g);

{1. Ищем элемент больше вставляемого }

k:=1; {k – индекс сравниваемого элемента}

while (k<=n) and (g>=a[k]) do {если k не вышла за границу n,

и вставляемый элемент меньше или равен A[k]}

k:=k+1; {то переходим к следующему элементу}

{2. Увеличиваем длину массива на 1}

n:=n+1;

{3. Сдвигаем элементы начиная с k-го вправо}

for i:=n downto k+1 do

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

{4. В A[k] заносим g}

a[k]:=g;

…

2 Варианты заданий