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;