#include <iostream>
/*
* iostream - заголовочный файл с классами, функциями и переменными для организации ввода-вывода в языке программирования
*/
#include <fstream>
/*
* fstream - заголовочный файл с классами, функциями и переменными для считывания данных из файла и для записи данных в файл.
*/
#include <vector>
/*
* vector - заголовочный файл с классами, функциями и переменными для работы с векторами
*/
#include <algorithm>
/*
* algorithm - заголовочный файл с классами, функциями и переменными для поиска, сортировки,
* подсчета, манипулирования и прочего с динамическими структурами данных
*/
#include <sstream>
#include <string>
#include <stdlib.h>
using namespace std;
/*
* использование пространства имён std, без него придется везде писать std::string, std::cin, std::cout, std::vector, std::remove и т.д.
* однако, в крупных проектах так и пишут, отказываясь от using namespace std
*/
vector<int> split(string line, char separator) {
/**
* Разбивает строку на вектор содержащий элементы строки, разделенные separator
*
* @param {string} - line строка, которую нужно разбить на элементы разделяющим символом
* @param {char} separator - разделяющий символ, например пробел
* @returns {vector<int>} - вектор, содержащий разбитую строку без разделяющего символа
*
*/
vector<int> result; // переменная для хранения реузльтирующего вектора (его вернет функция)
string temp; // переменная для хранения строки
for (int i = 0; i < line.length(); ++i) { // цикл от 0 до размера переданной строки
if (line[i] != separator) { // если текущий элемент строки не равен сепарирующему (пробел)
temp += line[i]; // добавляем к временной переменной значение из строки
} else { // в противном случае
result.push_back(atoi(temp.c_str())); // добавляем в результирующий вектор значение temp преобразованное в integer
// с помощью функции std::stoi
temp = ""; // обнуляем переменную temp
}
}
if (!temp.empty()) { // если темп не пустая
result.push_back(atoi(temp.c_str())); // добавляем в результирующий вектор значение temp преобразованное в integer
}
return result; // возвращаем результирующий вектор
}
string to_string(int value) {
/**
* Функция конвертирования целочисленного значения в строку
*
* @param {int} value - число, которое нужно конвертировать в строку
* @returns {string} - возвращает число конвертированное в строку
*
*/
return static_cast<ostringstream*>( &(ostringstream() << value) )->str();
}
void fromFile(const char *filename, vector<vector<int> > &R, vector<vector<int> > &D, vector<vector<int> > &directives, int &n, int &m) {
/**
* Функция чтения входных значений из файла в переменные R, D, directives, n, m
*
* @param {const char} *filename - название файла
* @param {vector<vector<int> >} &R - ссылка на матрицу R
* @param {vector<vector<int> >} &D - ссылка на матрицу D
* @param {vector<vector<int> >} &directives - ссылка на матрицу directives
* @param {int} &n - ссылка на целочисленное значение n
* @param {int} &m - ссылка на целочисленное значение m
* @returns {void} - ничего не возвращает
*
*/
ifstream in(filename); // открываем файл для чтения
if (in.is_open()) { // если файл открылся
string line; // переменная для хранения строки
vector<int> temp; // переменная для хранения временных значений
while (getline(in, line) and
line != "Directives") { // цикл, пока можно получить строку из файла и строка не равна "Directives"
temp = split(line, ' '); // разбиваем строку на вектор с помощью функции split
n = temp[0]; // присваиваем размерность n
m = temp[1]; // присваиваем размерность m
}
int index = 0; // переменная для хранения итерации цикла
while (getline(in, line) and line != "R") { // цикл, пока можно получить строку из файла и строка не равна "R"
directives.push_back(vector<int>()); // помещаем пустой целочисленный вектор в конец
temp = split(line, ' '); // разбиваем строку на вектор с помощью функции split
for (int j = 0; j < temp.size(); ++j) { // перебираем циклом вектор temp
directives[index].push_back(temp[j]); // добавляем в конец directives[index] значение temp[j]
}
index++; // добавляем к индексу 1
}
index = 0; // обнуляем индекс
while (getline(in, line) and line != "D") { // цикл, пока можно получить строку из файла и строка не равна "D"
R.push_back(vector<int>()); // помещаем пустой целочисленный вектор в конец
temp = split(line, ' '); // разбиваем строку на вектор с помощью функции split
for (int j = 0; j < temp.size(); ++j) { // перебираем циклом вектор temp
R[index].push_back(temp[j]); // добавляем в конец R[index] значение temp[j]
}
index++; // добавляем к индексу 1
}
/*
* дальше тоже самое, формируем матрицу D
*/
index = 0;
while (getline(in, line)) {
D.push_back(vector<int>());
temp = split(line, ' ');
for (int j = 0; j < temp.size(); ++j) {
D[index].push_back(temp[j]);
}
index++;
}
} else { // если не открылся, пишем ошибку
cout << "file not found";
}
}
bool contains(int value, vector<int> vector) {
/**
* Проверяет, содержится ли значение value в списке vector
*
* @param {int} - value значение, которое ищем в vector
* @param {vector<int>} vector - вектор, в котором ищем значенеи
* @returns {bool} - true, в случае, если значение value нашлось в vector, false в противоположном случае.
*
*/
return find(vector.begin(), vector.end(), value) != vector.end(); // и
}
bool check(int index, vector<string> positions, vector<int> Kr) {
/**
* Проверяет, содержится ли значение value в списке vector
*
* @param {int} - index текущий индекс(номер) элемента
* @param {vector<string>} positions - вектор позиций элементов
* @param {vector<int>} Kr - вектор, в котором хранятся позиции, в которые можно поместить элемент (которая помечается + в лабе)
* @returns {bool} - true, в случае, если значение индекс не выходит за границы размерностей,
* не содержится в списке Kr, а также значение позиции с этим индексом равно "-", false в противоположном случае
*
*/
return index >= 0 && index < positions.size() && positions[index] == "-" && !contains(index, Kr);
}
void vector_remove(int value, vector<int> &vector) {
/**
* Удаляет значение value из вектора &vector
*
* @param {int} - value значение, которое нужно удалить
* @param {vector<int>} &vector - ссылка на вектор, из которого нужно удалить значение
* @returns {void} - ничего не возвращает
*
*/
vector.erase(remove(vector.begin(), vector.end(), value), vector.end());
}
int calculate_length(vector<vector<int> > R, vector<vector<int> > D) {
/**
* Функция для расчёта длины L
*
* @param {vector<vector<int> >} R - матрица R
* @param {vector<vector<int> >} &D - матрица D
* @returns {int} - возвращает длину
*
*/
int sum = 0; // переменная для хранения результирующей длины
for (int i = 0; i < R.size(); ++i) { // цикл от нуля до размера вектора R
for (int j = 0; j < R[i].size(); ++j) { // цикл от нуля до размера вектора R[i]
sum += R[i][j] * D[i][j]; // прибавляем к sum результат перемножения ij элементов матриц R и D
}
}
return sum / 2; // возвращаем полусумму
}
vector<vector<int> > swap(vector<vector<int> > R, vector<string> positions) {
/**
* Функция перестановки элементов в матрице R
*
* @param {vector<vector<int> >} R - матрица R
* @param {vector<positions>} positions - вектор позиций
* @returns {vector<vector<int> >} - возвращает матрицу после перестановок
*
*/
vector<vector<int> > result; // резултирующая матрица
for (int i = 0; i < R.size(); ++i) { // цикл от 0 до размера матрицы R
result.push_back(vector<int>()); // помещаем пустой вектор в конец
for (int j = 0; j < R[i].size(); ++j) { //цикл от 0 до размера матрицы R[i]
result[i].push_back(R[atoi(positions[i].c_str())][atoi(positions[j].c_str())]); // добавляем в результирующий вектор значение из матрицы R с ключами
// stoi(positions[i] и stoi(positions[j]. std::stoi - функция для преобразования string в integer
}
}
return result; // возвращаем матрицу после перестановок
}
int main() {
setlocale(LC_ALL, "Russian");
vector<vector<int> > R, D, directives;
vector<int> Ir, Er, Kr;
vector<string> positions;
int n, m, iteration = 0;
char choose;
cout << "Если хотите ввести данные из файла, нажмите 1. В противном случае, будет применен ручной ввод" << endl;
cin >> choose;
if (choose == '1') {
fromFile("input.txt", R, D, directives, n, m);
} else {
cout << "Введите n" << endl;
cin >> n;
cout << "Введите m" << endl;
cin >> m;
cout << "Введите количество директивных элементов:" << endl;
int count;
cin >> count;
for (int i = 0; i < count; ++i) {
vector<int> temp;
cout << "Введите директивный элемент:" << endl;
int element;
cin >> element;
cout << "Введите позицию директивного элемента:" << endl;
int position;
cin >> position;
temp.push_back(position);
temp.push_back(element);
directives.push_back(temp);
}
cout << directives[0][0];
cout << "Введите матрицу весов R" << endl;
for (int i = 0; i < n; ++i) {
R.push_back(vector<int>());
for (int j = 0; j < m; ++j) {
int value;
cin >> value;
R[i].push_back(value);
}
}
cout << "Введите матрицу весов D" << endl;
for (int i = 0; i < n; ++i) {
D.push_back(vector<int>());
for (int j = 0; j < m; ++j) {
int value;
cin >> value;
D[i].push_back(value);
}
}
}
for (int i = 0; i < R.size(); ++i) {
positions.push_back("-");
Ir.push_back(i);
}
for (int i = 0; i < R.size(); ++i) {
for (int j = 0; j < directives.size(); ++j) {
if (i == (directives[j][1] - 1)) {
positions[i] = to_string(directives[j][0] - 1);
Er.push_back(directives[j][0] - 1);
vector_remove(directives[j][0] - 1, Ir);
}
}
}
int index = 0;
do {
iteration++;
for (int i = 0; i < positions.size(); ++i) {
if (positions[i] != "-") {
if (check(i - n, positions, Kr)) {
Kr.push_back(i - n);
}
if (i % n != 0) {
if (check(i - 1, positions, Kr)) {
Kr.push_back(i - 1);
}
}
if ((i + 1) % n != 0) {
if (check(i + 1, positions, Kr)) {
Kr.push_back(i + 1);
}
}
if (check(i + n, positions, Kr)) {
Kr.push_back(i + n);
}
}
}
sort(Kr.begin(), Kr.end());
cout << "Шаг " << iteration << endl;
int max = INT_MIN;
for (int i = 0; i < Ir.size(); ++i) {
int Je = 0;
for (int j = 0; j < R.size(); ++j) {
if (R[Ir[i]][j] != 0) {
if (contains(j, Er)) {
Je += R[Ir[i]][j];
} else {
Je -= R[Ir[i]][j];
}
}
}
cout << "\te" << Ir[i] + 1 << ": J = " << Je << endl;
if (Je > max) {
max = Je;
index = Ir[i];
}
}
vector<vector<int> > tempVector;
int count = 0;
for (int i = 0; i < Er.size(); ++i) {
if (R[index][Er[i]] != 0) {
int j = 0;
for (j = 0; j < positions.size(); ++j) {
if (positions[j] == to_string(Er[i])) {
break;
}
}
tempVector.push_back(vector<int>());
tempVector[count].push_back(R[index][Er[i]]);
tempVector[count].push_back(j);
count++;
}
}
int F, min = INT_MAX, position = 0;
for (int i = 0; i < Kr.size(); ++i) {
cout << "\tВ позиции" << Kr[i] + 1 << ": F = ";
F = 0;
for (int j = 0; j < tempVector.size(); ++j) {
F += tempVector[j][0] * D[Kr[i]][tempVector[j][1]];
}
cout << F << endl;
if (F < min) {
min = F;
position = Kr[i];
}
}
positions[position] = to_string(index);
cout << "\tЭлемент " << index + 1 << " помещен в позицию" << (position + 1) << endl;
vector_remove(position, Kr);
vector_remove(index, Ir);
Er.push_back(index);
} while (!Ir.empty());
string output;
output += "Итоговое размещение: \nL до размещения элементов: " + to_string(calculate_length(R, D)) + "\n";
for (int i = 0; i < positions.size(); ++i) {
output += to_string((atoi(positions[i].c_str()) + 1)) + "\t";
if ((i + 1) % n == 0) {
output += "\n";
}
}
cout << R[0][2] << endl;
R = swap(R, positions);
output += "L после размещения элементов: " + to_string(calculate_length(R, D)) + "\n";
cout << output;
cout << "Вы хотите сохранить результат работы в файл? 1 - Да";
cin >> choose;
if (choose == '1') {
ofstream out;
out.open("output.txt");
out << output;
out.close();
}
system("pause");
return 0;
}