p align="left">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//для строк с первой по последнюю
Страницы: 1, 2, 3, 4, 5
|