ЛАБОРАТОРНАЯ РАБОТА № 6 Разработка алгоритмов и программирование задач формирования и обработки двумерных массивов

ЛАБОРАТОРНАЯ                      РАБОТА № 6

Разработка алгоритмов и программирование задач формирования и обработки двумерных массивов

Цель: освоить методы разработки алгоритмов и программирование задач по формированию и обработке двумерных массивов.

Краткие теоретические сведения

Массивы, положение элементов в которых описывается двумя индексами, называются двумерными. Двумерный массив можно представить в качестве таблицы, в каждой ячейке которой содержится определенное значение. Для того чтобы получить доступ к тому или иному элементу двумерного массива, нужно указать номер строки i и номер столбца j. Часто двумерные массивы называются матрицами.

Например, представление чисел последовательно в несколько строк является матрицей:

æ 2.3

ç

- 2.7

7.4

0.2 ö

÷

Х = ç- 0.4

3.2

- 4.8

- 0.12÷

ç 12.7

- 1.4

÷

Данная матрица Х имеет размер 3 на 4, т.е. она состоит из 3 строк и 4 столбцов.

Количество элементов или размер массива вычисляется как произведение количества строк n=3 на количество столбцов m=4, то есть размер массива составляет 3 • 4 = 12 элементов.

Каждый элемент имеет свой номер, он состоит из двух чисел - номера строки, в которой находится элемент, и номера столбца. Например, Х₁₃ – это элемент, стоящий в первой строке и в третьем столбце.

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

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

1

Ввод N, М

2

i =1, N                    

3

j =1, М

4

Ввод Х_ij

Для осуществления ввода элементов двумерного массива Х вначале необходимо ввести количество строк N и количество столбцов М (блок 1). Во внешнем цикле осуществляется перебор параметра i от 1 до N (блок 2), а во вложенном цикле осуществляется перебор параметра j от 1 до М (блок 3). Ввод значения элемента массива Х_ij выполняется в блоке 4.

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

83

1

i =1, N                    

2

j =1, М

3

Вывод Х_ij

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

Двумерные массивы на языке программирования Pascal описать можно в разделе переменных VAR или в разделе типов TYPE.

1   вариант

Var имя массива: array [тип индекса] of тип элементов массива;

Например,

Var Х: array [1..3,1..4] of integer;

//Х     –    двумерный          массив       размером         3    на     4,     который        состоит        из элементов целого типа.

2   вариант

Type имя типа = array [тип индекса] of тип элементов массива; Var имя массива: имя типа;

Например,

Type mas2= array [1..3,1..4] of real; Var Х: mas2;

Для обращения к элементу двухмерного массива необходимо указать имя массива и в квадратных скобках через запятую – значения двух индексов (первый указывает номер строки, а второй – номер столбца), на пересечении которых стоит элемент (например, х[i,2]:=6).

Формирование двумерного массива можно осуществить несколькими способами:

1)   ввод значений элементов двумерного массива с клавиатуры

Write („Введите n, m‟);                 Readln (n, m); Writeln ('Введите элементы матрицы Х'); For i:=1 to n do

For j:=1 to m do

begin       Write („Х[', i , ',' , j ,']=');                  Read (X[i, j]);            end;

84

Когда осуществляется ввод очередного элемента, то оператор read считывает его и помещает в ячейку с текущими индексами i и j. Когда параметр i равен единице, значение параметра j будет изменяться m раз, и, значит, заполняется первая строка таблицы. Когда параметр i равен двум, значение параметра j снова будет изменяться m раз и заполняется вторая строка таблицы. Аналогично заполняются остальные строки таблицы. Вложенный цикл в общей сложности совершит n ∙ m итераций, внешний только n.

2)            задание    значений     элементов     двумерного     массива     с использованием генератора случайных чисел

Const n = 5; m=4;

Var X: array [1..n, 1..m] of integer; i, j : integer;

begin

randomize;

for i:=1 to n          do

for j:=1 to m           do

X[i, j] := random(45)-22;

end;

3)       считывание значений      элементов двумерного массива  из текстового файла

Assign (F,’C:\tp\bin\my.txt’); Reset (F);

Readln (F, n, m);                            {чтение из файла размерности матрицы} For i:=1 to n do begin

For j:=1 to m           do

Read (F, X[i, j]);                         {считывание элементов строки} Readln (F);

end; Close(F);

