Работа с двумерными числовыми массивами (стр. 2 из 5)
1.3 Использование массивов в рамках данного проекта
Работа со статическими массивами более проста и менее затратна в плане использования ресурсов компьютера, но так как в задании нигде не оговариваются конкретные размеры исходных матриц, то было принято решение построить программу ну основе использования динамических массивов.
Приложение построено таким образом, что размер используемой матрицы можно менять во время выполнения, так же он автоматически определяется при загрузке исходных данных из файла. Размеры динамических массивов внутри программы изменяются соответствующим образом автоматически.
2. Практическая часть
2.1 Постановка задачи
Приложение предназначено для выполнения специфической обработки матриц. Исходные матрицы должны загружаться из файла, либо вводиться непосредственно в элементы интерфейса приложения.
Граничные условия на вводимые данные таковы:
· Размеры матрицы должны лежать в пределах [1; 2147483647]. Если введено число, выходящее из этого диапазона, либо значение, не являющееся целым числом, то размер устанавливается равным единице.
· Элементы матрицы должны лежать в пределах [-2147483648; 2147483647]. Если какой-то из элементов лежит вне этого диапазона, либо введёно значение, не являющееся целым числом, то элемент устанавливается равным нулю.
· В заданиях, связанных с подсчётом сумм элементов, результат может лежать в пределах [-9223372036854775808; 9223372036854775807]. Если сумма выходит за эти пределы, результат не определён.
2.2 Функциональная структура программы
Программа разделена на три модуля:
MatrixOperations – различные операции с матрицей
fileIO – сохранение матрицы в файл/ чтение матрицы из файла
form – форма приложения, процедуры обмена данными между массивами и элементами формы. Структура связей модулей такова:
2.3 Описание модулей
2.3.1 Модуль MatrixOperations
Это основной модуль программы, содержащий процедуры для выполнения матричных операций, предусмотренных заданием.
Определяет повсеместно используемые типы «матрица» и «вектор»:
1 type
2 TVector = array of integer;
3 TMatrix = array of TVector;
Поиск максимальных элементов в матрице.
Процедура GetMaxVals, которая, перебирая все строки матрицы, находит в каждой максимальный элемент, записывает его значение в массив maxVal, а его номер столбца в массив maxValCol. Предварительно процедура выделяет необходимую намять для этих массивов. Листинг:
1 {
2 формирует массив максимальных элементов maxVal и массив номеров столбцов,
3 содержащих максимальные элементы maxValCol на основе матрицы arr
4 }
5 procedure GetMaxVals(var maxVal, maxValCol: TVector; const arr: TMatrix);
6 var
7 RowN, ColN, maxInRow: integer;
8 begin
9 //выделим необходимый для каждого массива объём памяти
10 SetLength(maxVal, high(arr)+1);
11 SetLength(maxValCol, high(arr)+1);
12 for RowN:= low(arr) to high(arr) do
13 begin//для каждой строки
14 maxVal[RowN]:= low(integer);//по умолчанию максимальное значение -2147483648
15 maxValCol[RowN]:= -1;//по умолчанию номер столбца с макс элементом -1
16 for ColN:= low(arr[RowN]) to high(arr[RowN]) do
17 begin//для каждого столбца
18 if arr[RowN, ColN] > maxVal[RowN] then
19 begin//если элемент больше макс значения, то
20 maxVal[RowN]:= arr[RowN, ColN];//максимальное значение приравняем элементу
21 maxValCol[RowN]:= ColN;//номер столбца приравняем текущему столбцу
22 end;
23 end;
24 end;
25 end;
Суммы элементов между диагоналями
Далее идут функции, осуществляющие подсчёт сумм элементов выше и ниже пересечения диагоналей, а так же смену местами этих элементов. Главной диагональю считается множество элементов матрицы, индексы которых совпадают, побочной диагональю считается та, которая идёт по диагонали из нижнего левого угла матрицы.
Функции GetSumAbove и GetSumBelow проходят соответствующие половины строк матрицы, для каждой строки высчитывая диапазон столбцов, из которых нужно суммировать элементы:
1 {возвращает сумму элементов выше пересечения диагоналей матрицы arr}
2 function GetSumAbove (const arr: TMatrix): Int64;
3 var
4 RowN, ColN: integer;
5 lastColumn: integer;//номер столбца, содержащего элемент дальней диагонали минус 1
6 begin
7 Result:= 0;
8 for RowN:= 0 to (high(arr) div 2) do
9 begin//с нулевой, по средюю строку
10 lastColumn:= high(arr)-RowN-1;//определим номер столбца последнего элемента, подлежащего суммированию
11 //если число столбцов меньше числа строк, то последний столбец может оказаться ближе
12 if lastColumn > high(arr[RowN]) then lastColumn:= high(arr[RowN]);
13 for ColN:= RowN+1 to lastColumn do //просуммируем элементы в высчитаных пределах
14 Result:= Result + arr[RowN, ColN];
15 end;
16 end;
17 {возвращает сумму элементов ниже пересечения диагоналей матрицы arr}
18 function GetSumBelow(const arr: TMatrix): Int64;
19 var
20 RowN, ColN: integer;
21 lastColumn: integer;//номер столбца, содержащего элемент дальней диагонали минус 1
22 begin
23 Result:= 0;
24 for RowN:= (high(arr) div 2)+1 to high(arr) do
25 begin//со средней по последнюю строку
26 lastColumn:= RowN-1;//определим номер столбца последнего элемента, подлежащего суммированию
27 //если число столбцов меньше числа строк, то последний столбец может оказаться ближе
28 if lastColumn > high(arr[RowN]) then lastColumn:= high(arr[RowN]);
29 for ColN:= high(arr)-RowN+1 to lastColumn do //просуммируем элементы в высчитаных пределах
30 Result:= Result + arr[RowN, ColN];
31 end;
32 end;
Процедура SwapAboveBelow таким же образом, как функция GetSumAbove, определяет, какие элементы лежат выше пересечения диагоналей, но не суммирует их, а каждый меняет местами с элементом того же столбца, симметричным текущему относительно верхней и нижней границ матрицы. Для смены используется вспомогательная процедура swap для целых чисел, определённая в этом же модуле:
1 {вспомогательная процедура: поменять местами два целых числа}
2 procedure swap(var first, second: integer);
3 var tmp: integer;
4 begin
5 tmp:= first;
6 first:= second;
7 second:= tmp;
8 end;
9 {поменять местами элементы выше и ниже пересечения диагоналей матрицы arr}
10 procedure SwapAboveBelow (var arr: TMatrix);
11 var
12 RowN, ColN: integer;
13 lastColumn: integer;//номер столбца, содержащего элемент дальней диагонали минус 1
14 begin
15 for RowN:= 0 to (high(arr) div 2) do
16 begin//с нулевой, по средюю строку
17 lastColumn:= high(arr)-RowN-1;//определим номер столбца последнего элемента, подлежащего суммированию
18 //если число столбцов меньше числа строк, то последний столбец может оказаться ближе
19 if lastColumn > high(arr[RowN]) then lastColumn:= high(arr[RowN]);
20 for ColN:= RowN+1 to lastColumn do//для каждого элемента в высчитаных пределах
21 //поменяем его местами с элементом того же столбца, отстаящем на то же число строк, но от нижней границы матрицы
22 swap(arr[RowN, ColN], arr[high(arr) - RowN, ColN]);
23 end;
24 end;
Циклический сдвиг строк
Далее функция CircuarShift, осуществляющая циклический сдвиг строк матрицы вверх, или вниз. Направление сдвига определяется булевым параметром shiftUp, передаваемым процедуре:
1 {
2 осуществляет циклический сдвиг строк матрицы arr вверх при shiftUp = true,
3 и вниз, при shiftUp = false
4 }
5 procedure CircuarShift(var arr: TMatrix; shiftUp: boolean);
6 var
7 RowN: integer;
8 tmpRow: TVector;//временная переменная для хранения строки иатрицы
9
10 begin
11
12 if high(arr) < 1 then exit;//если в матрице меньше двух строк - выходим
13 if shiftUp then
14 begin//если сдвиг вверх
15 tmpRow:= arr[high(arr)];//сохраним последнюю строку матрицы
16 arr[high(arr)]:= arr[0];//приравняем последнюю строку первой
17 for rowN:= 0 to high(arr)-2 do
18 begin//для строк с нулевой по пред-предпоследнюю
19 arr[rowN]:= arr[rowN+1];//текущая строка равна нижней
20 end;
21 arr[high(arr)-1]:= tmpRow;//предпоследнюю строку приравняем последней
22 end
23 else
24 begin//иначе, если сдвиг вниз
25 tmpRow:= arr[0];//сохраним нулвую строку
26 arr[0]:= arr[high(arr)];//приравняем нулевую строку последней
27 for rowN:= high(arr) downto 2 do
28 begin//для строк с последней по вторую
29 arr[RowN]:= arr[RowN-1];//текущая строка равна верхней
30 end;
31 arr[1]:= tmpRow;//первую строку приравняем нулевой
32 end;
33 end;
«Разворачивание» матрицы
Процедура UnwindMatrix осуществляет "разворачивание" матрицы в одномерный массив против часовой стрелки. Эта процедура в своих локальных переменных хранит координаты текущего элемента, текущее направление обхода (посредством перечислимого типа TDirection), а так же границы ещё не обойдённой части матрицы, которые сужаются каждый раз, когда проходится целая строка, или столбец. В этот же момент меняется направление обхода и текущим становится элемент в этом направлении. Обход завершается, когда число пройденных элементов станет равняться количеству элементов в матрице:
1 //перечисление - направления
2 type TDirection = (down, right, up, left);
3
4 {обходит матрицу arr против часовой стрелки и наполняет элементами массив res}
5 procedure UnwindMatrix(const arr: TMatrix; var res: TVector);
6 var
7 count, cur: integer;//число элементов в матрице и счётчик элементов
8
9 RowN, ColN: integer;
10 leftB, bottomB, rightB, topB: integer;//границы обхода - меняются при проходе полной строки или столбца
11 direction: TDirection;//текущее направление обхода
12
13 begin
14 if (length(arr) = 0) or (length(arr[0]) = 0) then exit;//если в матрице нет элементов - выходим
15 count:= length(arr) * length(arr[0]);//подсчитаем число элементов в матрице
16 SetLength(res, count);//выделим память для хранения всех элементов матрицы
17
18 //начальные условия обхода: текущий элемент [0,0], границы совпадают с граниуцами матриы, направление - вниз
19 direction:= down;
20 RowN:= 0;
21 ColN:= 0;
22 leftB:= 0;
23 bottomB:= high(arr);
24 rightB:= high(arr[0]);
25 topB:= 0;
26
27 for cur:= 0 to count-1 do
28 begin//пока не пройдём count элементов
29 res[cur]:= arr[RowN, ColN];//добавляем текущий элемент в массив
30 //дальненйшие действия зависят от текущего направления обхода
31 case direction of
32 down://если вниз
33 if RowN < bottomB then inc(RowN)//если не дошли до нижней границы - сдвигаемся вниз
34 else
35 begin//иначе - прошли левый столбец
36 direction:= right;//сменим направление на "вправо"
37 inc(leftB);//сдвинем левую границу к центру
38 inc(ColN);//сдвинемся вправо
39 end;
40
41 right://если вправо
42 if ColN < rightB then inc(ColN)//если не дошли до правой границы - сдвигаемся вправо