5 Типовые задачи обработки массивов

Все виды задач обработки массивов сводятся к сочетаниям циклических и разветвляющихся вычислительных процессов и представляют собой разветвления в циклах или циклы в разветвлениях.

5.1 Задачи выборок

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

Пример 5.1. Дан массив mz месячных заработков сотрудников предприятия (i=1,2,...n). Пусть p – процентная ставка подоходного налога, который вычитается из суммы заработка :

при mz < z₁ p = p₁ ;

при z₁ m z < z₂ p = p₂ ;

при mz z ₂ p = p₃ .

Рассчитать сумму подоходного налога sn и сумму причитающейся получки sp каждого сотрудника.

Задача, очевидно, сводится к просмотру всего массива заработков и выбору из него сумм, попадающих в пределы : < z1 ; от z1 до z2 ; > z2 , после чего суммы налогов и получки вычисляются по формулам

sn = mz * p/100 и sp = mz – sn .

где p принимает значения p₁ , p₂ , p₃ в зависимости от величины mz .

Соответствующий фрагмент программы в предположении, что массив mz и константы n, z₁ , z₂ , z₃ , p₁ , p₂ , p₃ введены, может иметь вид

for i:=1 to n do

begin

if mz[i]<z1 then p:=p1;

if mz[i]>=z1 and mz[i]<z2 then p:=p2;

if mz[i]>=z2 then p:=p3;

sn := mz[i]*p div 100;

sp :=mz[i] – sn;

write(i:2,' Заработок ',mz[i]:6,' Налог ',sn:6,' Получка ',sp:6);

end;

Аналогично выполняется и выборка элементов двумерных массивов.

Пример 5.2. В двумерном массиве p размером 6 8 выбрать все отрицательные числа, вывести их и подсчитать их общее количество.

Если искомое количество отрицательных элементов обозначить k, то соответствующий фрагмент программы может иметь вид :

k:=0;

for i:=1 to 6 do

begin

for j:=1 to 8 do

begin

if p[i,j]<0 then

begin

k:=k+1;

write(p[i,j]);

end;

end;

end;

write(' Число отрицательных элементов k=',k);

5.2 Преобразование одних массивов в другие

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

Пример 5.3. Пусть rsb_i – рейтинговая сумма балов i–го студента за 1–й этап обучения (i=1..n).

Студенты, набравшие сумму балов, не менее некоторой контрольной ks, образуют элитную группу и могут быть переведены на 2–й этап обучения. Допустим требуется проанализировать средние показатели успеваемости элитной и остальной групп по отдельности. Это означает, что общий массив rsb необходимо разделить на 2 массива rse и rso, отобрав в первый из них суммы балов  ks, а во второй – остальные. Задача заключается в просмотре всех элементов исходного массива rsb и проверке каждого из них на условие rsb_i  ks. Каждому элементу rsb , который удовлетворяет этому условию, присваивается очередной порядковый номер j и он переименовывается в элемент массива rse под этим номером. Каждому элементу, который этому условию не удовлетворяет, присваивается очередной номер k и он переименовывается в соответствующий элемент массива rso. Некоторую особенность в этой и аналогичных задачах представляет описание массивов. Объем исходного массива rsb в данном случае известен (n–элементов) а формируемых массивов rse и rso – нет, поэтому в описании всех трех массивов необходимо предусмотреть одинаковое максимально возможное число элементов n, которое обеспечивает нормальную работу программы в любом крайнем случае как в том, когда в элитную группу войдут все студенты, так и в том, когда в ней не окажется ни одного. Фрагмент программы, реализующий поставленную задачу (для конкретных условий n=150 и ks=4800), в котором ввод исходного массива rsb обозначен лишь условно может иметь вид :

program Rejting;

Const n=150; ks=4800;

Type mas=array[1..n] of integer;

Var rsb,rse,rso:mas;i,j,k:integer;

begin

{ ввод массива rsb }

j:=0;

k:=0;

for i:=1 to n do

begin