В программе должна быть объявлена переменная типа TEXT, которая будет указывать на текстовый файл, файл нужно открыть и указывать на него в каждом операторе ввода (или вывода). Для данного примера файл my.txt в папке C:\tp\bin должен иметь такой вид: в первой строке указывается количество строк и столбцов матрицы, затем элементы матрицы по строкам.

85

Например,

4)           задание    значений     элементов    двумерного    массива    по заданному правилу

Например, необходимо заполнить массив Х(6, 8) следующим образом:

Массив заполняется по принципу «змейки». Правило заполнения: если номер строки – нечетное число, то элемент массива вычисляется по формуле: Х[i,j]=(i - 1)*m + j, иначе Х[i,j]= i * m – j +1.

Write („Введите n, m‟); Readln (n, m); For i:=1 to n do

For j:=1 to m do

if i mod 2 = 1 then Х[i,j]=(i-1)*m+j else Х[i,j]=i*m-j+1;

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

For i:=1 to n do begin For j:=1 to m do

Write (X[i, j]: 6 : 2, „ „); {вывод элементов i-й строки} Writeln ; {перевод курсора на новую строку} end;

При решении задач с двумерными массивами можно выделить несколько видов задач.

86

Пример 1. Для массива А(n,m) определить процент нулевых элементов.

Решение.

Введем обозначения: n, m – количество строк и столбцов в массиве; А - имя массива; i, j – индексы массива; А(i,j) - элемент массива А; k - количество нулевых элементов в массиве А; р - процент нулевых элементов.

Исходные данные: n, m, массив А. Результат вычислений: р.

Схема алгоритма решения задачи имеет вид:

Пояснения к решению задачи.

Формула         для      расчета        процента         нулевых         элементов          имеет       вид:

p =    k n × m

×100% ,  где k - количество нулевых элементов в массиве А.

87

Текст программы решения задачи имеет вид: program pr1;

type mas=array[1..10,1..10] of integer; var a:mas;

i,j,n,m,k: integer;                p: real; begin

writeln(„Ввод n,m‟); readln (n,m); writeln („Ввести массив A‟);

for     i:=1       to     n     do

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

end.

k:=0;

for      i:=1       to     n     do

for      j:=1       to     m     do

if     a[i,j] =0        then      k:=k+1;

p := k*100/(n*m);                    writeln ('p=', p:6:2);

Пример 2. Для массива Т(n,m) определить количество и произведение положительных элементов, которые расположены ниже главной диагонали.

Решение.

Введем обозначения: n, m – количество строк и столбцов в массиве; Т - имя массива; i, j – индексы массива; Т(i,j) - элемент массива Т; k - количество элементов; р – произведение элементов.

Исходные данные: n, m, массив Т. Результат вычислений: k, р.

Текст программы решения задачи имеет вид: program      pr2;

type mas=array[1..10,1..10] of real; var t:mas;

i, j, n, m, k: integer;                  p: real; begin

writeln („Ввод n,m‟); readln (n,m); writeln („Ввод элементов массива T‟); for    i:=1      to         n          do

for      j:=1      to     m     do     read (t[i,j]); k:=0; p:=1;

88

end.

for      i:=1       to     n     do

for      j:=1       to     m     do if          t[i,j] > 0 then if i > j then

begin   k:=k+1; p:=p * t[i,j]                     end; writeln ('p=', p:6:2, '                                    k=', k:2);

Схема алгоритма решения задачи имеет вид:

89

Пояснения к решению задачи.

Матрицу, у которой одинаковое количество строк и столбцов, называют квадратной. У квадратной матрицы появляются

«диагонали» - главная, идущая из левого верхнего угла в правый нижний и побочная. На главной диагонали лежат элементы, у которых номер строки и столбца равны между собой (Т[1,1], Т[2,2] и т.д.). Диагональ делит матрицу на две части. У элементов, лежащих ниже главной диагонали, номер столбца меньше номера строки (например, Т[2,1], Т[5,2]).

Для решения задач такого вида необходимо вспомнить следующие свойства матриц:

-   если номер строки элемента совпадает с номером столбца (i=j), значит, элемент находится на главной диагонали матрицы;

-    если номер строки превышает номер столбца (i>j), то элемент находится ниже главной диагонали матрицы;

-     если   номер столбца больше номера строки (i<j), то элемент находится выше главной диагонали матрицы;

