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)//если не дошли до правой границы - сдвигаемся вправо
43 else
44 begin//иначе - прошли нижнюю строку
45 direction:= up;//сменим направление на "вверх"
46 dec(bottomB);//сдвинем нижнюю границу к центру
47 dec(RowN);//сдвинемся вверх
48 end;
49
50 up://если вверх
51 if RowN > topB then dec(RowN)//если не дошли до верхней границы - сдвигаемся вверх
52 else
53 begin//иначе - прошли правый столбец
54 direction:= left;//сменим направление на "влево"
55 dec(rightB);//сдвинем правую границу к центру
56 dec(ColN);//сдвинемся влево
57 end;
58
59 left://если влево
60 if ColN > leftB then dec(ColN)//если не дошли до левой границы - сдвигаемся влево
61 else
62 begin//иначе - прошли верхнюю строку
63 direction:= down;//сменим направление на "вниз"
64 inc(topB);//сдвинем верхнюю границу к центру
65 inc(RowN);//сдвинемся вниз
66 end;
67 end;
68 end;
69 end;
Сортировка строк матрицы
Наконец упорядочивание строк матрицы по убыванию суммы элементов каждой строки. Вспомогательная функция getRowSum возвращает сумму элементов заданной строки:
1 {возвращает сумму элементов RowN-ой строки матрицы arr}
2 function getRowSum(const arr: TMatrix; RowN: integer): Int64;
3 var ColN: integer;
4 begin
5 Result:= 0;
6 if RowN > high(arr) then exit;//если в матрице нет RowN-ой строки - выходим
7 for ColN:= 0 to high(arr[RowN]) do//суммируем элементы строки
8 Result:= Result + arr[RowN, ColN];
9 end;
Сама сортировка осуществляется посредством процедуры SortRows. Был выбран алгоритм прямой вставки, так как число строк в матрице не предполагается большим, а этот алгоритм эффективен на небольших наборах данных. В любом случае сортировка осуществляется быстро, так как при перемене мест строк не происходит копирование данных, но просто переставляются местами указатели. Листинг этой функции:
1 {сортирует строки матрицы по убыванию сумм элементов каждой строки}
2 procedure SortRows(var arr: TMatrix);
3 var
4 i, k: integer;//переменные для алгоритма сортировки
5 tmpRow: TVector;//временная переменная для алгоритма сортировки
6 begin
7 //алгоритм сортировки методом прямой вставки
8 for i:= 1 to high(arr) do
9 begin//для строк с первой по последнюю
10 k:= i;//начиная с текущей строки
11 while (k > 0) and (getRowSum(arr, k) > getRowSum(arr, k-1)) do
12 begin//пока не дошли до нулевой строки, и сумма строки над текущей строкой больше текущей суммы
13 swap(arr[k-1], arr[k]);//поменяем текущую строку и строку над ней местами
14 dec(k);//сдвинемся вверх
15 end;
16 end;
17 end;
- Введение
- 1. Теоретическая часть
- 1.1 Общее понятие о массивах
- 1.1.1 Определение и область применения
- 1.1.2 Специфические типы массивов
- 1.1.3 Реализация массивов
- 1.1.4 Достоинства массивов
- 1.1.5 Недостатки массивов
- 1.2 Массивы в Object Pascal
- 1.2.1 Статические массивы
- 1.2.2 Динамические массивы
- 1.2.3 Функции для работы с массивами
- 2. Практическая часть
- 2.1 Постановка задачи
- 2.3 Описание модулей
- 2.3.1 Модуль MatrixOperations
- 2.3.2 Модуль fileIO
- 3. Эксплуатационная документация
- 3.1 Описание применения
- 3.2 Руководство оператора
- Выводы