if rsb[i]>=ks then

begin

j:=j+1;

rse[j]:=rsb[i];

end

else

begin

k:=k+1;

rso[k]:=rsb[i];

end;

end;

writeln(' Элитный массив ');

for i:=1 to j do write(rse[i]:8); writeln;

writeln(' Остальной массив');

for i:=1 to k do write(rso[i]:8);

end.

Рассмотрим аналогичный пример с двумерным массивом.

Пример 5.4. В матрице А(10х10) выбрать числа больше 8 и меньше 2 и сформировать из них два одномерных массива – вектора B и C.

Ниже приводится фрагмент программы в котором исходная пробная матрица формируется с помощью функции Random (см. раздел 2.2).Единственное, что требует пояснения в данном случае. это заказ количества элементов в описании формируемых массивов B и C. Оно, очевидно, должно указываться как и в предыдущем примере с "запасом", на случай, если все элементы матрицы попадут в один или другой массив B или C, т.е. должно быть равно 100.

program MatrVec;

Type vec=array[1..100] of real;

Var a:array[1..10,1..10] of real;

b,c:vec; i,j,k,l:integer;

begin

writeln(' Исходная матрица ');

for i:=1 to 10 do

begin

for j:=1 to 10 do

begin

a[i,j]:=9.999*Random;

write(a[i,j]:5:2);

end;

writeln;

end;

k:=0; i:=0;

for i:=1 to 10 do

begin

for j:=1 to 10 do

begin

if a[i,j]>8 then

begin

k:=k+1;

b[k]:=a[i,j];

end

else if a[i,j]<2 then

begin

l:=l+1;

c[l]:=a[i,j];

end;

end;

end;

writeln(' Вектор B ');

for i:=1 to k do write(b[i]:5:2);

writeln(' Вектор C');

for i:=1 to l do write(c[i]:5:2);

end.

К задачам преобразования массивов относятся и задачи слияния нескольких однородных массивов в один.

Пример 5.5. Пусть, например, в эксперименте выполнено 3 серии измерений некоторой величины X. При этом в первой серии выполнено 25 измерений, во второй 30 и в третьей 15. Иными словами, получено 3 массива данных : X1 (i=1..25); X2 (i=1..30) и X3 (i=1..15). Требуется объединить три массива в один общий массив X, расположив в нем сначала элементы массива X1, затем X2, затем X3 и обеспечив общую сквозную нумерацию элементов массива X (i=1..70).

В этом случае, очевидно, 25 первых элементов массива X совпадут с одноименными элементами массива X1, то есть перенумеровка элементов массива X1 в элементы массива X будет выполняться по формуле

X_i = X1_i (i=1..25).

Затем первый элемент массива X2 должен стать 26–м элементом массива X и т.д. То есть каждый i–й элемент массива X2 должен переименоваться в 25+i –й элемент массива X. Иными словами, перенумеровка элементов массива X2 в элементы массива X должна выполняться по формуле

X_25+i= X2_i (i=1..30).

В конце этого цикла очевидно получим X₅₅ = X2₃₀. Далее, первый элемент массива X3 должен стать 56–м элементом массива X и, рассуждая аналогично предыдущему, получим, что перенумеровка элементов массива X3 в элементы массива X должна выполняться по формуле

X_55+i = X3_i (i=1..15).

Соответствующий фрагмент программы слияния массивов, реализующий данный алгоритм представлен ниже. Отметим, что в данном случае описания всех четырех массивов целесообразно выполнить в разделе Type, заказав для каждого из них размер наибольшего, а именно массива X, включающего суммарное количество 70 элементов.

program SliMas;

Type vec=array[1..70] of real;

Var X1,X2,X3,X:vec; i:integer;

begin

begin

{ ввод массивов X1,X2,X3 }

end;

begin

for i:=1 to 25 do X[i]:=X1[i];

for i:=1 to 30 do X[25+i]:=X2[i];

for i:=1 to 15 do X[55+i]:=X3[i];

end;

{ продолжение программы }