Методическая разработка по теме: «Обработка массивов» (стр. 3 )

  …

  Begin

  ...

  max:=A[1];

  min:=A[1];

  for i:=2 to n do

  if A[i]>max then max:=A[i]

  else if A[i]<min then min:=A[i];

  …

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

Задача 8: Подсчитать, сколько раз в массиве встречается элемент, равный 10.

Задача решается по следующему алгоритму:

1. Количество нужных элементов k=0.

2. Проходим по всем элементам массива,

3. И если очередной элемент массива равен 10,

4. Тогда увеличиваем k (количество элементов равных 10) на 1.

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

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

  k:integer; {количество элементов, равных 10}

  …

  Begin

  ...

  {1} k:=0;

  {2} for i:=1 to n do

  {3} if A[i]=10

  {4} then k:=k+1;

  …

Удаление элемента из массива

Задача 9: Удалить из массива 1-ый элемент.

Удаление элемента заключается в:

1. сдвиге элементов, стоящих правее удаляемого влево;

2. уменьшении количества элементов массива n на количество удаляемых элементов.

Сдвиг элементов выполняется так:

1. Начиная с удаляемого элемента, копируем содержимое элемента, стоящего правее в текущий элемент: A[i]:=A[i+1].

2. Переходим к следующему элементу вправо: i:=i+1.

3. Заканчиваем сдвиг, когда i=n-1, так как i+1 при i=n-1 равен n..

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

  …

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

  {вначале i:=1, потому что надо удалить 1-ый элемент}

  for i:=1 to n-1 do

  A[i]:=A[i+1];

  {2 - уменьшаем количество элементов в массиве}

  n:=n-1;

  …

Задача 10: Удалить из массива максимальный элемент массива.

Для этого надо:

1. Найти индекс максимального элемента.

2. Удалить элемент с найденным индексом.

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

  Var

  imax:IndexEl; {индекс максимального элемента}

  …

  Begin

  ...

  {1 - ищем индекс максимального элемента массива}

  imax:=1; {вначале imax указывает на первый элемент}

  {в цикле начиная со 2-го элемента}

  for i:=2 to n do

  {сравниваем i-ый элемент с максимальным на текущий момент времени, и если
  i-ый элемент больше максимального, то максимальным становится i-ый элемент}

  if A[i]>A[imax] then imax:=i;

  {2 - удаляем элемент массива с индексом imax}

  for i:=imax to n-1 do

  A[i]:=A[i+1];

  dec(n); {уменьшаем n на 1}

Замечание: в ТР имеются процедуры увеличения и уменьшения переменной целого типа.

  Inc - увеличение значения переменной.

Вид вызова	для целого X
Inc(x);	x:=x+1;
Inc(x, n);	x:=x+n;

где x - переменная целого типа; n - целочисленное выражение.

В первом случае переменной x присваивается следующее значение (например, x была равна 10, тогда после выполнения inc(x) x равна 11). Таким образом, можно сказать, что запись inc(x) эквивалентна записи x:=x+1. Можно также сказать, что запись inc(x, n) эквивалентна записи x:=x+n.

Dec – уменьшение значения переменной.

Вид вызова	для целого X
Dec(x);	x:=x-1;
Dec(x, n);	x:=x-n;

Вставка новых элементов в массив

Задача 11: В массив после максимального элемента вставить элемент, равный 0.

Пример исходного массива A: 1 2 5 1 0 1 2

  максимальный элемент A[3]=5

Массив после вставки элемента: 1 2 5 0 1 0 1 2

Алгоритм вставки элемента в массив:

1. Сдвинуть элементы от позиции вставляемого элемента в конец.

2. В позицию вставляемого элемента вписать нужное значение.

3. Количество элементов n увеличить на 1 .

Общий алгоритм программы следующий:

1 . Введем массив А.

2 . Найдем индекс max элемента.

3 . Вставим после max 0.

4 . Выведем получившийся массив.

Приведем полный текст программы:

{ Задание: В массив после максимального элемента вставить элемент, равный 0}

  Program InsertExample;

  Const

  maxN = 20; {максимально возможное количество элементов в массиве}

  Type

  IndexEll = 1 .. maxN; {индексы массива лежат в интервале от 1 до maxN}

  arrInt = array[interval] of integer; {массив целых чисел, содержащий до maxN эл-в}

  Var

  a:arrInt;  {массив}

  n:integer; {количество элементов в массиве}

  i:IndexEl; {переменная для сканирования массива}

  max: IndexEl; {номер max элемента массива}

  Begin

  {1 - ввод массива - генерируем случайные элементы}

  randomize;

  n:=random(6)+5; {n в интервале 5..10}

  for i:=1 to n do

  A[i]:=random(19)-9; {Генерируем элементы массива}

                          { каждый элемент имеет значение в интервале -9..9}

  {2 - ищем индекс max элемента}

  max:=1;

  for i:=2 to n do

  if A[i]>A[max] then max:=i;

  {3- вставляем 0 после максимального элемента}

  {сначала сдвигает “хвост” массива вправо}

  for i:=n downto max+1 do

  A[i+1]:=A[i];

  {заносим в следующий за максимальным элемент 0}

  A[max+1]:=0;

  {увеличиваем количество элементов массива}

  Inc(n);

  {4 - выводим массив}

  writeln('Массив А после вставки:');

  for i:=1 to n do

  write(A[i]:3);

  readln; {ждем нажатия клавиши Enter}

  End.

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

Замечание: данная программа таит в себе ошибку. Если n=20, то после вставки еще одного элемента n станет равной 21, и, скорее всего, программа повиснет (потому что элементов в массиве может быть НЕ БОЛЬШЕ 20). Следовательно, при вставке элементов необходимо следить, чтобы было n<=maxN.

Удаление нескольких элементов массива

Задача 12: Удалить из массива все элементы между k-м и z-м элементами.

Рассмотрим задачу на примере при количестве элементов в массиве n=10, k=3, z=7 (т. е. надо удалить элементы между третьим и седьмым).

Будем использовать переменную d - количество удаляемых элементов. Значение d можно вычислить по формуле: d = z - k – 1 ( в нашем примере получится d = 7 - 3 - 1 = 3).

Массив A до удаления:

a[1]        a[2]        a[3]        a[4]        a[5]        a[6]        a[7]        a[8]        a[9]        a[10]

  1          3          9          1          0          1          3          2          7          2

                  ^                          ^                  ^

                 a[k]                         a[z]                 a[n]

Массив A после удаления:

a[1]        a[2]        a[3]        a[4]        a[5]        a[6]        a[7]

  1          3          9          3  2          7          2

                  ^          ^          ^

                 a[k]        a[z]         a[n]

После удаления n стало меньше на d (в нашем примере на 3).

Общий алгоритм решения:

1 . Сдвинуть элементы вперед на d элементов, начиная с z-го.

2 . Уменьшить n на d.

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

  Var

  k: integer; {индекс элемента, после которого удаляем}

  z: integer; {индекс элемента, до которого удаляем}

  d: integer; {количество удаляемых элементов}

  …

  Begin

  …

  {вычисляем количество удаляемых элементов}

  d:=z-k-1;

  {1 - сдвигаем элементы}

  for i:=z to n do

  A[i-d]:=A[i];

  {2 - уменьшаем n на d}

  Dec(n, d);

  …

Задача 13: Из массива удалить все элементы, которые меньше 0.

Рассмотрим два решения этой задачи.

Алгоритм первого решения:

1. Просматриваем массив.

2. Если элемент<0, то удаляем его и n уменьшаем.

3. Если элемент>=0, то переходим к следующему.

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

  …

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

  i:=1;

  while i<=n do

  begin

  {проверяем, не нужно ли i-ый элемент удалять}

  if A[i]<0 then

  begin

  {если нужно – удаляем i-ый элемент}

for j:=i to n-1 do {сдвигаем}

  A[j]:=A[j+1];

  Dec(n);  {уменьшаем количество элементов}

  end

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

  end;