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

Некоторые алгоритмы

обработки массивов

1 Суммирование двух массивов одинакового размера

2 Суммирование элементов массива

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

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

5 Инвертирование массива

6 Формирование массива из элементов другого массива, удовлетворяющих заданному условию

7 Поиск максимального (минимального) элемента в массиве с запоминанием его положения в массиве

8 Поиск заданного элемента в массиве

9 Циклический сдвиг элементов массива

10 Упорядочение Массива

1 Суммирование двух массивов одинакового размера

Задано:массивы A =(a1,a2,...,an) , B =(b1,b2,...,bn).

Сформировать: массив C =(c1,c2,...,cn) , где Сi = Ai+Bi; i=1,2,...,n.

Задача сводится к организации цикла по i и вычислению Ci=Ai+Bi при каждом значении i от 1 до n.

Исходные данные:

N- размер массива;

A, B - массивы слагаемые размером N;

Результат: массив С - размером N;

Вспомогательные переменные: I - индекс - управляющая переменная цикла.

Procedure SUM_MAS (n : integer; A,B :mas; var C : mas);

{ где mas должен быть описан в главной программе в разделе описания типов , например так :

type mas = array[1..100 ] of real ;

тогда это будет процедура для суммирования двух одномерных массивов размером не более 100 элементов }

begin

for i := 1 to n do C[i] := A[i]+B[i];

end;

2 Суммирование элементов массива

Задано: массив P = (P1,P2,...,Pn) .

Определить: сумму элементов массива.

Исходные данные:

N - размер массива;

P - массив размером N;

Результат: S - сумма элементов;

Вспомогательная переменная:I - индекс - управляющая переменная цикла.

Procedure SUMMA (n : integer; A :mas; var S : real );

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

begin S:=0; { обнуление переменной под сумму }

for i := 1 to n do S := S+P[i]

end;

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

Задано: массив P = (P1,P2,...,Pn); T - заданное число.

Определить: сколько элементов удовлетворяет заданному условию, например Pi > T .

Исходные данные:

N - размер массива;

P - массив размером N;

T - заданное значение, с которым сравниваются элементы массива.

Результат: K - число элементов массива P, удовлетворяющих условию.

Вспомогательная переменная: I- индекс - управляющая переменная цикла.

Procedure USLOVIE ( n : integer; P :mas; T: real; var K : integer);

{процедура определения числа элементов, удовлетворяющих условию}

begin

k := 0; { обнуление переменной под счетчик чисел }

for i := 1 to n do if P[ i ] > T then k := k+1

end;

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

Задано: массив P = (P1,P2,...,Pn); T - заданное число.

Определить: сумму элементов массива P, удовлетворяющих заданному условию, например Pi > T .

Исходные данные:

N - размер массива;

P - массив размером N;

T - заданное значение, с которым сравниваются элементы массива;

Результат: S - сумма элементов массива P, удовлетворяющих условию.

Вспомогательная переменная : I - индекс - управляющая переменная цикла.

Procedure SUM_USLOV ( n : integer; P :mas; T: real; var S : real);

{процедура определения суммы элементов, удовлетворяющих условию}

begin S := 0; {обнуление переменной под сумму элементов}

for i := 1 to n do if P [ i ] > T then S := S+1

end;

5 Инвертирование массива

Задано: массив C=(c1,c2,...,cn).

Требуется: изменить порядок следования элементов массива C на обратный, используя одну вспомогательную переменную.

Исходные данные:

N - размер массива;

C - массив размером N;

Результат:

C - инвертированный массив;

Вспомогательные переменные:

I -индекс, управляющая переменная цикла;

M=n/2 - вычисляется до входа в цикл для уменьшения объема вычислений; P - используется при перестановке двух элементов массива.

Procedure INVER_MAS ( n : integer; C :mas; var C : mas);

Var m : integer; p : real; { локальные переменные }

begin m := n div 2 ; { целочисленное деление }

for i := 1 to m do

begin p := C[ i ]; C[i] := C[N-i+1]; C[N-i+1] := p end;

end;

6 Формирование массива из элементов другого массива, удовлетворяющих заданному условию

Задано: массив A=(a1,a2,...,an), T - заданное число.

Сформировать: массив B=(b1,b2,...,bn), состоящий из элементов массива, удовлетворяющих условию Ai>T.

Заметим, т .к. индексы элементов массивов A и B не совпадают (не все элементы массива Ai>T), то для обозначения индексов массива B должна быть предусмотрена другая переменная.

Исходные данные:

N - размер массива;

A - массив размером N;

T - заданное значение;

Результат:

B - массив размером не больше N;

Y - число элементов массива B;

Вспомогательная переменная: I - индекс - управляющая переменная цикла.

Procedure MAS_NEW (n:integer;T:real;A:mas;var B: mas; var Y: byte);

{ где mas должен быть описан в главной программе в разделе описания типов , например так :

type mas = array[1..100 ] of real ;

тогда это будет процедура для суммирования двух одномерных массивов размером не более 100 элементов }