-    элемент находится на побочной диагонали, если его индексы удовлетворяют неравенству (i+j-1)=N;

-   неравенство (i+j-1) <N характерно для элемента, находящегося выше побочной диагонали;

-   неравенство (i+j-1) >N характерно для элемента, находящегося ниже побочной диагонали.

Пример 3. Для массива Х(n,m) определить минимальный по модулю элемент и его индексы.

Решение.

Введем обозначения: n, m – количество строк и столбцов в массиве; Х - имя массива; i, j – индексы массива; Х(i,j) - элемент массива Х; min - минимальное значение в массиве Х, ni, nj - индексы минимального значения.

90

Исходные данные: n, m, массив Х. Результат вычислений: min, ni, nj.

Схема алгоритма решения задачи имеет вид:

1

начало

2

Ввод N, М

3

i =1, N                                         

4

j =1, М

5

Ввод Х_ij

Пояснения к решению задачи.

Для поиска минимального по модулю элемента в массиве используется стандартный алгоритм, состоящий из следующих шагов:

1.               выбирают в качестве минимального значения элемент, расположенный на пересечении первой строки и первого столбца

91

(min =│Х₁₁│), запоминают его номер строки и номер столбца (ni = 1, nj=1);

2.          сравнивают значение переменной min со вторым элементом массива. Если оказывается, что │Х₁₂│ меньше чем min, т.е. если выполняется условие │Х₁₂│<min, тогда в качестве min берут значение │Х₁₂│ и запоминают его индексы. В противном случае, значение переменной min оставляют без изменения.

3.    Циклически повторяют действия п.2 для третьего, четвертого и т.д. элементов. По завершению цикла переменная min будет содержать минимальный по модулю элемент массива, ni - номер строки, nj - номер столбца минимального по модулю элемента.

Аналогично осуществляется поиск максимального элемента.

Текст программы решения задачи имеет вид:

Program         pr3;

type mas=array[1..10,1..10] of real; var Х:mas;

i, j, n, m, ni, nj: integer;                 min: real; begin

writeln („Ввод n,m‟); readln (n,m); writeln („Ввод элементов массива X‟); for    i:=1      to         n          do

for      j:=1      to     m     do     read (X[i,j]); min:=abs(X[1,1]); ni:=1; nj:=1;

for     i:=1       to     n     do

for      j:=1      to     m     do

if     abs(X[i,j])<min then

begin       min:=abs(X[i,j]); ni:=i; nj:=j; end; writeln („Минимальный по модулю элемент равен ‟, min:6:2); writeln („Индексы ‟, '                                                      ni=', ni:2, '           nj=', nj:2);

end.

Пример 4. Из массива А(n,m) сформировать массив B(m), каждый элемент которого равен количеству отрицательных элементов соответствующего столбца массива А.

Решение.

Введем обозначения: n, m – количество строк и столбцов в массиве; А, В - имя массива; i, j – индексы массива; А(i,j) - элемент массива А; В(j) - элемент массива В; k - количество отрицательных элементов.

92

Исходные данные: n, m, массив А. Результат вычислений: массив В.

Схема алгоритма решения задачи имеет вид:

Текст программы решения задачи имеет вид: Program     pr4;

type mas1=array[1..10,1..10] of integer; mas2=array[1..10] of integer;

var a:mas1; b:mas2;                 i,j,n,m,k: integer; begin

writeln („Ввод n,m‟); readln (n,m); writeln („Ввод элементов массива A ‟); for   i:=1      to         n          do

93

for     j:=1       to     m     do        read (а[i,j]); writeln(„Вывод элементов массива В ‟); for j:=1      to          m          do

Задание

1.   Изучить лекционный материал и методические рекомендации для выполнения задания.

2.   Разработать алгоритм решения задачи.

3.   Составить программу на алгоритмическом языке Pascal.

4.            Выполнить      отладку     и     тестирование     программы     на компьютере.

5.            Подготовить      отчет     о     выполнении     задания.    Пример оформления отчета представлен в приложении 2.

6.   Подготовить ответы на контрольные вопросы.

Варианты заданий

94

95

96

97

98

Контрольные вопросы

1.   Что такое массив?

2.   Что такое индекс массива?

3.   Что такое размерность массива?

4.   Как различить одномерные и двумерные массивы?

5.   Как осуществляется ввод/вывод элементов матрицы?

Скачано с www.znanio.ru