Нулевые элементы в матрице целых чисел расположенные ниже главной диагонали.
Выбор метода
Во внутреннем представлении массива нет необходимости сохранять нулевые (фоновые) элементы, такие, что: M [x, y] = 0 при x < y.
Если исключить нулевые элементы по сохранению и представить матрицу в виде одномерного массива, то формула линиаризации (перехода от двухкоординатной обращения к одно координатного) запишется как:
j = СУММА [i = от 1 до y-1] (XM-(и-1)) + x-(y-1)
где x, y - номера столбца и строки соответственно; XM - число элементов в строке.
Текст программы
Program LAB2;
uses DataStr;
Var
arru: array [1 .. 100,1 .. 100] of integer; {Полная таблица}
arrp: array [1 .. 5050] of integer; {Сжатая таблица}
XM: integer; {Максимальные индексы в таблице}
{==== Функция пересчета индексов ====}
{Y, x - индексы в 2-мерном массиве. Функция возвращает индекс в 1-мерном массиве}
Function NewIndex (y, x: integer): integer;
var i, d: integer;
begin
d: = 0;
for i: = 1 to y-1 do d: = d + XM-i +1;
NewIndex: = d + x-y +1; end;
{==== Запись в краткое представление массива ====}
{Y, x - индексы в 2-мерном массиве, value - записываемое значение. Функция возвращает}
{Записываемое значение или - 0, если (x, y) задают индексы фонового элемента. }
Function PutTab (y, x, value: integer): integer;
begin
if x <y then PutTab: = 0
else begin
arrp [NewIndex (y, x)]: = value;
PutTab: = value; end;
end;
{==== Функция выборки из краткого представления массива ====}
{Y, x - индексы в 2-мерном массиве. Функция возвращает вилайливе значение}
Function GetTab (y, x: integer): integer;
begin
if x <y then GetTab: = 0
else GetTab: = arrp [NewIndex (y, x)];
end;
{============= Главная программа ===================}
Var
x, y: integer; {Индексы в 2-мерном массиве}
k, h: integer;
Моменты времени
tar1, tar2, taw1, taw2: longint;
tbr1, tbr2, tbw1, tbw2: longint;
begin
{===== Часть 1. Проверка формирования массива ======}
XM: = 10;
{Запись элементов в 1-мерный массив}
k: = 1;
for y: = 1 to XM do
for x: = y to XM do begin
h: = PutTab (y, x, k); k: = k +1;
end;
{Распечатка матрицы}
writeln ('===== Матрица =====');
for y: = 1 to XM do begin
for x: = 1 to XM do write (GetTab (y, x): 3);
writeln;
end;
{Распечатка внутреннего представления матрицы}
writeln ('===== Матрица (внутреннее представление) =====ь);
for y: = 1 to 55 do write (arrp [y]: 4);
writeln; writeln;
{========= Часть 2. Хронометраж ================}
XM: = 100;
{Заполнение нулями 2-мерного массива}
for y: = 1 to XM do
for x: = 1 to XM do arru [y] [x]: = 0;
{Запись элементов в 2-мерный массив}
k: = 1;
taw1: = GetTic;
for y: = 1 to XM do
for x: = y to XM do begin
arru [y] [x] = k; k: = k +1;
end;
taw2: = GetTic;
{Выборка элементов из 2-мерного массива}
tar1: = GetTic;
for y: = 1 to XM do
for x: = 1 to XM do h: = arru [y] [x];
tar2: = GetTic;
{Запись элементов в 1-мерный массив}
k: = 1;
tbw1: = GetTic;
for y: = 1 to XM do
for x: = y to XM do begin
h: = PutTab (y, x, k); k: = k +1;
end;
tbw2: = GetTic;
{Выборка элементов с 1-мерного массива}
tbr1: = GetTic;
for y: = 1 to XM do
for x: = 1 to XM do h: = GetTab (y, x);
tbr2: = GetTic;
{Печать результатов хронометража}
writeln ('полнодоступная вариант (запись)');
writeln ('Начало -', taw1);
writeln ('Конец -', taw2);
writeln ('полнодоступная вариант (чтение)');
writeln ('Начало -', tar1);
writeln ('Конец -', tar2);
writeln;
writeln ('Краткий вариант (запись)');
writeln ('Начало -', tbw1);
writeln ('Конец -', tbw2);
writeln ('Краткий вариант (чтение)');
writeln ('Начало -', tbr1);
writeln ('Конец -', tbr2);
end.
Результат работы программы
===== Матрица =====
1 2 3 4 5 6 7 8 9 10
0 11 12 13 14 15 16 17 18 19
0 0 20 21 22 23 24 25 26 27
0 0 0 28 29 30 31 32 33 34
0 0 0 0 35 36 37 38 39 40
0 0 0 0 0 41 42 43 44 45
0 0 0 0 0 0 46 47 48 49
0 0 0 0 0 0 0 50 51 52
0 0 0 0 0 0 0 0 53 54
0 0 0 0 0 0 0 0 0 55
===== Матрица (внутр.представлення) =====
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55
Полнодоступная вариант (запись)
Начало - 1050209
Конец - 1050210
Полнодоступная вариант (чтение)
Начало - 1050210
Конец - 1050211
Краткий вариант (запись)
Начало - 1050211
Конец - 1050229
Краткий вариант (чтение)
Начало - 1050229
Конец - 1050247
