Р= а + bх + сx² + dx³ + ех⁴ + fx⁵,

где a, b, c, d ,e, f — коэффициенты многочлена (объекты задачи арифметического типа). В алгоритме это переменные и их количество (шесть) определено в постановке задачи, т.е. к моменту разработки алгоритма.

Удобно такие разрозненные переменные объединить в совокупность —массив, именуя их затем общим именем (именем массива) и индексами (номерами в массиве). В рассматриваемом примере введем мас­сив А с шестью элементами (а₁—а₆):

Р = а₁ +а₂х + а₃ а² + а ₄х³ + а₅х⁴+ а ₆х⁵.

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

В задачах используются не только одномерные, но и многомерные мас­сивы, в частности двумерные. Для индексации элементов двумерного массива указываются два индекса — номер строки и номер столбца. Для наглядности такой массив представляется в виде матрицы, состоящей из m строк и n столбцов.

Например, оценки трех учеников по четырем предметам можно представить массивом Х из 3 строк и 4 столбцов:

Х₁₁ X₁₂ Х₁₃ X₁₄

X₂₁ X₂₂ Х₂₃ Х₂₄

Х₃₁ Х₃₂ Х₃₃ Х₃₄

При этом одномерные массивы часто называют векторами, а двумерные - матрицами.

Массиву дается имя и указывается его размер.

Итак, массив - это поименованный упорядоченный набор фиксированного количества некоторых однотипных значений (компонент массива).

Имя всего массива называют полной переменной, поскольку ее значение есть весь массив.

К каждой компоненте массива имеется прямой доступ. Для этого после имени массива следует указать в квадратных скобках индекс компоненты, например Х[10], MATR[4,5]. Такие переменные называются переменными с индексом, или индексными переменными. Значением такой переменной является не весь массив, а отдельная компонента, номер которой задается индексом. Поэтому переменную с индексом называют еще частичной переменной. Отметим, что в двумерном массиве первый индекс указывает номер строки, а второй - номер столбца.

В общем случае в качестве индекса может быть использована не только константа, но и выражение, значение которого и определяет номер компоненты массива. При этом важно, что в индексное выражение могут входить переменные, так что при изменении их значений меняется и значение индекса, которое определяет номер компоненты массива, например А[К]; А[I + J]; X[1,J]; X[I + 2J]. Таким образом, одна и та же переменная с индексом в процессе выполнения программы может обозначать различные компоненты массива. Очень важно в таких случаях помнить, что переменные, используемые для индексации, к моменту обработки элементов массивов должны быть определены.

Возможны не только арифметические массивы, но массивы других ти­пов, в частности строковые. Например, список фамилий (объект задачи) можно рассматривать как одномерный строковый массив.

Типовые действия с массивами

Массивы должны быть описаны в программе в разделе описания типов или переменных. Например:

CONST

N=10;

TYPE

Vector = ARRAY[1..20] OF REAL;

Matr = ARRAY[1..N,1..5] OF BYTE;

VAR

A, B : Vector;

C : ARRAY [1..N] OF INTEGER;

D : Matr;

Здесь описаны три одномерных и один двумерный массивы. Одномерные массивы А и В типа Vector состоят из двадцати элементов, а массив С – из десяти элементов. Двумерный массив D представляет собой матрицу размерами 10 5, имеющую десять строк и пять столбцов.

Далее приводятся фрагменты программ для реализация ти­повых действий с массивами. Предполагается, что описания мас­сивов в программах имеются, а индексы начинаются с 1.

1. Ввод массивов с клавиатуры:

а) одномерного массива А б) двумерного массива С

For I:=1 То N Dо For I:=1 То N Dо {строки}

Read( A[i]); For J:=1 To M Dо

{столбцы}

Read(C[i,j]);

При каждом выполнении оператора Read вводится один эле­мент массива (после набора каждого элемента нужно нажимать клавишу Enter (Ввод)). Ввод двумерного массива осуществляет­ся в приведенном примере по строкам.

2. Вывод на экран массивов:

а) одномерного в строку б) одномерного в столбец

For I :=l To N Do For I :=l To N Do

Write(A[i]); Writeln(A[i]);

в) двумерного по строкам

For I :=l To N Do

Begin

For J :=l To M Do

