4.1.2. Обработка массивов.
Массивы используются для решения большого класса задач. Эти классы можно разделить на две большие группы: классы поиска и сортировки.
Рассмотрим класс поиска элемента (или нескольких элементов) с заданными свойствами. Задача заключается в нахождении индексов элемента и значения элемента. Алгоритм состоит из следующих основных шагов: 1. ввод вспомогательных переменных; 2. просмотр массива в определенном порядке с целью нахождения искомого элемента.
Пример 1.3.1.
Н
айдем
наибольший элемент в матрице формата
M×N.
I, J – вспомогательные переменные
P, Q – индексы максимального элемента
A [I, J] – элементы матрицы
Пример на Turbo Pascal:
TYPE
matr = array [1..50, 1..50] of real;
VAR
A: matr;
I, J, P, Q, M, N: integer;
BEGIN
WRITE (‘Размеры матрицы? ‘);
READLN (M,N);
WRITE (‘Введите элементы: ‘);
FOR I:= 1 TO M DO
FOR J:= 1 TO N DO
READ (A [I, J]);
P:= 1;
Q:= 1;
FOR I:= 1 TO M DO
FOR J:= 1 TO N DO
IF A [I, J] > A [P, Q] THEN
BEGIN
P:= I;
Q:= J
END;
WRITELN (‘Максимальный элемент = ’,A [P,Q],’ находится
в ‘,P,’ строке и ’,Q,’ столбце’)
END.
Пример на QBasic:
INPUT "RAZM: "; M, N
DIM A(1 TO M, 1 TO N)
FOR I = 1 TO M
FOR J = 1 TO N
INPUT A(I, J)
NEXT J
NEXT I
P = 1
Q = 1
FOR I = 1 TO M
FOR J = 1 TO N
IF A(I, J) > A(P, Q) THEN
P = I
Q = J
END IF
NEXT J
NEXT I
PRINT "Максимальный элемент = ", A(P, Q), " находится в ", P, " строке и ", Q, " столбце "
Рассмотрим следующий пример:
Найти минимальный номер строки, содержащей максимальное число элементов знаки которых чередуются.
A – матрица MxN
I, J
K – текущее количество элементов с чередующимися знаками.
MK, MI
P – если true, то строк с чередующимися элементами нет
Пример на Turbo Pascal:
var
A: array [1..50, 1..50] of Integer;
I, J: Integer;
K: Integer;
MK, MI: Integer;
P: Boolean;
M, N: Integer;
begin
ReadLn(M, N);
for I := 1 to M do
for J := 1 to N do
begin
Write('A[', I, ', ', J, ']: ');
ReadLn(A[I, J]);
end;
P := True;
MK := 1;
for I := 1 to M do
begin
K := 1;
for J := 1 to N - 1 do
begin
if (A[I, J] * A[I, J + 1]) < 0 then
begin
Inc(K);
P := False;
end
else
if K > MK then
begin
MI := I;
MK := K;
K := 1;
end;
if K > MK then
begin
MI := I;
MK := K;
end;
end;
end;
if P then
WriteLn('Нет таких строк')
else
WriteLn('Строка: ', MI, ' Количество повторяющихся: ', MK);
ReadLn;
end.
Пример на QBasic:
INPUT M, N
DIM A(1 TO M, 1 TO N)
FOR I = 1 TO M
FOR J = 1 TO N
INPUT "A[I, J]"; A(I, J)
NEXT J
NEXT I
P = 1
MK = 1
FOR I = 1 TO M
K = 1
FOR J = 1 TO N - 1
IF (A(I, J) * A(I, J + 1)) < 0 THEN
K = K + 1
P = 0
ELSE
IF K > MK THEN
MI = I
MK = K
K = 1
END IF
END IF
IF K > MK THEN
MI = I
MK = K
END IF
NEXT J
NEXT I
IF P = 1 THEN
PRINT "Нет таких строк"
ELSE
PRINT " Строка: ", MI, "Количество повторяющихся: ", MK
END IF
Очень распространенным классом задач обработки массивов является их сортировка. Обычно элементы массива сортируются в порядке неубывания или в порядке невозрастания.
Поэтому рассмотрим следующий пример:
Имеется массив А, содержащий n элементов. Произвести сортировку элементов в порядке неубывания их значений.
Воспользуемся алгоритмом сортировки методом пузырька.
Идея этого алгоритма состоит в повторяющихся проходах по сортируемому массиву. За каждый проход элементы последовательно сравниваются попарно и, если порядок в паре неверный, выполняется обмен элементов. Проходы по массиву повторяются до тех пор, пока на очередном проходе не окажется, что обмены больше не нужны, что означает — массив отсортирован.
I, K, X – вспомогательные переменные
A(K) – элемент матрицы А
Пример на QBasic:
DIM I AS INTEGER, K AS INTEGER, N AS INTEGER
P
RINT
“Задайте количество элементов массива
“
INPUT N
DIM A (1 TO N) AS SINGLE
PRINT “Введите “; N; “ чисел“
FOR I = 1 TO N
INPUT A (I)
NEXT I
FOR I = 1 TO N-1
FOR K = I TO 1 STEP -1
IF A (K) >= A (K+1) THEN
X=A (K)
A (K) = A (K+1)
A (K+1) = X
END IF
NEXT K
NEXT I
PRINT “Полученный массив: “
FOR I = 1 TO N
PRINT USING “####.##”; A(I);
NEXT I
END
Пример на Turbo Pascal:
var
A: array [1..100] of Real;
N: Integer;
X: Real;
I, K: Integer;
begin
ReadLn(N);
for I := 1 to N do
ReadLn(A[I]);
for I := 1 to N - 1 do
for K := I downto 1 do
if A[K] >= A[K + 1] then
begin
X := A[K];
A[K] := A[K + 1];
A[K + 1] := X;
end;
WriteLn('Полученный массив: ');
for I := 1 to N do
WriteLn('A[', I, ']: ', A[I]:3:3);
ReadLn;
end.