Program lists;
{
Это точно не нужно вставлять в отчет.
Здесь встречается 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)
Более сложный пример:
var kek = List<List<integer>>;
kek.Add(new List<integer>);
kek[0].Add(1);
kek[0].Add(3);
kek[0].Add(4);
kek.Add(new List<integer>);
kek[1].Add(1);
kek[1].Add(3);
kek[1].Add(4);
получится список: [[1, 3, 4], [1, 3, 4]]
Всякие возможности списка: (их в разы больше, здесь расписаны те, что используются в коде)
List.Add() - добавить значение в конец списка
List.Max() - получить максимальное значение из списка
List.Min() - получить минимальное значение из списка
List.Where(value -> condition) - получить все элементы, которые удовлетворяют условию (condition)
ну типо
List.Where(value -> value = 3) - выведет все элементы, которые равны 3
List.Where(value -> value > 3) - выведет все элементы, которые больше 3
List.Where(value -> value = List.Max()) - выведет все элементы, которые равные максимальному, и т.д.
List.Contains(value) - возвращает True, если список содержит элемент value, ну или false, если нет
}
function readFile(path: string; var matrix: List<List<integer>>): List<integer>;
{
Функция чтения матрицы из файла
Входные параметры - path (string) (путь к файлу)
matrix (List<List<integer>>) - пустой двумерный список, который будет хранить матрицу инцедентности из файла
Выходные значения:
result (List<integer>) - функция возвращает список, содержащий ограничения k и v, записанные в файле в первой строке
}
var filecontent: TextFile;
i: integer;
temp: string;
begin
assignfile(filecontent, path); // связываем файл по пути path с переменной filecontent
reset(filecontent); // открываем файл для чтения
matrix := new List<List<integer>>; // создаем пустой двумерный список (в нем будем хранить матрицу инцедентности)
result := new List<integer>; // создаем пустой список для результата, в нем будем хранить значения k и v из файла (первая строка)
while not eof(filecontent) do begin // цикло до тех пор, пока не будет считан весь файл (not eof(filecontent) - конец файла)
readln(filecontent, temp); // читаем строку из файла в переменную temp
if(i = 0) then begin // если это первая итерация цикла
foreach var val in temp.Split(' ').ToList() do begin // перебираем список
{
короче есть цикл
for var i := 0 to 10 do begin
тут тупо каждый раз увеличивается i от нуля до 10 и чето происходит
end;
а есть цикл, в котором не увеличивается индекс, а тупо перебирается структура данных
var _list := new List<integer>; // например этот список будет [1, 3, 5, 6, 7, 8]
foreach var val in _list do begin // в переменной val будет храниться значения из списка _list
writeln(val); // выведет в консоль на каждой итерации значение из списка, типо сначала 1, потом 3, потом 5 и т.д.
end;
короче, это удобно для перебора динамических структур, индексы которых могут быть удалены и т.д.
Теперь к line.Split(' ').ToList()
line - это строка матрицы, например "0 1 0 1 1 1 0 0 1"
.Split(separator) - функция, которую можно применить к переменной string типа, она разбивает строку на массив, с использованием разделителя (separator)
то есть line.Split(' ') - вернет массив [0, 1, 0, 1, 1, 1, 0, 0, 1].
другой пример
var string := '1,2;3,4.5,6,7,8,9;12,34';
string.Split(','); // вернет массив [1, '2;3', '4.5', 6, 7, 8, '9;12', 34]
и в завершение, т.к. это массив, а у нас везде список, то нужно преобразовать массив в список
для этого используется метод .ToList()
line.Split(' ').ToList() - то есть здесь происходит разбиение строки с помощью пробела, сохранение всех значений в массив и преобразование в список
и т.к. это входное значение в цикле foreach, то в переменной val будут храниться значение из этого списка, в зависимости от итерации
это проще, чем кажется
}
result.Add(val.ToInteger()); // добавляем значение в результирующий список
end;
end else begin // в противном случае перебираем матрицу из файла
matrix.Add(new List<integer>); // добавляем пустой список в лист
foreach var val in temp.Split(' ').ToList() do begin // перебираем циклом также, как описано выше
matrix[i - 1].Add(val.ToInteger()); // добавляем в матрицу значение из файла
end;
end;
inc(i); // увеличиваем i на 1 на каждой итерации (i := i + 1)
end;
closefile(filecontent); // закрываем файл
end;
function readKeyboard(var matrix: List<List<integer>>): List<integer>;
// входные - матрица инцедентности, выходные - список как и у других двух функций ввода
var n, m, k, v, temp: integer; // размерности массивов, ограничение и временная переменная для ввода в матрицу
begin
writeln('Введите размерность матрицы m:');
readln(m); // читаем размерность матрицы m
writeln('Введите размерность матрицы n:');
readln(n); // читаем размерность матрицы n
matrix := new List<List<integer>>;
for var i := 0 to m - 1 do begin
matrix.Add(new List<integer>);
for var j := 0 to n - 1 do begin
writeln('enter e', i, ', v', j);
readln(temp); // читаем значение из файла
matrix[i].Add(temp); // записываем в список
end;
end;
writeln('Введите количество элементов в блоке:');
readln(k); // читаем размерность матрицы n
writeln('Введите ограничение связей:');
readln(v); // читаем размерность матрицы n
result := new List<integer>;
result.Add(k);
result.Add(v);
end;
function getRandom(var matrix: List<List<integer>>): List<integer>;
{
Функция заполнения двумерного списка целочисленными значениями с помощью генератора рандома
Входные значения:
matrix (List<List<integer>>) - двумерный динамический список целочисленных значений. Изначально пустой, будет хранить матрицу смежности из файла.
Выходные значения:
result (List<integer>) - функция возвращает список, содержащий ограничения k и v, записанные в файле в первой строке
}
var n: integer; // n - размерность матрицы
begin
result := new List<integer>; // результирующий список, где 0 - k, 1 - v
result.Add(random(2, 3)); // добавляем случайной значение от 3 до 6 в результирующий список (это будет k)
n := result[0] * random(3, 4); // рассчитываем размерность массива, чтобы программа не вылетала из-за кривых данных. умножаем k на случайное число от 3 до 7
result.Add(n + 1); // v - число связей будет равно размерность + 1, иначе будет крашиться в какие-то моменты, когда нельзя выбрать элемент из-за того, что все оценки > v
matrix := new List<List<integer>>; // создаем пустой двумерный лист
for var i := 0 to n do begin // цикл от 0 до n
matrix.Add(new List<integer>); // добавляем пустой лист, типо строка
for var j := 0 to n - 1 do begin // цикл от 0 до n - 1
matrix[i].Add(random(0, 1)); // добавляем случайное значение 0 или 1 в матрицу
end;
end;
// writeln('n => ', n, ', m => ', n + 1, ', v => ', result[1], ', k => ', result[0]); // выводит в консоль значения размерности и ограничения, закомменчено
end;
procedure writeInFile(path, text: string);
{
процедура сохранения строки в файл
Входные значения:
path(string) - путь к файлу
text - текст, который сохранится в файл
Это процедура, она не возвращает никаких значений, типо void() из c++
}
var
F: TextFile; // указываем переменной F тип данных текстового файла
begin
assign(F, path); // присваиваем файл по пути src в переменную SourceFile
rewrite(F); // открываем файл для записи
writeln(F, text); // записываем строку val в файл
close(F); // закрываем файл
end;
function findL1(SP: List<List<integer>>; Ie: List<integer>; n: integer): integer;
{
Входные параметры SP - список SP, тип данных - List<List<integer>>
Ie - список неразмещенных элементов
n - размерность списка SP
Выходные данные:
Возвращает индекс элемента для размещения по результата расчета L1
}
{функция поиска оценки L1}
var max, key, sum: integer; // переменные для хранения минимального значения и ключа элемента с минимальным значением, а также переменная для хранения суммы
begin
var RSP := new List<integer>; // создаем пустой список RSP каждый раз при поиске L1
sum := 0; // присваиваем переменной суммы значение 0
RSP.Add(0); // добавляем в список 0 в начале
writeln('RSP =>', RSP); // выводим список
for var i := 0 to n - 1 do begin // цикл от 0 до размерности - 1
sum += SP[i].count; // прибавляем к сумме значение количества элементов списка SP с индексом i
RSP.Add(sum); // добавляем сумму в список RSP
end;
writeln('RSP list:', RSP); // выводим список RSP
max := 0; // присваиваем максимальное как 0
for var i := 0 to RSP.count - 2 do begin // перебираем циклом список RPS без одного элемента
if(Ie.Contains(i)) then begin // если текущий элемент содержится в списке нераспределенных элементов
writeln('L1(e', i, ')', RSP[i + 1] - RSP[i]); // выводим ошибку в консоль
if(RSP[i + 1] - RSP[i] >= max) then begin // если RSP[i + 1] - RSP[i] > текущего max
max := RSP[i + 1] - RSP[i]; // то это значение становится максимальным
key := i; // присваиваем ключ этого элемента в переменную key
end;
end;
end;
result := key; // возвращаем ключ элемента, для которого ошибка L1 удовлетворяет всем условиям
end;
function findL3(Ie, L2, block: List<integer>; v, n: integer; SP: List<List<integer>>): List<integer>;
{
функция поиска оценки L3
Входные параметры:
Ie (List<integer>) - список неразмещенных элементов
L2 (List<integer>) - список ошибок L2
block (List<integer>) - список элементов в блоке
v (integer) - ограничения на кол-во цепей
n (integer) - размерность списка SP
SP (List<List<integer>>) - список SP
}
var max, key: integer;
begin
result := new List<integer>; // создаем пустой результирующий список
for var i := 0 to n - 1 do begin
result.Add(0); // заполняем его нулями
end;
var blockList := new List<integer>; // создаем список связей для всех элементов в блоке
foreach var e in block do begin // перебираем все элементы в блоке и храним их в e
foreach var val in SP[e] do begin // перебираем все элементы списка SP с индексом e и храним их в переменной val
if(not blockList.Contains(val)) then begin // если blockList не содержит элемент val
blockList.Add(val); // добавляем его в список
end;
end;
end;
for var i := 0 to n - 1 do begin
var tempList := new List<integer>; // создаем пустой веременный лист
if(L2[i] < MaxInt) then begin // если L2 с индексом i меньше чем MaxInt(константа большого числа)
foreach var val in SP[i] do begin // перебираем список SP[i] и храним в val
if(blockList.Contains(val)) then begin // если blockList содержит val
tempList.Add(val); // добавляем его в tempList
end;
end;
writeln('L3(e', i, ') = ', tempList, ' => ', tempList.Count); // выводим в консоль
result[i] := tempList.Count; // присваиваем результирующему списку с индексом i значение оценки L3
end;
end;
end;
function check_incident(index, k:integer; block: List<integer>; SP: List<List<integer>>): boolean;
{
функция поиска инцедентных элементов
}
begin
var tempList := new List<integer>; // создаем временный список
block.Add(index); // добавляем элемент с индексом index в блок (временно, после удалим)
foreach var val in SP[0] do begin
tempList.Add(0); // перебираем список SP[0] (связи нулевого элемента) и добавляем их в tempList
end;
foreach var e in block do begin // перебираем список блока и храним в e
foreach var val2 in SP[e] do begin // перебираем список SP[e] и храним в val2
var i := 0;
foreach var val in SP[0] do begin // перебираем SP[0] и храним в val
if(val2 = val) then begin // если val2 = val
tempList[i] += 1; // увеличиваем значение tempList[i] на 1
end;
inc(i); // увеличиваем i на 1
end;
end;
end;
block.Remove(index); // удаляем элемент с индексом i из блока
result := false; // считаем, что результат функции поиска инцедентности равен лжи (то есть элементы не инцедентны)
for var i := 0 to tempList.Count - 1 do begin // цикл от 0 до количества элементов временного списка - 1
if(tempList[i] >= k - 1) then begin // если значение tempList[i] больше k - 1
result := true; // то считаем, что они инцедентны и возвращаем результат true
break; // останавливаем цикл
end;
end;
end;
function findL2(Ie, block: List<integer>;v, k, n: integer; SP: List<List<integer>>): List<integer>;
{
функция поиска оценки L3
Входные параметры:
Ie (List<integer>) - список неразмещенных элементов
block (List<integer>) - список элементов в блоке
v (integer) - ограничения на кол-во цепей
k (integer) - количество элементов в блоке
n (integer) - размерность списка SP
SP (List<List<integer>>) - список SP
Выходные - список оценок L2
}
var min, key: integer;
begin
min := maxInt;
result := new List<integer>; // создаем пустой результирующий список
for var i := 0 to n - 1 do begin
result.Add(MaxInt); // добавляем в этот список максимально возможное число
end;
var tempList := new List<integer>; // создаем пустой временный список для хранения суммы всех связей элементов уже распределенных в текущий блок (левая часть разности формулы L2)
var tempList2 := new List<integer>; // создаем пустой временный список для хранения правой части формулы из оценки (хз как ее назвать, то что вычитается)
var resultList := new List<integer>; // создаем пустой список для результата вычитания списков tempList и tempList2, то есть все связи оценки L2
for var i := 1 to n - 1 do begin
if(Ie.Contains(i)) then begin // если список нераспределенных элементов содержит элемент с индексом i
foreach var e in block do begin // перебираем список элементов в блоке
foreach var val in SP[e] do begin // перебираем список SP с индексом первого элемента блока в значение val
if(not tempList.Contains(val)) then begin // если элемента нет в списке tempList
tempList.Add(val); // доблавяем в список tempList значение val (все связи первого элемента блока)
end;
end;
end;
foreach var val in tempList do begin // перебираем список tempList
if(SP[i].Contains(val)) then begin // если их еще нет в списке tempList
tempList2.Add(val); // добавляем
end;
end;
writeln('templ2=>', tempList2);
foreach var val in SP[i] do begin // перебираем все связи элемента с индексом i
if(not tempList.Contains(val)) then begin // если их еще нет в списке tempList
tempList.Add(val); // добавляем
end;
end;
writeln('templ1=>', tempList);
foreach var val in tempList2 do begin // перебираем список tempList2
if(tempList.Contains(val)) then begin // если их еще нет в списке tempList
tempList.Remove(val); // удаляем из списка tempList
end;
end;
if(tempList.Count <= v) then begin // если количество связей в списке tempList меньше чем v
result[i] := tempList.Count; // меняем значение результирующего списка с индексом i на количество связей в списке tempList
end;
writeln('L2(e', i, ') = ', tempList, ' => ', tempList.Count); // выводим все оценка L2
tempList.Clear(); // очищаем временный список
tempList2.Clear(); // очищаем временный список
end;
end;
end;
function generateSP(n, m: integer; Q: List<List<integer>>): List<List<integer>>;
{функция генерации списка SP}
begin
result := new List<List<integer>>;
for var j := 0 to n - 1 do begin
result.Add(new List<integer>); // создаем пустой двумерный список
end;
for var j := 0 to m - 1 do begin
for var i := 0 to n - 1 do begin
if Q[i][j] = 1 then begin
result[i].Add(j); // перебираем матрицу по ij и добавляем значение в result[i]
end;
end;
end;
end;
function generateIe(n: integer): List<integer>;
{функция генерации списка Ie}
begin
result := new List<integer>;
for var i := 1 to n - 1 do begin
result.Add(i); // добавляем все элементы кроме нулевого
end;
end;
function generateBlocks(count: integer): List<List<integer>>;
{функция генерации списка блоков}
begin
result := new List<List<integer>>;
for var i := 0 to count - 1 do begin
result.Add(new List<integer>); // создаем пустой двумерный лист
end;
end;
function MatrixToString(n, m: integer; matrix: List<List<integer>>): string;
{функция преобразования матрицы в строку}
begin
result := 'Введенная матрица:' + #10; // добавляем текст + символ переноса на следующую строку
for var i := 0 to n - 1 do begin
for var j := 0 to m - 1 do begin
result += matrix[i][j] + ' '; // добавляем к переменной result значение матрицы + пробел
end;
result += #10; // добавляем символ переноса на следующую строку
end;
end;
function blocksToString(blocks: List<List<integer>>; count: integer): string;
{функция преобразования блоков в строку}
begin
{не сильно отличается от кода выше}
result := 'Итоговое распределение: ' + #10; // #10 - символ переноса строки
for var i := 0 to count - 1 do begin
result += 'b' + (i + 1) + '{';
for var j := 0 to blocks[i].Count - 1 do begin
result += 'e' + blocks[i][j];
if(j <> blocks[i].Count - 1) then begin
result += ',';
end;
end;
result += '}' + #10;
end;
end;
var Q, SP, blocks: List<List<integer>>;
RSP, Limits, Ie, L2, L3: List<integer>;
n, m, k, v, min, count, key, current: integer;
switch, save: char;
res, name: string;
begin
writeln('1 - ввод из файла, 2 - случайные числа, 3 - ввод с клавиатуры');
readln(switch); // читаем выбор пользователя
case switch of
'1': begin // если ввели 1
writeln('Введите название файла:');
readln(name); // читаем название файла
if fileExists(name) then begin // если файл существует
Limits := readFile(name, Q); // вызываем функцию чтения из файла и храним ее результат в Limits
k := Limits[0]; // присваиваиваем значение
v := Limits[1]; // присваиваиваем значение
end else begin // если не существует
writeln('Файл ', name, ' не существует.');
exit; // выход из программы
end;
end;
'2': begin // если ввели два
Limits := getRandom(Q); // вызываем функцию заполнения случайными числами и храним ее результат в Limits
k := Limits[0]; // присваиваиваем значение
v := Limits[1]; // присваиваиваем значение
end else begin
Limits := readKeyboard(Q); // вызываем фукнкцию заполнения матрицы с клавиатуры
k := Limits[0]; // присваиваиваем значение
v := Limits[1]; // присваиваиваем значение
end;
end;
n := Q.Count; // присваиваем переменной n размерность матрицы Q по строкам
m := Q[0].Count; // присваиваем переменной n размерность матрицы Q по столбцам
count := round((n - 1) / k); // round - округляет число до целого, считаем количество блоков
blocks := generateBlocks(count); // вызываем функцию генерации блоков
Ie := generateIe(n); // вызываем функцию заполнения списка нераспределенных элементов
res += MatrixToString(n, m, Q) + #10; // присваиваем к переменной res результата работы функции возвращающей матрицу в виде строки
SP := generateSP(n, Q[0].Count, Q); // вызываем функцию генерации списка SP
writeln('SP list:', SP);
repeat begin // цикл - пока список Ie не пуст (пока есть не распределенные элементы)
key := findL1(SP, Ie, n); // вызываем функцию расчет оценки L1 и получаем индекса элемента для размещения
writeln('В результате расчета оценки L1 элемент e', key, ' будет помещен в блок - ', current);
blocks[current].Add(key); // добавляем элемент в блок
Ie.Remove(key); // удаляем элемент из списка нераспределенных элементов
repeat begin // цикл - пока количество элементов в блоке не равно k
if(k - 1 = current) and (blocks[current].Count = k - 1) then begin // условие, если текущий элемент остался последним
writeln('Оставшийся элемент e', Ie.First(), ' будет помещен в блок - ', current);
blocks[current].Add(Ie.First()); // добавляем в блок
Ie.Remove(Ie.First()); // удаляем из списка
end else begin // в противном случае, если элемент не один
L2 := new List<integer>; //
L2 := findL2(Ie, blocks[current], v, k, n, SP);
if(L2.Where(val -> val < MaxInt).Count > 1) then begin // если количество ошибок L2 больше одной, то считаем L3
L3 := new List<integer>;
L3 := findL3(Ie, L2, blocks[current], v, n, SP); // вызываем функцию расчета L3, передаем в нее список нераспр. элементов, список ошибок L2
// элементы в текущем блоке, ограничение на количество связей, количество элементов и список SP
if(L3.Where(val -> val = L3.Max()).Count < 2) then begin // если количество ошибок L3 меньше 2
key := L3.LastIndexMax; // берем последний среди максимальных ключ списка L3
writeln('В результате расчета оценки L3 элемент e', key, ' будет помещен в блок - ', current); // выводим в консоль
end else begin // в противном случае, смотрим список L2
min := MaxInt; // присваиваем переменной min максимально возможное значение
for var i := 0 to n - 1 do begin
if(min > L2[i]) then begin // если минимальное значение больше чем оценка из списка L2
min := L2[i]; // считаем эту оценку минимальной
key := i; // присваиваем переменной key ключ этого элемента
end;
end;
writeln('В результате расчета оценки L2 элемент e', key, ' будет помещен в блок - ', current);
end;
end else begin // если количество ошибок L2 равно единице, то не считаем L3
key := L2.LastIndexMin; // берем последний среди минимальных ключ списка L2
writeln('В результате расчета оценки L2 элемент e', key, ' будет помещен в блок - ', current);
end;
blocks[current].Add(key); // добавляем элемент в блок
Ie.Remove(key); // удаляем элемент из списка
end;
end until blocks[current].Count = k; // цикл repeat до тех пора, пока условие выполняется
foreach var e in blocks[current] do begin
//SP[e].Clear(); // удаляем элементы блока из списка SP
end;
inc(current);
end until Ie.Count = 0; // цикл repeat до тех пора, пока условие выполняется
res += blocksToString(blocks, count) + #10;
writeln(res);
writeln('Вы хотите сохранить результат работы программы в файл? y/n');
readln(switch);
if(switch = 'y') then begin
writeInFile('output.txt', res); // вызов функции сохранения в файл
end;
end.