Write (C[i,j]);

Writeln;

End.

3. Суммирование элементов массивов:

а) одномерного б) двумерного

S:=0; S:=0;

For I :=l To N Do For I :=l To N Do

S :=S+A[i]; For J :=l To M Do

S:=S+C[i,j];

4. Суммирование диагональных элементов матрицы (вычи­сление следа матрицы):

S:=0;

For I :=l To N Do

S:=S+C[i,i];

5. Суммирование двух массивов по элементам (оба массива -слагаемых должны полностью совпадать как по размерности, так и по типам их элементов):

а) одномерного б) двумерного

For i:=1 To N Do For i:=l To N Do

C[i]:=A[i]+B[i]; For j:=l To M Do

C[i,j]:=A[i,j]+B[i,j];

6. Суммирование элементов заданной k-й строки матри­цы:

S:=0;

For j:=l To M Do

S:=S+C[k,j];

7. Суммирование элементов строк матриц:.

Необходимо вычислить сумму элементов каждой строки матри­цы С размерами N М. Результат получим в виде вектора D:

For i:=l То К Do

Begin

S:=0;

For j:=l To M Do

S:=S+C[i,j];

D[i]:=S;

End;

8. Транспонирование матрицы:

Необходимо заменить строки матрицы ее столбцами, а столбцы — строками, т.е. вычислить d_ij = c_ji , i =1,... N, j = 1,... M:

For i:=l To N Do

For j:=l To M Do

D[i,j]:=C[j,i];

Транспонированную матрицу можно получить в исходном массиве С. Для квадратной матрицы размерами N N для это­го необходимо поменять местами каждый элемент верхнего треугольника с соответствующим элементом нижнего (диагональ­ные элементы переставлять не нужно). При этом для каждой строки нужно выполнять перестановку элементов, располо­женных правее главной диагонали, с элементами соответству­ющего столбца, расположенного ниже главной диагонали, т.е. взаимно перемещать элементы С_i,j и С_j,i ,i=1, ...,N-1; j = i+1, ... , N.

For i:=l To N-1 Do

For j:=i+l To N Do

Begin

X:= C[i,j];

C[i,j] := C[j,i];

C[j,i] := X;

End;

Для прямоугольной матрицы алгоритм усложняется.

9. Умножение матрицы на вектор:

Для вычисления произведения С матрицы A размерами N М на вектор В размером М необходимо вычислить С_i=i=1, ... N:

For i:=l To N Do

Begin

S:=0 ;

For j:=l To M Do

S:=S+A[i,j]*B[j];

C[i]:=S;

End;

10. Умножение матрицы на матрицу:

Для умножения матрицы А размерами N L на матрицу B раз­мерами L М необходимо вычислить С_ij = , i = 1 ... N, j = l,...М;

For i:=1 То М Do

For j:=l To N Do

Begin

S:=0 ;

For k:=l To L

S:=S+A[i,k]*B[k,j];

C[i,j]:=S;

End;

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

Требуется удалить k—й элемент из массива А размером N. Удалить элемент, расположенный на k—м месте в массиве, мож­но, сдвинув весь "хвост" массива, начиная с (k + 1)—го элемен­та, на одну позицию влево, т.е. выполняя операцию a_i :=a_i+1, i= k, k+1,... ,N-1:

N:=N-l;

For i:=k To N Do

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

12. Включение элемента в заданную позицию массива:

Перед включением элемента в k—ю позицию необходимо раз­двинуть массив, т.е. передвинуть "хвост" массива вправо на одну позицию, начиная с (k + 1)-го элемента, выполняя операцию a_i+1 := a_i, i = N, N-1 ,... ,k. Перемещения элементов массива нужно начинать с конца. В противном случае весь "хвост" будет заполнен элементом а_k. Далее k-му элементу присваивается за­данное значение В. Размер массива увеличивается на 1:

For i :=N Downto k Do

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

A[k]:=B;

N:=N+1;

13. Включение элемента в массив, упорядоченный по возрастанию, с сохранением упорядоченности:

Сначала следует найти элемент, перед которым необходимо включать заданное число В. Для этого нужно проверять условие В < а_i, для всех i =1 ,2,.... При выполнении условия текущее значение индекса i определяет позицию добавляемого элемента. Далее включение элемента осуществляется по алгоритму, опи­санному в п. 12.