{ процедура включения в новый массив элементов, удовлетворяющих условию }

begin Y := 0; { обнуление ячейки под счетчик элементов массива В }

for i := 1 to n do

If A[ i ] > T then begin Y := Y+1; B[ Y ] := A[ i ] end;

end;

7 Поиск максимального (минимального) элемента в массиве с запоминанием его положения в массиве

Задано:массив A=(a1,a2,...,an).

Найти: max (min) элемент массива A и его индекс.

Исходные данные:

N - размер массива;

A - массив размером N;

Результат:

A_max максимальный элемент массива A;

K - его индекс.

Вспомогательная переменная: I - индекс управляющая переменная цикла.

Procedure MAX_MAS1(n:integer; A :mas; var A_max :real; var K byte);

{ процедура поиска максимального элемента массива и его номера }

begin A_max := A[1]; K := 1;

for i := 2 to n do

If A_max<A[i] then begin K := i; A_max := A[i] end;

end;

Примечание: Если в массиве несколько max элементов (имеют одно и то же значение), то в K будет запоминаться первый из них, а чтобы запоминался индекс последнего нужно заменить условие на A_max<=A(I). Поиск минимального элемента аналогичная процедура.

8 Поиск заданного элемента в массиве

Задано: массив P=(p1,p2,...pn); элемент L (массив может быть как числовым так и символьным.

Найти: Есть ли в массиве P, элемент равный L. Результат присвоить символьной переменной.

Исходные данные:

N - размер массива;

P - массив размером N;

L - значение, которое ищется в массиве;

Результат: R - имеет значение "элемент, равный L есть" или "элемента, равного L нет" в зависимости от результата поиска;

Вспомогательная переменная: I - индекс управляющая переменная цикла.

Procedure POISK ( n:integer; P :mas; L :integer; var R :string);

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

Label m ;

begin

R :=" элемента равного L в массиве нет " ;

for i := 1 to n do

If P[i] = L then

begin R := " элемент , равный L есть "; Goto m end;

m: end;

Примечание. Если элемент, равный L, найден, то чтобы завершить цикл используется оператор безусловного перехода Goto m , где локальная метка m обязательно должна быть описана в процедуре.

9 Циклический сдвиг элементов массива

Задано: массив A=(a1,a2,...,an); N - размер массива; m – число позиций, на которые надо сдвинуть массив вправо ( влево ).

Сформировать: сдвинутый массив, например : исходный массив A=(a1,a2,a3,a4,a5,), а сдвинутый вправо на 2 позиции A=(a4,a5,a1,a2,a3).

Исходные данные:

N - размер массива;

A - массив размером N;

M - число позиций сдвига;

Результат: A - массив, циклически сдвинутый на M позиций вправо;

Вспомогательные переменные:

I - индекс - управляющая переменная цикла;

P - массив размером не менее N (вариант 1) для временного хранения "хвоста" массива;

P - переменная (вариант 2) для временного хранения элемента массива A; Y - управляющая переменная внутреннего цикла (вариант 2).

Вариант 1: "хвост" массива пересылается во вспомогательный массив, остальные элементы перемещаются вправо на M позиций. Порядок перемещения обратный, прямой привел бы к искажениям массива. Далее в первые элементы массива A пересылаются элементы вспомогательного массива. Эта процедура повторяется Мраз.

Procedure SDVIG_VAR1( n, m : integer; A : mas; var A : mas ;);

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

Var P : mas;

begin

for i := 1 to m do

P[ i ] := A [ n - m + i ];

for i := n - m downto 1 do

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

for i := 1 to m do A [ i ] := P [ i ] ;

end;

Вариант 2. Во вспомогательную переменную каждый раз пересылается последний элемент массива А, затем все элементы сдвигаются вправо на одну позицию (в обратном порядке) и на место первого элемента помещается содержимое вспомогательной переменной.

Procedure SDVIG_VAR2( n, m : integer; A : mas; var A : mas ;);

{ где mas должен быть описан в главной программе, см 7.1.}

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

Var P : real;

begin

for i := 1 to m do

begin P := A [ n ] ;

for y := n downto 2 do A[ y ] := A [ y-1] ;

A [1] := P ;

end

end;

При сравнении двух вариантов сдвига элементов массива на m позиций вправо можно отметить, что в варианте 1 потребуется больше памяти, а в варианте 2 - больше затрат времени.

10 Упорядочение Массива

Задано: массив А=(a1,a2,...an).

Требуется: расположить элементы массива А в порядке возрастания (убывания).

Существует много различных методов. Рассмотрим один из них, основанный на поиске минимального (максимального) элемента массива или его части.

Исходные данные:

N - размер массива;

A - массив размером N;

Результат:

А - массив, упорядоченный по возрастанию;

Вспомогательные переменные:

P - переменная для хранения промежуточного значения минимального элемента;

K - индекс минимального элемента;

I - индекс элемента упорядоченного массива (управляющая переменная внешнего цикла);

J - индекс элемента части массива, в котором ищется минимальный элемент (управляющая переменная внутреннего цикла).

Вначале найдем минимальный элемент массива и поменяем его местами с первым элементом, затем определим минимальный элемент из оставшихся элементов (кроме первого) и поменяем его местами со вторым элементом.

Procedure SORTIROV (n : integer; A :mas; var A : mas; var K : integer);

{ где mas должен быть описан в главной программе, см 7.1.}

{ процедура упорядочивания одномерного массива по возрастанию}

Var p : real ; i, j : integer ; { локальные переменные }

begin

for i := 1 to n - 1 do

begin P := A [ i ] ; k := i ;

for j := i + 1 to n do

If A [ i ] < P then begin P := A [ i ] ; k := j end;

A [ k ] := A [ i ] ; A [ i ] := P

end

end;

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

Представленные выше несколько типовых алгоритмов работы с массивами, так же как и более сложные фрагменты программ, можно легко проверить (так называемая, безмашинная отладка программ, или "прокрутка"). Для этого задаются конкретными значениями исходных данных и выполняют операторы процедур или программ шаг за шагом, фиксируя значение переменных после каждого выполнимого оператора.

Типовые алгоритмы оформлены в виде процедур, которые при необходимости можно использовать при программировании конкретных задач, связанных с обработкой массивов. Ниже рассмотрим несколько примеров обработки массивов.

Пример 1.

Упорядочить по возрастанию одномерный массив A размером N.

program primer_1;

const N = 5;

var A : array [ 1..N ] of real;

p : real;

i, j, k, g : integer;

begin

writeln('упорядочение массива по возрастанию');

writeln('введите элементы массива через пробел в конце ENTER ');

for i := 1 to N do read (A [ i ] ); writeln;

{ второй вариант ввода одномерного массива }

{ for i := 1 to N do

begin write (' введите A [', i:2 ,' ] = ' ) ; readln ( A[i] ); end;}

{ для упорядочивания массива задействуем промежуточные

переменные p - для запоминания минимального значения массива,

k - для запоминания его местонахождения }

for i := 1 to N - 1 do

begin

p := a [ i ] ; k := i ;

for j := i + 1 to N do

if A [ j ] < p then begin p := A[ j ]; k := j ; end;

A [ k ] := A [ i ] ; A [ i ] := p ;

end;

for i := 1 to N do

begin write( ' A [ i ] ='); writeln( A [ i ] : 8 : 5 ); end;

end.

В следующем примере представлен более удобный вариант оформления программ, где самостоятельные части работы вынесены в процедуры. Главная программа ( вызывающая ) получается тогда очень короткой, а отладка таких программ значительно проще.

Пример 2.

Программа для умножения сцепленных матриц A = ?aik? размера m x n и B = ?bik? размера r x s ( матрицы называются сцепленными, если число столбцов первой матрицы равно числу строк второй ). Произведение AB двух сцепленных матриц есть матрица C=?cik? размера m x s, где cik = ? aijbjk.

program primer_2;

uses CRT;

const n = 3; m = 2; r = 3; s = 3;

type massiv = array [1..10,1..10] of real;

var a,b,c : massiv;

sum : real;

i, j, k : integer;

ch : char;

procedure VVOD_2(n,m:integer;ch:char;var a:massiv);

{ процедура ввода двумерной матрицы построчно}

begin

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

for i := 1 to n do

begin

for j := 1 to m do read ( A [ i , j ] );

writeln; { для перехода на новую строку}

end;

end;

procedure PRINT_MAS(n,m:integer;ch:char;a:massiv);

{ печать матрицы построчно }

{ n,m - размер матрицы }

{ ch - название матрицы , для обозначения при выводе }

begin

writeln(' Элементы массива ',ch);

for i := 1 to n do

begin

for j := 1 to m do write(a [ i , j ] : 8 : 2);

writeln; { для перехода на новую строку }

end;

end;

begin {---------- main ------------------}

{ В рассматриваемом примере размеры матриц A, B, C заданы с помощью

констант. Заметим, что лучше это сделать вводом с клавиатуры или чтени-

ем данных из файла }

VVOD_2(m,n,'A',a); { вызов процедуры VVOD_2 для ввода матрицы A }

VVOD_2(r,s,'B',b); { вызов процедуры VVOD_2 для ввода матрицы B }

{ формирование матрицы C равной произведению матриц A*B }

for i := 1 to m do

for k := 1 to s do

begin

sum := 0; { обнуление переменной для вычисления суммы }

for j := 1 to N do sum := sum + a[ i , j ] * b [ j , k ] ;

c[ i , k ] := sum;

end;

{ вывод на экран исходных данных и результатов }

PRINT_MAS(m,n,'A',a); { m,n - размерыматрицы A }

PRINT_MAS(r,s,'B',b); { r,s - размерыматрицы B }

PRINT_MAS(m,s,'C',c); { m,s - размерыматрицы C }

end.