unit Matrix модуль Matrix Здесь описываются функции для работы матрица

  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
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
unit Matrix; // модуль Matrix
{
Здесь описываются функции для работы с матрицами (сложение, вычитание, умножение, ...)
}
interface // интерфейсная часть;
type MyMatrix = class
{
Класс для работы с матрицами MyMatrix
Ниже описаны зоны видимости:
private - приватная зона видимости. Это значит, что все переменные и функции, описанные в области могут использоваться ТОЛЬКО внутри класса MyMatrix.
К ним не получить доступ извне. Например, MyMatrix.matrix - вызовет ошибку (что-то по типу undefined index, но хз как именно в паскале)
public - публичная зона видимости. Это значит, что ко всем переменным и функциям, описанным в этой области можно получить доступ извне. Что и используется в программе.
}
private
{
List - это тоже класс, встроенный в компилятор.
Здесь впервые встречается List. В кратце опишу что это. Представляет список на базе динамического массива.
Это тип данных, похожий на динамический массив, но имеет несколько отличий. По функционалу похож на линковый стэк.
Приведу пример, допустим нужно сделать список с название list, размерностью 4 и значениями: 1, 2, 4, 3.
Если бы это был простой массив в Pascal, то пришлось бы написать следующее:
var list: array of ineger;
SetLength(list, 4);
list[0] := 1;
list[1] := 2;
list[2] := 4;
list[3] := 3;
Тоже самое, но с использованием списка:
var list: List<integer>; // указываем переменной list тип данных - List<integer>.
list := new List<integer>(); // создаем пустой лист без размерности (0).
list.Add(1); // добавляем в список значение, и автоматически увеличиваем размерность листа на 1
list.Add(2); // добавляем в список значение, и автоматически увеличиваем размерность листа на 1
list.Add(4); // добавляем в список значение, и автоматически увеличиваем размерность листа на 1
list.Add(3); // добавляем в список значение, и автоматически увеличиваем размерность листа на 1
Это удобно тем, что не нужно указывать индекс при добавлении, а также заранее указывать размерность, т.к. в любой момент мы можем добавить или удалить элемент.
Получить доступ к элементу можно как и из обычного массива:
writeln(list[2]); // вернет 4. (в точности, как в строке 26)
}
matrix: List<List<integer>>; // создаем переменную для матрицы, которая будет создаваться при вызове класса MyMatrix с типом данных - двумерный список
indices: List<integer>; // создаем переменную для хранения индексов массивов (это те самые цифры над матрицей, номера элементов и т.д.)
matrix_size: integer; // переменная, которая хранит размерность матрицы
function GetValue(x, y: integer): integer; // функция (заголовок) для получения значение из матрицы по переданным индексам x и y
procedure SetValue(x, y: integer; value: integer); // функция (заголовок) для изменения значения в матрице по переданным индексам x и y
public
{
Здесь используется понятие конструктор, логика такая же как и в c++/c#/java
При создании экземпляра Класса MyMatrix будет вызван конструктор.
Помимо этого, здесь используется прием - перегрузка функции, 4 строчки ниже - перегрузка констуктора.
Что такое перегрузка и для чего она нужна?
Допустим, есть функция sum(a, b: integer) ..., которая складывает переданные ей целочисленные значения a и b.
Если передать в эту функцию a, b: float, тогда возникнет ошибка.
Но не писать же новую функцию sum_float, например?
Для этого создается функция с точно таким же названием, в данном случае sum(a, b: float) и в ней производится такая же операция сложения.
Конструкторы ниже перегружены, ниже описание в каком случае какой конструктор
}
constructor Create(obj: MyMatrix); // конструктор, если передана матрица (например, когда нужно менять в матрице элементы местами, передается уже заполненная матрица)
constructor Create(size: integer); // конструктор, если передан размер матрицы
constructor Create(path: string); // конструктор, если передан путь к файлу с матрицей
constructor Create(count_cell, plate_columns: integer); // конструктор, если переданы размеры платы - например, 4х3
{
property - свойство.
property Size - свойство, в котором будет храниться размерность матрицы экземпляра класса.
property Size : integer - тип данных этого свойства - целочисленное.
property Size : integer read matrix_size; - read matrix_size означает, что при попытке чтения это переменной, выведется значение из matrix_size.
Т.к. matrix_size находится в приватной зоне видимости, то получить доступ напрямую к нему вне класса нельзя. Для этого создается свойство, которое указывает на эту переменную.
Переменная matrix_size задается внизу каждого из конструкторов.
Например, есть матрица R, если написать R.Size - вернет ее размерность
Value - свойство для получения значения из матрицы по указанным индексам x,y.
read GetValue - при попытке чтения (read) вызывает функцию getValue(x, y: integer);
write SetValue - при попытке записи (write) вызывает функцию SetValue(x, y: integer, value: integer);
Опять же, из-за того, что значения матрицы внутри класса получить извне нельзя, для этого написаны функции внутри класса, которые читают/записывают значения в матрице.
На примере матрицы R.
R[0][1] - вызовет getValue(0, 1);
R[0][1] := 12; - вызовет SetValue(0, 1, 12);
Но это только в случае, если R является экземпляром класса MyMatrix;
}
property Size: integer read matrix_size; // свойство size
property Value[x, y: integer]: integer read GetValue write SetValue; default; // свойство value
class function operator+(a, b: MyMatrix): MyMatrix; // перегрузка оператора сложения для двух матриц
class function operator*(a, b: MyMatrix): MyMatrix; // перегрузка оператора умножения для двух матриц
function Transpose(): MyMatrix; // заголовок функции транспонирования
function DiagonalAmount(): integer; // заголовок функции нахождения диагональной суммы
function Gamma(): MyMatrix; // заголовок функции нахождения гаммы для матрицы
function Mins(): List<(integer, integer)>; {функция нахождения матрицы L ()}
function Swap(a, b: integer): MyMatrix; // заголовок функции перестановки элементов местами
function ToList(): List<List<integer>>; // заголовок функции, возвращающей матрицу в виде листа
function ToString(): string; override; // заголовок функции, возвращающей матрицу в виде строки (для вывода в виде текста)
function ToHalfString(): string; // // заголовок функции, возвращающей матрицу в виде строки треугольником (ну, типо отсекает одинаковые значения в матрице)
end;
implementation // исполняемая часть - здесь находится код всех функций, описанных выше;
constructor MyMatrix.Create(obj: MyMatrix);
{
Конструктор для заполнения матрицы obj: MyMatrix
Передается экземпляр класса MyMatrix - obj.
Например, это уже заполненная матрица R, которая объявлена как экземпляр класса MyMatrix.
Как итог, скопирует данные из матрицы R.
}
begin
{
Идентификаторы:
x, y - используются для хранения итераций циклов;
}
self.matrix := new List<List<integer>>(); // создаем пустой двумерный лист, который будет хранить матрицу
self.indices := new List<integer>(); // создаем пустой лист, который будет хранить индексы матрицы (номера элементов над матрицей)
for var y := 0 to obj.Size - 1 do begin // цикл от 0 до размерности матрицы - 1 (т.к. все динамические структуры данных начинаются с нуля)
self.matrix.Add(new List<integer>());
self.indices.Add(obj.indices[y]);
for var x := 0 to obj.Size - 1 do begin
self.matrix[y].Add(obj[x, y]);
end;
end;
self.matrix_size := obj.Size;
end;
constructor MyMatrix.Create(size: integer);
{
конструктор для заполнения если передан размер матрицы
}
begin
{
Идентификаторы:
x, y - используются для хранения итераций циклов;
}
// self - это указатель на текущий экземпляр класса. В интерфейсе были описаны переменные и функции
self.matrix := new List<List<integer>>(); // создаем пустой двумерный лист для матрицы
self.indices := new List<integer>(); // создаем пустой двумерный лист для номеров элементов
{цикл ниже создает пустую матрицу переданной размерности size и заполняет список номеров элементов}
for var y := 0 to size - 1 do begin // цикл от 0 до size - 1 (размерность матрицы)
self.matrix.Add(new List<integer>()); // добавляем на каждой итерации цикла пустой лист в матрицу
self.indices.Add(y + 1); // добавляем на каждой итерации цикла в список номеров элементов значение y + 1 ()
for var x := 0 to size - 1 do begin // цикл от 0 до size - 1 (размерность матрицы)
self.matrix[y].Add(0); // заполняем вложенный список нулями
end; // конец цикла
end; // конец цикла
self.matrix_size := size; // устанавливаем приватной переменной matrix_size локальное значение size
end;
constructor MyMatrix.Create(path: string);
{конструктор для заполнения если передан путь к файлу}
begin
{
Идентификаторы:
text - используется для хранения данных из файла;
line - используется для хранения строки из файла
count - используется для подсчета количества строк в файле (это будет являться размерностью матрицы)
}
matrix := new List<List<integer>>(); // создаем пустой двумерный лист для матрицы
self.indices := new List<integer>(); // создаем пустой двумерный лист для номеров элементов
var text: PABCSystem.Text; // используется для хранения данных из файла
assign(text, path); // связываем дескриптор файла с переменной text
reset(text); // открываем файл для чтения
var count := 0; // используется для подсчета количества строк в файле (это будет являться размерностью матрицы)
while not eof(text) do begin // цикл от нуля, до конца файла (eof(text) - это конец файла)
var line := ReadLnString(text); // используется для хранения строки из файла
if (line.Length > 0) then begin // условие, если длина строки > 0
{строчку ниже можно расписать так:
value := line.Split(' ').Select(i -> StrToInt(i)).ToList();
Split это встроенная функция, она разбивает строку на массив используя разделитель
Конкретно в этом случае, она разбивает строку
0 1 2 3 4 5 6
на массив
[0, 1, 2, 3, 4, 5, 6]
Функция Select - тоже встроенная, она применяется к массивам. Вкратце, она перебирает массив поэлементно и делает операцию (i -> StrToInt(i))
В данном случае, она преобразовывает строку '0' в целочисленное значение 0, и так для каждого элемента.
После чего используется
ToList() - это встроенная функция, используется для преобразования массива в список (т.к. у нас везде используется список, это необходимо)
matrix.Add(value); // и в самом конце, с помощью метода(функции) встроенной в класс List - .Add() мы добавляем результат в наш список
}
matrix.Add(line.Split(' ').Select(i -> StrToInt(i)).ToList());
self.indices.Add(count + 1); // добавляем в список индексов новый индекс на каждой итерации + 1
count := count + 1; // увеличиваем счетчик на 1. Кстати, можно писать inc(count); только что об этом узнал
end;
end;
close(text); // закрываем файл
self.matrix_size := matrix.Count; // устанавливаем приватной переменной matrix_size значение размерности полученной матрицы
end;
constructor MyMatrix.Create(count_cell, plate_columns: integer);
{конструктор для заполнения если передано количество элементов и количество строк платы, используется для вычисления матрицы D}
begin
{
Идентификаторы:
count_cell - количество элементов на плате
plate_columns - количество строк в плате
x, y - используются для хранения итераций циклов;
pos1, pos2 - используются для хранения
}
matrix := new List<List<integer>>(); // тоже самое, как и выше
self.indices := new List<integer>(); // тоже самое, как и выше
for var y := 0 to count_cell - 1 do begin // цикл от 0 до количества элементов платы - 1
matrix.Add(new List<integer>()); // все как и раньше
self.indices.Add(y + 1); // добавляем в список индексов новый индекс (y + 1) на каждой итерации
for var x := 0 to count_cell - 1 do begin // цикл от 0 до количества элементов платы - 1
{
Тут рассчет расстояний, вкратце - как он сделан
div - целочисленное деление, пример:
55 div 6 = 9 (деление, при котором остаток отбрасывается)
52 div 7 = 7 (деление, при котором остаток отбрасывается)
div - получение остатка от деления, пример:
55 mod 6 = 1 (55 - 54)
52 mod 7 = 3 (52 - 49)
Соответственно - переменные pos1 и pos2 это массивы, которые хранят значения:
pos1[0] := y div plate_columns;
pos1[1] := y mod plate_columns;
pos2[0] := x div plate_columns;
pos2[1] := x mod plate_columns;
Функция abs - встроенная в паскаль, считает модуль переданного числа.
Получаем сумму модуля разницы pos1[0] - pos2[0] И pos1[1] - pos2[1]).
И так на каждой итерации рассчитывается расстояния каждого элемента к каждому в зависимости от заданного кол-ва столбцов платы (plate_columns)
abs(pos1[0] - pos2[0]) + abs(pos1[1] - pos2[1]) - рассчитанное значение
}
var pos1 := (y div plate_columns, y mod plate_columns);
var pos2 := (x div plate_columns, x mod plate_columns);
matrix[y].Add(abs(pos1[0] - pos2[0]) + abs(pos1[1] - pos2[1])); // добавляем в матрицу рассчитанное значение
end;
end;
self.matrix_size := matrix.Count; // устанавливаем приватной переменной matrix_size значение размерности полученной матрицы
end;
function MyMatrix.GetValue(x, y: integer): integer;
{функция для получения значения из матрицы}
begin
result := self.matrix[y][x];
end;
procedure MyMatrix.SetValue(x, y: integer; value: integer);
{функция для изменения значения из матрицы}
begin
self.matrix[y][x] := value;
end;
class function MyMatrix.operator+(a, b: MyMatrix): MyMatrix;
{перегрузка оператора сложения для матриц}
begin
{
a.Size
у a и b указан тип данных - MyMatrix
}
var res := new MyMatrix(a.Size);
for var y := 0 to a.Size - 1 do begin
for var x := 0 to a.Size - 1 do begin
res[x, y] := a[x, y] + b[x, y];
end;
end;
result := res;
end;
class function MyMatrix.operator*(a, b: MyMatrix): MyMatrix;
{перегрузка оператора умножения для матриц}
begin
var res := new MyMatrix(a.Size);
// создаем новую матрицу и передаем в нее размер матрицы a. (то есть res - экземпляр класса MyMatrix)
// вызовется конструктор с size
for var y := 0 to a.Size - 1 do begin
for var x := 0 to a.Size - 1 do begin
for var z := 0 to a.Size - 1 do begin
res[x, y] := res[x, y] + a[z, y] * b[x, z]; // тупо перемножение
end;
end;
end;
result := res;
end;
function MyMatrix.Transpose(): MyMatrix;
{функция транспонирования матрицы}
begin
var res := new MyMatrix(self);
{
res - это экземпляр класса MyMatrix;
Здесь вызывается самый первый конструктор, в него передается текущая матрица и она копируется в переменную res.
А дальше она транспонируется, то есть res[x][y] := res[y][x];
}
for var y := 1 to matrix_size - 1 do begin
for var x := 0 to y - 1 do begin
res[x, y] := res[x, y] xor res[y, x];
res[y, x] := res[x, y] xor res[y, x];
res[x, y] := res[x, y] xor res[y, x];
end;
end;
result := res;
end;
function MyMatrix.DiagonalAmount(): integer;
{функция нахождения диагональной суммы}
begin
var sum := 0;
for var i := 0 to self.matrix_size - 1 do begin
sum += self[i,i];
end;
// Round(); - функция округления, возвращает целочисленное число
result := Round(sum / 2);
end;
function MyMatrix.Gamma(): MyMatrix;
{функция нахождения матрицы Gamma}
begin
var res := new MyMatrix(self);
for var y := 0 to res.Size - 1 do begin
var tmp := res[y, y];
for var x := 0 to res.Size - 1 do begin
res[x, y] := res[x, y] - tmp;
end;
end;
result := res;
end;
function MyMatrix.Mins(): List<(integer, integer)>;
{функция нахождения минимальных элементов в матрице L ()}
begin
{
Здесь происходит разветвление алгоритма, в случае, если в матрице L нашлось два и более одинаковых минимальных элемента
(Например -8 -8 -8), тогда функция вернет список mins, содержащий номера элементов для перестановки
}
var mins := new List<(integer, integer)>();
var min := -1; // считаем, что наименьший элемент равен -1
for var y := 0 to self.Size - 1 do begin // цикл от 0 до размерности матрицы L - 1
for var x := y to self.Size - 1 do begin // цикл от 0 до размерности матрицы L - 1
if (self[x, y] < min) then begin // условие, если текущий элемент матрицы меньше чем min
mins.Clear(); // значит очищаем список минимальных элементов (тех, что будем менять) (Вызывает функцию Clear() встроенную в класс List (она очищает лист))
min := self[x, y]; // и присваиваем минимальной значение переменной min
end;
if (self[x, y] = min) then begin // если текущее значение матрицы равно минимальному
mins.Add((x, y)); // то добавляем его в массив минимальных
end;
end;
end;
result := mins; // возвращаем список минимальных элементов
end;
function MyMatrix.Swap(a, b: integer): MyMatrix;
{
функция перестановки элементов местами
использует XOR операцию
Пример:
a := 2;
b := 3;
чтобы присвоить переменной a значение 3, а после присвоить b значение 2 нужно либо использовать третью переменную:
temp := a;
a := b;
b := temp;
Либо использовать xor операцию:
a := a xor b
b := a xor b
a := a xor b
}
begin
var res := new MyMatrix(self);
res.indices[a] := res.indices[a] xor res.indices[b];
res.indices[b] := res.indices[a] xor res.indices[b];
res.indices[a] := res.indices[a] xor res.indices[b];
for var i := 0 to res.Size - 1 do begin
res[a, i] := res[a, i] xor res[b, i];
res[b, i] := res[a, i] xor res[b, i];
res[a, i] := res[a, i] xor res[b, i];
res[i, a] := res[i, a] xor res[i, b];
res[i, b] := res[i, a] xor res[i, b];
res[i, a] := res[i, a] xor res[i, b];
end;
result := res;
end;
function MyMatrix.ToList(): List<List<integer>>;
begin
// просто возвращает матрицу в виде двумерного листа
result := self.matrix;
end;
function MyMatrix.ToString(): string;
begin
// возвращает матрицу в виде строки, нужна для "красивой" отрисовки матрицы в окошко результата
var res: string;
for var y := -1 to self.Size - 1 do begin // цикл от -1 до размерности матрицы - 1
if (y = -1) then begin // если это первая итерация цикла, тогда
res += ' '; // добавляем в начале три пробела
end else begin // в противном случае
if (indices[y].ToString().Length = 1) then begin // если длина индекса равна 1
res += ' ' + indices[y] + '|'; // пишем пробел + индекс |
end else begin // в противном случае
res += indices[y] + '|'; // пишем индекс |
end;
end;
for var x:=0 to self.Size - 1 do begin // цикл перебора матрицы от 0 до размера матрицы - 1
var tmp := ''; // временная переменная
if (y = -1) then begin // если это первая итерация цикла, тогда
tmp := indices[x].ToString() // временная переменная хранит индекс в виде строки
end else begin // в противном случае
tmp := self[x, y].ToString();// временная переменная хранит число из матрицы в виде строки
end;
{
это оператор вывода
вкратце, этот код можно заменить так:
if(tmp.Length = 1) then res += ' ' + tmp;
else if(tmp.Length = 2) res += ' ' + tmp;
else if(tmp.Length = 3) res += ' ' + tmp;
но в таких ситуациях принято использовать switch-case
}
case tmp.Length of // оператор выбора
1: res += ' ' + tmp; // если длина временной переменной = 1, то 3 пробела
2: res += ' ' + tmp; // если длина временной переменной = 2, то 2 пробела
3: res += ' ' + tmp; // если длина временной переменной = 3, то 1 пробел
end;
end;
if not (y = -1) then begin
res += ' | '; // если это первая итерация, то добавляем в конце палочку
end;
res += #10; // символ переноса строки
end;
result := res; // возвращаем результат
end;
function MyMatrix.ToHalfString(): string;
begin
// возвращает матрицу в виде треугольника (половины), нужна для "красивой" отрисовки матрицы в окошко результата
// тут все тоже самое, только не добавляет нижние элементы
var res: string;
for var y := -1 to self.Size - 1 do begin
if (y = -1) then begin
res += ' ';
end else begin
if (indices[y].ToString().Length = 1) then begin
res += ' ' + indices[y] + '|';
end else begin
res += indices[y] + '|';
end;
end;
for var x := 0 to self.Size - 1 do begin
if (x > y - 1) then begin // вот это условие не добавляет элементы
var tmp := '';
if (y = -1) then begin
tmp := indices[x].ToString()
end else begin
tmp := self[x, y].ToString();
end;
case tmp.Length of
1: res += ' ' + tmp;
2: res += ' ' + tmp;
3: res += ' ' + tmp;
end;
end else begin
res += ' ';
end;
end;
if not (y = -1) then begin
res += ' | ';
end;
res += #10;
end;
result := res;
end;
end.