k:=1;

While B<a[k] do

Begin

k:=k+1;

End;

For i :=N Dowto k-1 Do

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

A[k-1]:=B ;

14. Удаление строки из матрицы:

Требуется удалить строку с заданным номером К. Решение этой зада­чи аналогично решению задачи удаления элемента из одномерного массива. Все строки, начиная с (К + 1)-й, нужно переместить вверх. Число строк уменьшается на 1.

N:=N-1;

For i:=K To N Do

For j:=l To M Do

B[i,j]:=B[i+l,j];

Удаление столбца осуществляется аналогично.

15. Включение cтроки в матрицу:

Включаемая строка задана как вектор С. Включение строки в матрицу аналогично включению элемента в одномерный массив (см. п.12).

For i :=N Downto К Do

For j:=1 To M Do

B[i+l,j]:=B[i,j];

For j:=1 To M Do

B[K,j]:=C[j];

N:=N+1;

16. Поиск минимального (максимального) элемента в мас­сиве:

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

Р:=А[1];

К:=1 ;

For i:=2 To N Do

If P>A[i] Then

Begin

P:=A[i];

K:=i

End;

Если в массиве несколько элементов имеют минимальное зна­чение, то

в К будет запоминаться индекс первого из них. Если проверять условие Р>=А(i), то будет запоминаться индекс по­следнего элемента. Для поиска максимального элемента нужно проверять условие P<A(i). Для двумерного массива алгоритм аналогичный, но нужно просматривать все элементы

каждой строки, что требует организации двойного цикла, и запоминать два индекса: номер строки К и номер столбца L.

P:=C[l,l];

K:=l;

L:=l ;

For i:=l To N Do

For j:=l To M Do

If P>C[i,j] Then

Begin

P:=C[i,j];

K:=i;

L:=j

End;

17. Преобразование матрицы:

Преобразование матрицы, как правило, производится относительно ка­кой-либо оси, которой могут быть главная диагональ, побочная диагональ, любая строка или столбец.

Рассмотрим эти понятия на примере матрицы А размерами N N, обозна­чив номер строки переменной I, а номер столбца - переменной J.

1. Элементы главной диагонали имеют одинаковые индексы, т.е. А(1,1) (например А(1,1), А(2, 2),... A(N, N)).

2. У всех элементов, расположенных выше (правее) главной диагонали, J>I.

3. У всех элементов, расположенных ниже главной диагонали, J<I.

4. Элементами, симметричными относительно главной диагонали, яв­ляются пары A(I, J) и A(J, I).

5. У элементов, образующих побочную диагональ, есть зависимость индексов: I+J=N+1, или J=N+1-I, т.е. A(I, N+1-I).

6. У всех элементов, расположенных выше побочной диагонали, I<N+1-J.

7. У всех элементов, расположенных ниже побочной диагонали, I>N+1-J.

8. Элементами, симметричными относительно побочной диагонали, являются пары A(I, J) и A(N+1-J, N+1-I).

9. Элементами, симметричными относительно средней горизонтальной оси, являются пары A(I, J) и A(I, N+1-J).

Примеры решения задач по обработке массивов

Пример 2.1. Сформировать массив Y из положительных эле­ментов заданного массива Х размером 10.

Решение.

Возможный вариант программы:

PROGRAM PRIM21;

VAR

X, Y : ARRAY [1..10] OF REAL;

I, K : INTEGER;

{X – исходный массив}

{Y – сформированный массив}

{K – количество элементов массива Y}

BEGIN

{Ввод массива Х}

For I:=1 To 10 Do

Read (X[I]);

{Формирование массива Y}

K:=0;

For I:=1 To 10 Do

If X[I] > 0 Then

BEGIN

K:=K+1;

Y[K]:=X[i];

END;

{Вывод сформированного массива Y на экран}

For I:=1 To K Do

Write(Y[i]:5:2);

End.

Пример 2.2. В одномерный массив размером N ввести произвольные числа. Поменять местами элементы массива, стоящие равноудаленно от элемента с заданным индексом К. Вывести на экран в строку исходный и новый массивы.

Решение.

Введем произвольные числа в массив A(N).

