Понятие массива (стр. 5 )

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

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. Ставим его на второе место.

И так далее 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;

…