include iostream iostream заголовочный файл классами функциями перемен

  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
#include <iostream>
/*
* iostream - заголовочный файл с классами, функциями и переменными для организации ввода-вывода в языке программирования
*/
#include <fstream>
/*
* fstream - заголовочный файл с классами, функциями и переменными для считывания данных из файла и для записи данных в файл.
*/
#include <vector>
/*
* vector - заголовочный файл с классами, функциями и переменными для работы с векторами
*/
#include <algorithm>
/*
* algorithm - заголовочный файл с классами, функциями и переменными для поиска, сортировки,
* подсчета, манипулирования и прочего с динамическими структурами данных
*/
#include <sstream>
/*
* sstream - заголовочный файл с классами, функциями и переменными для организации работы со строками, через интерфейс потоков
*/
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::atoi
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 с ключами
// atoi(positions[i] и atoi(positions[j]. std::atoi - функция для преобразования 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 << "Введите матрицу весов R" << endl;
int dim = n * m;
for (int i = 0; i < dim; ++i) {
R.push_back(vector<int>());
for (int j = 0; j < dim; ++j) {
cout << "Введите элемент R[" << i << "][" << j << "] = ";
int value;
cin >> value;
R[i].push_back(value);
}
}
cout << "Введите матрицу весов D" << endl;
for (int i = 0; i < dim; ++i) {
D.push_back(vector<int>());
for (int j = 0; j < dim; ++j) {
cout << "Введите элемент D[" << i << "][" << 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;
}