Индекс элемента, относительно которого производится обмен, обозна­чим переменной К. При вводе К следует выполнить проверку, так как К не должно быть меньше единицы или больше N.

Алгоритм. Алгоритм заключается в том, что менять местами элементы массива можно до тех пор, пока не закончится массив слева или справа от К, т.е. пока индекс элемента слева больше или равен единице, а индекс элемента справа от К меньше или равен N.

Для формирования индекса элемента слева от К назначаем переменную L, а для формирования индекса элемента справа от К - переменную PR.

Вариант программы

PROGRAM PRIM22;

VAR

A : ARRAY [1.. 100] OF REAL;

N , I, L, K,PR : INTEGER;

X : REAL;

BEGIN

Write('Введите размер массива (не более 100)’);

Readln(N);

WHILE (N<=2) OR (N>=100) DO

Begin

Writeln(‘Ошибка ввода. Повторить’);

Writeln(‘Введите размер массива’);

Readln(N);

End;

FOR I:=1 ТО N Do

Begin

Write(‘Введите ‘, I:3, ‘ число ’);

Readln(A[I]);

End;

Writeln(‘Исходный массив’);

FOR I:=1 TO N Do

Begin

Write(A[I]);

If I Mod 6 = 0 Then Writeln;

End;

Writeln;

Write(‘Введите индекс‘);

Readln(К) ;

L:=K-1;

PR:=K+1;

WHILE (L>=1) AND (PR<=N) Do

Begin

X:=A[L];

A[L]:=A[PR];

A[PR]:=X;

L:=L-1;

PR:=PR+1;

END;

Writeln;

Writeln(‘Новый массив’);

FOR I:=1 ТО N Do

Begin

Write(A[I]);

If I Mod 6 = 0 Then Writeln;

End;

END.

Пример 2.3. В массивы вводятся элементы двух последовательностей A_i и B_j целых чисел, которые содержат 6 и 8 элементов соответственно.

A_i — неубывающая и B_j — невозрастающая последовательности. Не­обходимо вывести на экран общий список значений элементов этих последовательностей по их возрастанию без создания третьего массива.

Решение.

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

В соответствии с условиями задачи, массив А начинаем просматривать с первой ячейки, а массив В — с последней, т.е.

если условие А[1]<В[8] выполняется - на экран выводится А[1];

если условие А[2]<В[8] не выполняется - на экран выводится В[8];

если условие А[2]<В[7] не выполняется - на экран выводится В[7];

если условие А[2]<В[6] не выполняется - на экран выводится В[6];

если условие А[3]<В[1] не выполняется - на экран выводится В[1].

Дальнейшее сравнение чисел из двух массивов невозможно, так как один из них (массив В) закончился. Оставшиеся в массиве А числа следует вывести на экран.

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

Анализируя приведенные выше строки сравнения чисел из разных мас­сивов, приходим к выводу:

- индексы элементов массива меняются, поэтому введем переменные для формирования индексов (К1 и К2);

- начальное значение индекса элемента в массиве А — К1 равно 1;начальное значение индекса элемента в массиве В — К2 равно 8;

- сравнивать числа из разных массивов можно до тех пор, пока один из массивов не закончится, т.е. пока К1<=6, а К2>1.

Программа

PROGRAM PRIM23;

VAR

A : ARRAY [1..6] OF INTEGER;

B : ARRAY [1..8] OF INTEGER;

I, K1, K2 : INTEGER;

BEGIN

Writeln(‘Введите массив А’);

FOR I:=1 ТО 6 Do

Begin

Write(‘Введите ‘, I:1, ‘ число массива А’);

Readln(A[I]);

End;

Writeln(‘Введите массив B’);

FOR I:=1 ТО 8 Do

Begin

Write(‘Введите ‘, I:1, ‘ число массива B’);

Readln(B[I]);

End;

Writeln(‘Общий список чисел по возрастанию’);

К1:=1;

К2:=8;

WHILE (К1<=6) AND (K2>=1) Do

IF A[K1]<B[K2] THEN

Begin

Write(A[K1]:4);

K1:=K1+1

End

ELSE

Begin

Write(B[K2]:4);

К2:=К2-1;

END;

{Из двух циклов For в зависимости от чисел, введенных в массивы, будет работать какой-либо один из них}