ПримерЫ обработки двумерных массивов

Обработка двумерных массивов

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

b: array[1..n] of array[1..m] of integer;

С другой стороны двумерный массив можно описать и так:

b: array[1..n,1..m] of integer;

Чаще пользуются вторым описанием, оно является более кратким, но менее наглядным. В описании n – количество строк, m – количество столбцов матрицы. При изменении второго индекса на единицу мы передвигаемся вдоль строки, а при изменении первого индекса на единицу передвигаемся вертикально вдоль столбца. Обычно в качестве идентификатора номера строки используют символ i, а столбца – j. Тогда к элементу массива, описанному выше, можно обратиться по имени b[i,j].

Ниже приведены примеры описания двумерных массивов и обращения к элементам:

type

massiv1=array[1..n] of real;

massiv2=array[1..5,1..6] of integer;

var

f:array[1..10] of massiv1;

mas:array[0..10,1..30] of char;

b:massiv2;

asd:array[1..20,1..10] of byte;

begin

..............

f[i,j]:=13.13;

mas[0,1]:='a';

b[5,6]:=7;

asd[i,8]:=0;

...............

 

При обработке двумерных массивов возникают такие же задачи, как и при обработке одномерных массивов: ввод элементов массива, нахождение суммы, произведения, среднего и т.д., поиск некоторого элемента в массиве, сортировка элементов массива, вывод элементов массива.

На рис.17 приведена схема алгоритма формирования элементов массива с помощью датчика случайных чисел, вывод элементов массива на экран, вычисление суммы всех элементов двумерного массива. Программа дана в примере pr21.

program pr21;

const n1=10; {максимальнoе количество стpок массива}

m1=10; { максимальное количество столбцов массива}

type mas = array[1..n1,1..m1] of integer;

var a: mas;

i, { текущий номеp строки }

j, { текущий номеp столбца }

n,s,m : integer;

begin

writeln('Введите число стpок и столбцов массива:');

read(n,m);

randomize;

Рис. 17

for i:=1 to n do

for j:=1 to m do

a[i,j]:=random(10);

writeln('Полученный массив');

for i:=1 to n do

begin

for j:=1 to m do

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

writeln;

end;

s:=0;

for i:=1 to n do

for j:=1 to m do

s:=s+a[i,j];

writeln('s=',s);

end.

Анализируя предложенную программу, можно заметить, что для ввода, вывода и нахождения суммы элементов массива используются три раза вложенные циклы. Так как массив располагается в непрерывной области памяти построчно, более рационально будет и обрабатывать элементы построчно. В программе во вложенных циклах для каждого значения индекса i индекс j изменяется от 1 до m, т.е. индекс j изменяется чаще. Таким образом, обрабатываются элементы массива построчно. Хотелось бы обратить внимание на вывод элементов массива на экран. Здесь для каждого значения i в теле цикла выполняются два оператора: первый оператор цикла выводит на экран в строчку элементы одной строки, а второй оператор вывода переводит курсор на новую строку, что как раз и обеспечивает вывод матрицы в виде прямоугольника.

Следующий пример иллюстрирует работу с диагоналями матрицы. Дана квадратная матрица. Заменить отрицательные элементы побочной диагонали на сумму элементов главной диагонали матрицы. При изучении поставленной задачи следует напомнить, что главная диагональ проходит из правого верхнего в левый нижний угол. Так как мы работаем с квадратной матрицей, то только на главной диагонали будут лежать элементы, индексы строк и столбцов которых одинаковы. Именно этот факт и используется при решении задачи. Мы не будем перебирать все элементы массива и смотреть, совпали ли индексы, а сразу задаем оба индекса с помощью одного идентификатора i. Побочная диагональ проходит из правого верхнего в левый нижний угол матрицы. Нетрудно заметить, что при движении по побочной диагонали номер строки возрастает от 1 до n, номер столбца убывает от n до 1. Таким образом, только на побочной диагонали лежат элементы, у которых номер столбца определяется по формуле j=n-i+1.Программа приведена в примере pr22, а графическая схема алгоритма – на рис.18.

program pr22;

const n1=10; {максимальнoе количество стpок массива}

type

mas = array[1..n1,1..n1] of integer;{квадpатная матpица}

var a:mas;

i, { текущий номеp стpоки }

j, { текущий номеp столбца }

n,s:integer;

begin

writeln('Введите число стpок и столбцов массива:');

read(n);

for i:=1 to n do

for j:=1 to n do

begin

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

read(a[i,j]);

end;

writeln('Исходный массив');

for i:=1 to n do

begin

for j:=1 to n do

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

writeln;

end;

s:=0;

for i:=1 to n do {Сумма элементов главной диагонали }

s:=s+a[i,i];

writeln('s=',s);

for i:=1 to n do{Замена элементов побочной диагонали}

begin

j:=n-i+1;

if a[i,j]<0 then a[i,j]:=s;

end;

Рис. 18

writeln('Полученный массив');

for i:=1 to n do

begin

for j:=1 to n do

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

writeln;

end;

end.

И последний пример на обработку двумерных массивов. Дана прямоугольная матрица. Отсортировать столбцы матрицы в порядке неубывания максимальных элементов столбцов.

Решение задачи сводится к формированию одномерного массива из максимальных элементов столбцов, а уж затем сортируется этот одномерный массив и параллельно – столбцы матрицы. Чтобы не запутать читателя , в этой задаче используем знакомый метод сортировки "пузырьком". Исходный массив имеет идентификатор a, а промежуточный одномерный массив – b. Графическая схема алгоритма приведена на рис.19, а программа – в примере pr23.

program pr23;

const n1=10; {максимальнoе количество стpок массива}

m1=10; {максимальнoе количество столбцов массива}

type

mas = array[1..n1,1..m1] of integer;{квадpатная матpица}

var

a:mas;

b:array[1..m1] of integer;{массив из максимальных элементов столбцов}

i, { текущий номеp стpоки }

j, { текущий номеp столбца }

n,m,d:integer;

fl:boolean;

begin

writeln('Введите число стpок и столбцов массива:');

read(n,m);

for i:=1 to n do

for j:=1 to m do

begin

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

read(a[i,j]);

end;

Рис. 19

 

writeln('Исходный массив');

for i:=1 to n do

begin

for j:=1 to m do

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

writeln;

end;

{Фоpмиpование одномеpного массива из максимальных

элементов столбцов}

for j:=1 to m do {Пеpебиpаем все столбцы}

begin

b[j]:=a[1,j];{Пpинимаем пеpвый элемент в столбце за максимальный }

for i:=2 to n do{Пеpебиpаем все элементы в столбце}

if a[i,j]>b[j] then b[j]:=a[i,j];

end;

{Сортировка одномерного и двумерного массива}

repeat

fl:=true;{Поднять флаг}

for j:=1 to m-1 do {Перебрать элементы одномерного

массива}

if b[j]>b[j+1] then { Проверить нужна ли перестановка }

begin

fl:=false;{опустить флаг}

{Переставить элементы одномерного массива и}

d:=b[j];

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

b[j+1]:=d;

{столбцы двумерного массива}

for i:=1 to n do

begin

d:=a[i,j];

a[i,j]:=a[i,j+1];

a[i,j+1]:=d;

end;

end;

until fl;{Завершить сортировку,если флаг не опускался}

writeln('Отсортированный массив');

for i:=1 to n do

begin

for j:=1 to m do

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

writeln;

end;

end.

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